Consider a graph, where every set \(A_i\) is a vertex and two vertices are connected if and only if their symmetric difference is a singleton \(\{x\}\) for a certain \(x\in\{1,2,\dots,n\}\). If such an arc arises, it will be given weight \(x\). The question now transforms into: prove that not all possible weights occur in the graph.
In each cycle of this graph, there has to exist a weight that occurs at least twice. In this way, one can delete an arc of this weight, resulting in a graph with the same number of different weight occurrences, but less cycles. Repeating this process, we end up with an acyclic graph with equally many different weights as the original graph. In graph theory, it is known that an acyclic graph with \(n\) vertices contains at most \(n-1\) arcs.