-1

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)

rohit_wason
  • 31

1 Answers1

3

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$. ■

rohit_wason
  • 31
  • 1
    It works just fine. Note, however, that the first paragraph is unnecessary. We can start with the $51$ "bins" $${0}, {1,99}, {2,98}, \ldots, {49,51}, {50}$$ and note the remainders of the $52$ numbers must land in these bins. By the pigeonhole principle, at least two remainders must land in the same bin, giving the same conclusion. – Brian Moehring Apr 27 '20 at 02:26
  • 1
    I’d make one small change. What’s important isn’t that one bin contains exactly two remainders, but rather that it contains two distinct remainders, since that’s what ensures that you have two remainders whose sum is $100$. That said, what you have is correct and clear. – Brian M. Scott Apr 27 '20 at 02:27