Let $S$ be a subset of $\{0,1,2,\ldots,98 \}$ with exactly $m\geq 3$ (distinct) elements, such that for any $x,y\in S$ there exists $z\in S$ satisfying $x+y \equiv 2z \pmod{99}$. Determine all possible values of $m$.
Problem
Source: China ningbo ,13 Aug 2013
Tags: modular arithmetic, combinatorics proposed, combinatorics
14.08.2013 00:11
If $m \mid 99$ let $99=m \cdot d$ then $S=\{0, d, 2d, \ldots, (m-1)d\}$ satisfies since $u_1d+u_2d \equiv 2u_3d \pmod {md}$ is equivalent to $u_1+u_2 \equiv 2u_3 \pmod m$ which has always a solution $u_3$ in the set $\{0, 1, 2 \ldots, m-1\}$ for all $u_1$ and $u_2$ since $m$ is odd. Now we will show that if $m \nmid 99$ then the condition does not satisfy. Let $x_1, x_2, \ldots, x_m$ be the elements of the set $S$. Consider the sums $x_m+x_1, x_m+x_2, \ldots, x_m+x_{m-1}$ and let $x_m+x_1 \equiv 2y_1 \pmod {99}, \: x_m+x_2 \equiv 2y_2 \pmod {99}, \ldots,$ $x_m+x_{m-1} \equiv 2y_{m-1} \pmod {99}$. Since $x_i$'s are different modulo $99$, the numbers $y_i$'s are also different modulo $99$. On the other hand, none of $y_i$'s can be equivalent to $x_m$ modulo $99$ because otherwise we would have two equivalent terms. Hence $(y_1, y_2, \ldots, y_{m-1})$ is a permutation of $(x_1, x_2, \ldots, x_{m-1})$ and by adding up these equations we get $(m-1)x_m \equiv x_1+x_2+ \ldots+x_{m-1} \pmod {99}$ which means $mx_m \equiv x_1+x_2+\ldots+x_m \pmod {99}$. Now do the same procedure for all $x_i$'s to get $mx_1 \equiv mx_2 \equiv \ldots \equiv mx_m \pmod {99}$. Let $\gcd(m, 99)=d$ and $m=dm_1, \: 99=dk$. Then we have $x_1 \equiv x_2 \equiv \ldots \equiv x_m \pmod k$. So, we have $m$ many numbers equivalent to each other modulo $k$. However, we know that there are $d$ many numbers modulo $kd$ which are all equivalent to each other modulo $k$. Hence in order for $x_i$'s to be different modulo $99=kd$, we must have $m \leq d$ which means that $dm_1 \leq d$ and hence $m_1=1$. So $m=d \mid 99$ and we are done. Hence all possible $m$ values are $m=3, 9, 11, 33, 99$.
14.08.2013 01:02
Wait isn't this trivial by Lagrange? EDIT: Whoops, nevermind, I thought too fast, $ f(x,y)=50(x+y) $ isn't associative. Although perhaps some approach similar to the coset proof of Lagrange could work?