I have the following problem with me:
"Let $p$ be a prime, and let $a_1, \dots, a_p$ be integers. Show that there exists an integer $k$ such that the numbers $ [a_1 + k, a_2 + 2k, \dots, a_p + pk] $ produce at least $\tfrac{1}{2} p$ distinct remainders upon division by $p$."
I found a solution here :
https://artofproblemsolving.com/wiki/index.php?title=2018_USAMO_Problems/Problem_4
However the solution used graph theory which I haven't studied yet. Can anybody help me with a proof using modular arithmetic?
My try:
I tried the problem by taking small values, however the numbers I chose didn't seem to be arbitrary enough because $k=1$ itself was enough in all the case I chose. So along with the proof can anybody also help me to find a sequence for which k turns out to be more than 1?
Ok, so my line of thought -
First we note that we can take $k$ as $1\le k\le p\;\;(1)$
Now, if $a_i+ik\equiv a_j+jk\pmod p$, where $i\neq j$, then $k\equiv (a_j-a_i)(j-i)^{-1}\pmod p$. In particular, from $(1)$ it follows that such a $k$ is unique.
In total, there are $\binom p2$ such pairs.
The question states that we have to prove that there is a $k$ for which there are atleast $\frac p2$ different remainders modulo $p$, of the set $\{a_1+k,\ldots,a_p+pk\}$.
Suppose this is not true; that is, for all $k$, there are $\lt \frac p2$ different remainders. For $p\ge 3$, $\lt \frac p2$ is equivalent to $\le \frac{p-1}2$.
If we consider the table of $a_i+ik$ v/s $k$, then in each row (i.e., with fixed $k$), there are $\ge \frac{p+1}2$ of the set $\{a_1+k,\ldots,a_p+pk\}$ which give a remainder that is repeated; in particular, we have formed $\ge \frac{p+1}2$ pairs of numbers which have the same remainder.
Summing this over $k$ gives us that this is $\ge \frac{p(p+1)}2$. But we already showed that the number of such pairs is $\frac{p(p-1)}2$.
Thus we are done by contradiction.
For $p=2$ the proof is simple.