Let us have $n$ ( $n>3$) balls with different rays. On each ball it is written an integer number. Determine the greatest natural number $d$ such that for any numbers written on the balls, we can always find at least 4 different ways to choose some balls with the sum of the numbers written on them divisible by $d$.
Problem
Source: Moldova TST, day 2, problem B8
Tags: combinatorics
don2001
30.03.2016 05:51
Please give me some guidance. Thank you.
abk2015
30.03.2016 05:54
Wait, isn't $d$ dependant on $n$?
Snakes
31.03.2016 23:20
Yes, you're right @abk2015.
Try to prove that for some $n-k$ we have at least four different ways, but for a bigger number than this $n-k$ we can't find(just look for a counterexample) Also use this well-known lemma:
If we have $n$ numbers $a_{1},a_{2},a_{3}\cdots a_{n}$, we can also find a group of numbers from these such that their sum is divisible by $n$
proofLet us denote
$S_{1}=a_{1}$ ;
$S_{2}=a_{1}+a_{2}$ ;
$\cdots$
$S_{n}=\sum_{i=1}^{n} a_{i}$.
Now, if one of this sums is divisible by n, then we already have a group from $a_{1},a_{2},\cdots a{n}$ with the sum divisible by $n$. If none of them is, from the Pigeon hole principle we have at least two sums $S_{i}\equiv S_{j} (mod {n})$ so their difference(let $i$ be greater than $j$) is: $S_{i}-S_{j}=a_{j+1}+a_{j+2}+\cdots +a_{i}$ is a sum divisible by $n$. So we're done