Among $52$ distinct integers, prove that there exist two, such that their sum is divisible by $100$ or their difference is.

Question

This has been a head-scratcher for a few days, and I avoided looking it up. Here's what I came up with today (feedback appreciated)

Answer 1

The given integers $\{a_1,a_2,\dots,a_{52}\}$ produce remainders, $\{r_1, r_2, \dots, r_{52}\}$ upon division by $100$. If two of these remainders, $r_i,r_j$ are equal the difference of their corresponding integers $(a_i - a_j) \equiv (r_i-r_j) \equiv 0 \pmod {100}$ and the conjecture is proven.

If, on the other hand the sequence $\{r_i\}$ is distinct, we have $52$ distinct numbers in the range $R_{100}=\{0,1,2,\dots,99\}$. We define $49$ favorable 'bins' labeled with a pair of one smaller and one larger number $[1,99],[2,98],\dots,[49,51]$ such that the sum of these numbers is $100$. We assign each number from $\{r_i\}$ to exactly one of these 'bins' if $r_i$ equals the smaller number or the larger.

Eliminating two possible remainders, $(0,50)$ whose 'favorable' pairs are outside the range $R_{100}$ we're left with at least $50$ remainders that each belong to the $49$ 'bins'.

According to the pigeonhole principle, one 'bin' must hold at least $2$ such remainders. But since $\{r_i\}$ is distinct, this bin contains exactly $2$ remainders hence the sum of the two corresponding integers is a multiple of $100$. ■