Prove that a $46$-element set of integers contains two distinct doubletons $\{u, v\}$ and $\{x,y\}$ such that $u + v \equiv x + y$ (mod $2016$).
Problem
Source: RMM Shortlist 2016 C4
Tags: combinatorics, number theory, sets of integers
05.07.2019 23:12
Reduce each element of the set by modulo $2016$, and let them become $0\le t_1 \le t_2 \le \dots \le t_{46} \le 2015$. Let $t_{n+1}-t_n = x_n, \forall n \in \{ 1,2,\dots ,45 \}$. If there are $a \le b$ and $c \le d$, with $(a,b)\neq (c,d)$, satisfying $x_a + x_{a+1} + \dots x_b \equiv x_c + x_{c+1} + \dots + x_d \pmod {2016}$, then we are done because this means $t_{b+1}-t_a \equiv t_{d+1}-t_c \pmod {2016} \implies t_{b+1}+t_c \equiv t_{d+1}+t_a$. From now, assume all the consecutive sum of terms of $x_1, x_2, \dots, x_{45}$ are different. That means there are $\binom{45}{2}+45 = 1025$ different values among them. Let's put them into a set $X$. Now, consider the sets of the form $\{ i, 2016-i \}$: $\{0,0\}, \{1,2015\}$ $, \{2,2014\}, \dots \{1007,1009\},$ $\{1008,1008\}$. There are $1009$ such sets. By pigeonhole principle, there are one of the group whose elemets are attained at least twice by the elements of $X$. By our assumption, such set must not be $\{0,0\}$ or $\{1008, 1008\}$. So, there exist $i$ such that $\{ i, 2016-i \} = $ $\{ x_a+x_{a+1}+\dots +x_b, x_c+x_{c+1}+\dots +x_d \} =$ $ \{ t_{b+1}-t_a, t_{d+1}-t_c \}$ for some $a \le b,c \le d$. Summing each of them up gives us: \[2016 = t_{b+1}-t_a + t_{d+1}-t_c \implies t_{b+1} + t_{d+1} \equiv t_a + t_c \pmod {2016}.\]It can be checked that $\{b+1,d+1\} \neq \{a,c\}$. Again, we find the desired doubletons and we are done. $\blacksquare$ .