Arrange arbitrarily $1,2,\ldots ,25$ on a circumference. We consider all $25$ sums obtained by adding $5$ consecutive numbers. If the number of distinct residues of those sums modulo $5$ is $d$ $(0\le d\le 5)$,find all possible values of $d$.
Problem
Source: Lithuania NMO 2010
Tags: combinatorics proposed, combinatorics
16.03.2012 17:07
Let those numbers be $a_i$, for $1\leq i\leq 25$. From now on, $a_{i+25}=a_i$. Let $s_i=a_i+a_{i+1}+a_{i+2}+a_{i+3}+a_{i+4}$. To get $d=1$, $a_i=i$ is a solution, because $s_i\equiv 0(\mod 5)$ for all $i$. To get $d=3$, use the previous solution but with $a_5=6$ and $a_6=5$. This only changes $s_1$, which is now 11, and $s_6$, which is now 39. All the values of $s_i$ are now 0, 1 or 4 modulo 5. To get $d=4$, use the previous solution but with $a_{10}=12$ and $a_{12}=10$. This only changes $s_6$, which is now 41; $s_7$, which is now 47, and $s_{11}$ and $s_12$, which are now both 3 modulo 5. All the values of $s_i$ are now 0, 1, 2 or 3 modulo 5. To get $d=5$, make $5|a_i$ for $1\leq i\leq 4$, and $a_i\equiv 1(\mod 5)$ for $5\leq i\leq 9$. Now $s_i\equiv i(\mod 5)$ for $1\leq i\leq 5$. Finally, we have to prove that $d$ can't be 2. Suppose that all the $s_i$ are $m$ or $n$ modulo 5, and that there is at least one of each of them. We can suppose wlog that $s_1\equiv s_2\equiv m(\mod 5)$ and $s_3\equiv n(\mod 5)$ (from the conditions, somewhere in the circle there must be three consecutive $s_i$ congruent with mmn or nnm, because 25 is odd). Now notice that $\sum\limits_{j=0}^{4}s_{i+5j}\equiv\sum\limits_{i=1}^{25}a_i\equiv 0(\mod 5)$. The sum of five terms, each congruent with $m$ or $n$ modulo 5, is a multiple of five, so all of them must have the same residue modulo 5. $s_{i+1}-s_{i}=a_{i+5}-a_i$. We can see then that $5|a_{i+5}-a_{i}$ if $i\equiv 1(\mod 5)$, and $a_1$, $a_6$, $a_{11}$, $a_{16}$ and $a_{21}$ all have the same residue modulo 5. We also see that $a_{i+5}-a_{i}\equiv n-m(\mod 5)$ if $i\equiv 2(\mod 5)$. $a_2$, $a_7$, $a_{12}$, $a_{17}$ and $a_{22}$ all have different residues modulo 5, and one of them has the same residue as $a_1$. We've found 6 numbers with the same residue modulo 5, which is impossible since the $a_i$ were the numbers from 1 to 25.
20.03.2012 16:01
Alvid wrote: $a_2$, $a_7$, $a_{12}$, $a_{17}$ and $a_{22}$ all have different residues modulo 5, and one of them has the same residue as $a_1$. We've found 6 numbers with the same residue modulo 5, which is impossible since the $a_i$ were the numbers from 1 to 25. From ${s_2}\not \equiv {s_3}(\bmod 5)$,we have ${a_{5k + 2}}\not \equiv {a_{5k + 7}}(\bmod 5)$ for all integer $k$, but we cannot say $a_2$, $a_7$, $a_{12}$, $a_{17}$ and $a_{22}$ all have different residues modulo 5.
21.03.2012 19:38
yunxiu wrote: From ${s_2}\not \equiv {s_3}(\bmod 5)$,we have ${a_{5k + 2}}\not \equiv {a_{5k + 7}}(\bmod 5)$ for all integer $k$, but we cannot say $a_2$, $a_7$, $a_{12}$, $a_{17}$ and $a_{22}$ all have different residues modulo 5. We have that $s_2\equiv s_7\equiv s_{12}\equiv s_{17}\equiv s_{22}\equiv m (\bmod 5)$ and $s_3\equiv s_8\equiv s_{13}\equiv s_{18}\equiv s_{23}\equiv n (\bmod 5)$. $n-m\equiv s_{5k+3}-s_{5k+2}\equiv a_{5k+7}-a_{5k+2} (\bmod 5)$, and therefore $a_{5k+2}\equiv a_2+k(n-m) (\bmod 5)$. 5 does not divide $n-m$, so these five numbers are different modulo 5.