The numbers from$ 1$ to $2016$ are divided into three (disjoint) subsets $A, B$ and $C$, each one contains exactly $672$ numbers. Prove that you can find three numbers, each from a different subset, such that the sum of two of them is equal to the third.
HIDE: original wording Skaitļi no 1 līdz 2016 ir sadalīti trīs (nešķeļošās) apakškopās A, B un C, katranotām satur tieši 672 skaitļus. Pierādīt, ka var atrast trīs tādus skaitļus, katru no citas apakškopas, ka divu no tiem summa ir vienāda ar trešo.Problem
Source: 2016 Latvia BW TST P9
Tags: combinatorics, Subsets
18.12.2022 23:05
(Just to bump and give a reference) This PNT's problem implies the desired
19.12.2022 08:40
We will generalize $2016$ by $3n$. Assume contradiction (there doesn't exists $3$ numbers like that) Assume $1 \in A$ and $k \in B$ is the minimum number that not in $A$. We will prove that $c-1 \in A \forall c \in C$. We have $\forall c \in C, c-1 \notin B$ (else we will have $(1,c-1,c)$ that satisfied) Assume exists $c,c-1 \in C$ Now, considering the trio $(c-k,k,c)$ with $c \in C$. Since $k \in B,c \in C$, therefore $c-k \notin A$. Considering $(k-1,c-k,c-1)$ we also have $c-k \notin B$. Therefore, $c-k \in C$. Similarly, by considering $(c-k-1,k,c-1)$ and $(1,c-k-1,c-k)$ we infer $c-k-1 \in C$. Inducting and we have $c-ik,c-ik-1 \in C \forall i \geq 0, i<\dfrac{c-1}{k}$. But obviously there exists $i$ satisfied $0 \leq i <\dfrac{c-1}{k}$ and $c-ik \leq k$, so $c-ik \in A$ or $B$, contradiction. Therefore, $\forall c \in C,c-1 \in A$. If $C=\lbrace c_1,c_2,\cdots , c_n\rbrace$, then $\lbrace c_1-1,c_2-1,\cdots, c_n-1 \rbrace \subset A$ Since $\min C >k>1$, we can see $1 \notin \lbrace c_1-1,c_2-1,\cdots, c_n-1 \rbrace$. So $\lbrace 1,c_1-1,c_2-1,\cdots, c_n-1 \rbrace \subset A$, or $A$ has more than $n$ elements, contradiction.