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=\varnothing$, then $A_i=A_j=\{n+1\}$. The proposition is proven.

Case II There exists only one $i$ such that $B_i=\varnothing$. There is no loss of generality in supposing $B_{n+2}=\varnothing$, 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 \cdots \cup B_{i_k}=B_{j_1}\cup \cdots \cup B_{j_m}.\stackrel{◯}{1}$$ We write $C=A_{i_1}\cup \cdots \cup A_{i_k}$, $D=A_{j_1}\cup \cdots \cup A_{j_m}$. Then $C$ and $D$ differ at the most by the element $n+1$. (This can be shown by $\stackrel{◯}{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 \cdots \cup B_{i_k}=B_{j_1}\cup \cdots \cup B_{j_m}.\stackrel{◯}{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 \cdots \cup B_{r_u}=B_{t_1}\cup \cdots \cup B_{t_v}.\stackrel{◯}{3}$$ Again, we write $C=A_{i_1}\cup \cdots \cup A_{i_k}$, $D=A_{j_1}\cup \cdots \cup A_{j_m}$, and write $E=A_{r_1}\cup \cdots \cup A_{r_u}$, $F=A_{t_1}\cup \cdots \cup A_{t_v}$. By using $\stackrel{◯}{2}$, $\stackrel{◯}{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\ne D$ and $E\ne 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},\stackrel{◯}{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\}=\varnothing$, 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{array}{ll}1,& i\in A_j,\\ 0,& i\notin A_j.\end{array}$$ 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+\cdots +x_{n+1}{a}_{n+1}=0.\stackrel{◯}{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}+\cdots +x_{i_k}{a}_{i_k}=y_{j_1}{a}_{j_1}+\cdots +y_{j_m}{a}_{j_m},\stackrel{◯}{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 \cdots \cup A_{i_k}=A_{j_1}\cup \cdots \cup A_{j_m}.\stackrel{◯}{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.