Problem 1698

1. Base Case:
For $n = 1$, we have the sets $A_1$ and $A_2$ which are non-empty subsets of $\{1\}$. Since there are only two sets, they must either be equal or one is a subset of the other. In either case, we can find two disjoint non-empty subsets of $\{1, 2\}$ such that their unions are equal. This is trivial and serves as our base case.

2. Induction Hypothesis:
Assume the statement is true for $n-1$. That is, for any $n$ non-empty subsets $A_1, A_2, \ldots, A_n$ of $\{1, 2, \ldots, n-1\}$, there exist two disjoint non-empty subsets of $\{1, 2, \ldots, n\}$ such that the union of the subsets is equal.

3. Induction Step:
We need to show that the statement holds for $n$. Consider the sets $A_1, A_2, \ldots, A_{n+1}$ which are non-empty subsets of $\{1, 2, \ldots, n\}$.

4. Definitions:
For a set $U$ of indices, define:
$$S_U := \bigcup_{x \in U} A_x, \quad V_U = \{A_x \mid x \in U\}$$
Note that $S_U$ is the union of the members of $V_U$.

5. Classification of Sets:
Call a set *bad* if it contains $n$ and *good* otherwise. If there exists at most one *bad* set, then by the induction hypothesis, we are done. So assume there are at least two *bad* sets.

6. Assumption:
Assume that there do not exist disjoint subsets $X, Y$ of indices such that $A_x, A_y$ are *good* for all $x \in X, y \in Y$ and $S_X = S_Y$. Otherwise, we are trivially done.

7. Choosing Families:
Choose two families of sets $A$ and $B$ with $n$ elements each such that each of them contains at least one bad set. Remove the element $n$ from all the *bad* sets. By the induction hypothesis, we find two disjoint subsets $X_1, Y_1$ of indices in $A$ and $X_2, Y_2$ in $B$ satisfying:
$$S_{X_1} = S_{Y_1}, \quad V_{X_1} \cap V_{Y_1} = \emptyset$$
$$S_{X_2} = S_{Y_2}, \quad V_{X_2} \cap V_{Y_2} = \emptyset$$

8. Ensuring Disjointness:
By our assumption, at least one of $S_{X_1}$ or $S_{Y_1}$ must contain a bad set, say $S_{X_1}$. Similarly, assume that $S_{Y_2}$ contains a bad set.

9. Combining Sets:
Hence, we find $M, N$ such that:
$$S_M = S_{X_1} \cup S_{X_2} \cup \{n\} = S_{Y_1} \cup S_{Y_2} \cup \{n\} = S_N$$
We can add back the $\{n\}$ to all the bad sets which exist both in the LHS and RHS, and so we are done.

10. Handling Overlap:
If there is a set $A_k$ on both sides, then $M, N$ are not disjoint. We can remove $A_k$ from both sides and still have:
$$S_M \setminus A_k = S_N \setminus A_k$$
This is because all elements of $A_k$ are in $S_{Y_1}$ and $S_{X_2}$. Hence, even if we delete the set $A_k$ from both sides, the elements will still remain on both sides, and we will still have $S_M \setminus A_k = S_N \setminus A_k$.

Thus, we have shown that there exist two disjoint non-empty subsets of $\{1, 2, \ldots, n+1\}$ such that their unions are equal.

$\blacksquare$