Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 3 / d

Assume $n\ge 1$ and list the elements of $X$ as $a_1,\dots ,a_n$. Define the partial sums $s_j=a_1+\cdots +a_j$ for $1\le j\le n$. If one is divisible by $n$, its corresponding nonempty prefix is a suitable $Y$.

Otherwise the $n$ partial sums have remainders in the $n-1$ nonzero residue classes. The pigeonhole principle gives $i<j$ with $s_i\equiv s_j(\mathrm{mod}n)$. Thus $s_j-s_i=a_{i+1}+\cdots +a_j$ is divisible by $n$, giving a nonempty subset $Y=\{a_{i+1},\dots ,a_j\}$.

Therefore a nonempty $Y$ exists. This strengthens the literal assertion, which would otherwise allow the trivial empty set with sum zero.