4. At least how many elements must we arbitrarily choose from the group ( $\phi_{2016},+$ ) so that among them there are surely three elements (not necessarily distinct) whose sum is $\hat{0}$?

## County School Inspectorate

Harghita

## Mathematics Olympiad - 12th grade regional stage - February 27, 2016  Solutions and grading criteria
4. At least how many elements must we arbitrarily choose from the group $\left(\phi_{2016},+\right)$ so that among them there are surely three elements (not necessarily distinct) whose sum is...̣̂ ?....... 1p

## Solution

If we choose all the elements.................................... odd, then any three of them have an odd sum, which cannot be $2016 k=\hat{0}$. Therefore, we must choose at least 1009 elements.

Next, we will show that this is sufficient. If $A=\left\{x_{0}, x_{1}, \ldots, x_{1008}\right\}$ with $x_{0}<x_{1}<\ldots<x_{1008}$ is an arbitrary subset with 1009 elements of the set $\notin_{2016}$, then the set $B=\left\{x_{0}+x_{1}, x_{0}+x_{2}, \ldots, x_{0}+x_{1008}\right\}$ has 1008 elements.

The set of the negatives of the elements of set $A, A \phi=\left\{-x_{0},-x_{1}, \ldots,-x_{1008}\right\}$ contains 1009, so $A \notin C ̧ B{ }^{1}$ Æ. Therefore, there exist $i, j$ Î $\{0,1, \ldots, 1008\}$ such that $-x_{i}=x_{0}+x_{j}$, so $x_{i}+x_{0}+x_{j}=\hat{0}$.