China Western Mathematical Olympiad

Proof I We prove by induction for $n$.

When $n = 1$, $A_1 = A_2 = \{1\}$, the proposition holds.

Suppose it holds for $n$. We consider the case of $n+1$.
Suppose $A_1, A_2, \dots, A_{n+2}$ are nonempty subsets of $\{1, 2, \dots, n+1\}$. Let $B_i = A_i \setminus \{n+1\}, i = 1, 2, \dots, n+2$. We will prove the following cases.

Case I There exist $1 \le i < j \le n+2$ such that $B_i = B_j = \emptyset$, then $A_i = A_j = \{n+1\}$. The proposition is proven.

Case II There exists only one $i$ such that $B_i = \emptyset$. There is no loss of generality in supposing $B_{n+2} = \emptyset$, and that is $A_{n+2} = \{n+1\}$. Now by the inductive assumption, for $\{1, 2, \dots, n+1\}$, there exist two disjoint subsets $\{i_1, \dots, i_k\}$ and $\{j_1, \dots, j_m\}$ such that
$$B_{i_1} \cup \dots \cup B_{i_k} = B_{j_1} \cup \dots \cup B_{j_m}. \qquad \textcircled{1}$$
We write $C = A_{i_1} \cup \dots \cup A_{i_k}$, $D = A_{j_1} \cup \dots \cup A_{j_m}$. Then $C$ and $D$ differ at the most by the element $n+1$. (This can be shown by $\textcircled{1}$ and the definition of $B_i$.) In this case, we can make the proposition to hold true by putting $A_{n+2}$ into $C$ or $D$.

Case III No $B_i$ is empty. Now $B_1, B_2, \dots, B_{n+1}$ are nonempty subsets of $\{1, 2, \dots, n\}$. By the inductive assumption, we show that, for $\{1, 2, \dots, n+1\}$, there exist disjoint subsets $\{i_1, \dots, i_k\}$ and $\{j_1, \dots, j_m\}$ such that
$$B_{i_1} \cup \dots \cup B_{i_k} = B_{j_1} \cup \dots \cup B_{j_m}. \qquad \textcircled{2}$$
In addition, $B_2, B_3, \dots, B_{n+2}$ are also nonempty subsets of $\{1, 2, \dots, n\}$. By the inductive assumption, we can show that, for $\{2, 3, \dots, n+2\}$, there exist disjoint subsets $\{r_1, \dots, r_u\}$ and $\{t_1, \dots, t_v\}$ such that
$$B_{r_1} \cup \dots \cup B_{r_u} = B_{t_1} \cup \dots \cup B_{t_v}. \qquad \textcircled{3}$$
Again, we write $C = A_{i_1} \cup \dots \cup A_{i_k}$, $D = A_{j_1} \cup \dots \cup A_{j_m}$, and write $E = A_{r_1} \cup \dots \cup A_{r_u}$, $F = A_{t_1} \cup \dots \cup A_{t_v}$. By using $\textcircled{2}$, $\textcircled{3}$ and the definition of $B_i$, we see that $C$ and $D$ differ at the most by the element $n+1$, and so do $E$ and $F$. If $C = D$ or $E = F$, then the proposition holds. Hence we need only to consider the case when $C \neq D$ and $E \neq F$. There is no loss of generality in supposing $C = D \cup \{n+1\}$, but $E = F \setminus \{n+1\}$. Now $C \cup E = D \cup F$. After amalgamating the sets occurred repeatedly in $C$ and $E$, as well as in $D$ and $F$, we get two subsets $\{p_1, \dots, p_x\}$ and $\{q_1, \dots, q_y\}$ of $\{1, 2, \dots, n+2\}$ such that
$$A_{p_1} \cup \cdots \cup A_{p_x} = A_{q_1} \cup \cdots \cup A_{q_y}, \qquad \textcircled{4}$$
where $G = A_{p_1} \cup \cdots \cup A_{p_x} = C \cup E$, $H = A_{q_1} \cup \cdots \cup A_{q_y} = D \cup F$.

Now, if $\{p_1, \cdots, p_x\} \cap \{q_1, \cdots, q_y\} = \emptyset$, then the proposition holds. If there is $i \in \{p_1, \cdots, p_x\} \cap \{q_1, \cdots, q_y\}$, we write $\tilde{C} = \{A_{i_1}, \cdots, A_{i_k}\}$, $\tilde{D} = \{A_{j_1}, \cdots, A_{j_m}\}$, $\tilde{E} = \{A_{r_1}, \cdots, A_{r_u}\}$, $\tilde{F} = \{A_{t_1}, \cdots, A_{t_v}\}$. And there is no loss of generality in assuming that $A_i$ does not belong to $\tilde{C}$ and $\tilde{E}$ at the same time, and it does not belong to $\tilde{D}$ and $\tilde{F}$ at the same time too. Hence there are only two possibilities.

(a) $A_i \in \tilde{C}$ and $A_i \in \tilde{F}$. If there are two sets in $\tilde{C}$ containing $n+1$, then we take away set $A_i$ from the left side in ④. Now since all elements except $n+1$ in $A_i$ belong to $E$ (in view of ③), and there are two sets on the left side in ④ containing $n+1$. Thus after taking away $A_i$, the number of elements in $G$ does not reduce and ④ is still an equality. In the same way, if there are two sets in $\tilde{F}$ containing $n+1$, then we take away $A_i$ from the right side in ④, and ④ still holds.
Of course, if there is only one set in $\tilde{C}$ and $\tilde{F}$ containing $n+1$, then after taking away $A_i$ from both sides in ④, it remains to be an equality. (Now, by ② and ③, we can see that the two sides of ④ will not become empty sets.)

(b) $A_i \in \tilde{D}$ and $A_i \in \tilde{E}$, then $n+1 \notin A_i$. Now after taking away $A_i$ from both sides in ④, the resulting expression is still an equality.

In view of the above operation, we have a method to make the two sets of subscripts $\{p_1, \cdots, p_x\}$ and $\{q_1, \cdots, q_y\}$ in ④ disjoint. Therefore the proposition holds for $n+1$.

Proof II Here we need to use a fact from linear algebra that $n+1$ vectors in the $n$-dimensional linear space are linearly dependent.

If element $i$ is in set $A_j$, we write it as 1, otherwise write it as 0. Then $A_j$ corresponds to an $n$-dimensional vector, which is nonzero and contains 0 and 1. We write $a_j = (a_{j_1}, a_{j_2}, \cdots, a_{j_n})$, where
$$a_{j_i} = \begin{cases} 1, & i \in A_j, \\ 0, & i \notin A_j. \end{cases}$$
Since $a_1, a_2, \dots, a_{n+1}$ are $n+1$ vectors in the $n$-dimensional space, so there exists a group of real numbers, not every one of them to be zero, $x_1, x_2, \dots, x_{n+1}$ such that
$$x_1 a_1 + x_2 a_2 + \dots + x_{n+1} a_{n+1} = 0. \qquad \textcircled{5}$$
Hence, for $\{1, 2, \dots, n+1\}$, there exist two disjoint and nonempty subsets $\{i_1, \dots, i_k\}$ and $\{j_1, \dots, j_m\}$ such that
$$x_{i_1} a_{i_1} + \dots + x_{i_k} a_{i_k} = y_{j_1} a_{j_1} + \dots + y_{j_m} a_{j_m}, \qquad \textcircled{6}$$
where $x_{i_1}, \dots, x_{i_k} > 0$, $y_{j_1} = (-x_{j_1})$, $\dots$, $y_{j_m} = (-x_{j_m}) > 0$ (Here, it is essential to put the terms with coefficients greater than zero in ⑤ to one side, and those with coefficients less than zero to another side).
We conclude that
$$A_{i_1} \cup A_{i_2} \cup \dots \cup A_{i_k} = A_{j_1} \cup \dots \cup A_{j_m}. \qquad \textcircled{7}$$
In fact, if element $a$ ($1 \le a \le n$) belongs to the left side in ⑦, then the $a$-th component of the sum of the vectors from the left side in ⑥ must be greater than zero. Thus it makes the $a$-th component of the sum of the vectors from the right side in ⑥ to be greater than zero. Hence, there is $a_{j_t}$, and its $a$-th component is 1, that is, $a \in A_{j_t}$. Conversely, it is also true, that is, ⑦ holds.