Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 3 / e

Prove the stronger statement with a nonempty subset. Order the $n\ge 1$ integers as $a_1,\dots ,a_n$, and form the prefix sumsThere are $n+1$ such sums but only $n$ residue classes modulo $n$. The pigeonhole principle gives indices $0\le i<j\le n$ with $s_i\equiv s_j(\mathrm{mod}n)$. Their difference satisfiesThe selected elements form a nonempty subset of $S$, proving the claim. Neither positivity nor distinct values in a general ordered sequence are needed for the consecutive sum divisible by the sequence length argument; distinctness merely makes the present input a set.