2018 USAMO Problems/Problem 4
Problem 4
Let be a prime, and let be integers. Show that there exists an integer such that the numbers produce at least distinct remainders upon division by .
Solution
For fixed where the statement holds for exactly one
Notice that the left side minus the right side is congruent to modulo For this difference to equal there is a unique solution for modulo given by where we have used the fact that every nonzero residue modulo has a unique multiplicative inverse. Therefore, there is exactly one that satisfies for any fixed
Suppose that you have graphs and graph consists of the vertices for all Within any graph vertices and are connected by an edge if and only if Notice that the number of disconnected components of any graph equals the number of distinct remainders when divided by given by the numbers
These graphs together have exactly one edge for every unordered pair of elements of so they have a total of exactly edges. Therefore, there exists at least one graph that has strictly fewer than edges, meaning that it has more than disconnected components. Therefore, the collection of numbers for this particular value of has at least distinct remainders modulo This completes the proof.
Solution 2
We consider the Lemma and it's proof as present in the above solution.
For every , let be the number of distinct residues that takes on. Further for each residue , let be the number of times it is achieved by an for . Note that
The number of pairs s.t for a given is, The first equality is given by a well known theorem, which can be proven by C-S or Jensen's.
Summing over all , the number of times a pair has is, Alternatively, every pair has a unique s.t by the Lemma so we double-count as, By AM-HM inequality, So it is clear that s.t .
~Aaryabhatta1