48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Call a set $M$ of integers good if $47\nmid a-b+c-d+e$ for any $a,b,c,d,e\in M$.

Consider the set $J=\{-9,-7,-5,-3,-1,1,3,5,7,9\}$. We claim that $J$ is good. Actually, for any $a,b,c,d,e\in J$ the number $a-b+c-d+e$ is odd and $$-45=(-9)-9+(-9)-9+(-9)\le a-b+c-d+e\le 9-(-9)+9-(-9)+9=45.$$ But there is no odd number divisible by $47$ between $-45$ and $45$.

For any $k=1,\dots ,46$ consider the set $$A_k=\{x\in X\mid \exists j\in J:kx\equiv j(\mathrm{mod}47)\}.$$ If $A_k$ is not good, then $47\mid a-b+c-d+e$ for some $a,b,c,d,e\in A_k$, hence $47\mid ka-kb+kc-kd+ke$. But set $J$ contains numbers with the same residues modulo $47$, so $J$ also is not good. This is a contradiction; therefore each $A_k$ is a good subset of $X$.

Then it suffices to prove that there exists a number $k$ such that $|A_k|\ge 2007$. Note that each $x\in X$ is contained in exactly $10$ sets $A_k$. Then $$\sum _{k=1}^{46}|A_k|=10|X|=100000$$ hence for some value of $k$ we have $$|A_k|\ge \frac{100000}{46}>2173>2007$$