You are given a set of $m$ integers, all of which give distinct remainders modulo some integer $n$. Show that for any integer $k \le m$ you can split this set into $k$ nonempty groups so that the sums of elements in these groups are distinct modulo $n$. Proposed by Anton Trygub
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 8.8
Tags: number theory
07.04.2023 00:49
We will prove with induction on $m$ that for all positive integers $n$ and all sets with $m$ elements such that all of them are distinct modulo $n$, the following holds: for all $k \leq m$, we may split this set into $k$ nonempty subsets with distinct sums modulo $n$. For $m=1$, the assertion is vacuous. With the base case established, assume the assertion is true for $m$ and we will prove it for $m+1$. Assume the claim doesn't hold. Let $A$ be a set with $m+1$ elements, fix $k \leq m$ and let $a \in A$. We may split the remaining $m$ elements of $A$ in $k$ groups satisfying the condition. Let the remainders of these groups modulo $n$ be $a_1,\ldots,a_k$. Let $G$ be a directed graph such that its vertices are the remainders $a_i$ (so $G$ has $k$ vertices), and we draw an edge $a_i \rightarrow a_j$ if and only if $a_j \equiv a_i+a \pmod n$. If there is a vertex with no edge emanating from it, then if this vertex is $a_i$, we may add $a_1$ to the particular set and obtain a split of set $A$ in $k$ distinct sets modulo $n$. From now on, assume that at least one edge emanates from each vertex. If two edges emanate from the same vertex, say $a_i \rightarrow a_j$ and $a_i \rightarrow a_k$, then $a_j \equiv a_i+a \equiv a_k \pmod n,$ a contradiction. Therefore, ${\rm outdeg} \, v=1$ for all vertices $v$. In a similar manner, we may conclude that ${\rm indeg} \, v \leq 1$ for all vertices $v$. Therefore, it is easy to obtain that $G$ is a disjoint union of cycles (indeed, take a maximal directed path. Its last vertex has to point to exactly one vertex, and this vertex has to be the first vertex of the path. Delete this path and proceed inductively). Let $s_1,s_2,\ldots,s_t$ be the cycles' lengths. Then, if for example $a_1,\ldots,a_{s_1}$ belong to the cycle of length $s_1,$ $s_1a \equiv (a_2-a_1)+(a_3-a_2)+\ldots+(a_1-a_{s_1}) \equiv 0 \pmod n,$ and similarly $s_ia \equiv 0 \pmod n$ for all $i$. However, $s_1+\ldots+s_t=k,$ and so $n \mid ka$. Since we may repeat the above steps for all $a \in A,$ we conclude that $n \mid ka$ for all $a \in A$, or equivalently $\dfrac{n}{\gcd(n,k)} \mid a$ for all $a \in A$. Let set $B$ constitute of all elements of $A$ divided by $\dfrac{n}{\gcd(n,k)}$. Since the elements of $A$ are distinct modulo $n$, the elements of $B$ are distinct modulo $\gcd(n,k)$, and there are in total $m+1$, which is a contradiction, since $\gcd(n,k) \leq k<k+1 \leq m+1,$ and so by the Pigeonhole Principle some two of them must coincide modulo $n$. This contradiction proves the inductive step and subsequently the desired assertion, and so we are done.