Graph and Magic¶

Solution¶

When does removing a number \(x\) from the sets result in two equal sets? Only when there exist two sets, say \(A_i, A_j\), whose only difference is \(x\). This means all numbers except \(x\) are either present in both or absent from both.

Now, we model the problem as a graph by considering \(n\) vertices, each representing an \(A_i\). Draw an edge between two vertices \(u,v\) with weight \(w\) if the only difference between \(A_u, A_v\) is the element \(w\). Now, the problem is equivalent to proving that there exists a weight that does not appear among the edges!

According to our graph modeling, each time we traverse an edge with weight \(w\), the element \(w\) is either removed from or added to our current set. Thus, in any closed walk, each weight must appear an even number of times (because the presence or absence of each element must change an even number of times to return to the initial set after traversing the walk).

Now, assume for contradiction that for every weight, there is at least one edge with that weight. So, for each weight, choose an arbitrary edge with that weight and form a graph \(G\) with \(n\) edges. First, it is clear that graph \(G\) has no cycles. Because if there were a cycle, each weight would have to appear an even number of times, which is impossible since we have exactly one edge for each weight. Therefore, \(G\) must be a forest. On the other hand, we said \(G\) has exactly \(n\) edges, and we know this is impossible (because the maximum number of edges in a forest corresponds to a tree, which has \(n-1\) edges). Thus, from the resulting contradiction, we can conclude that there is a weight that does not appear among the edges, which proves our claim.