Among $10$ random non-negative integers, there exist $2$ numbers whose sum or subtraction is multiple of $17$ So this is a middle school problem my niece asked; I could not really prove it after a couple of days:
Again: prove that among any $10$ non-negative integers, there exist two numbers, $a$ and $b$, such that either $a+b$ or $|a-b|$ is divisible by $17$.
My clue so far: if any two of them are the same, then obviously their subtraction is $0$, and therefore divisible by $17$. So we only need to look into the case where all the numbers are different.
 A: It suffices to show that among any $10$ distinct integers, there exists two numbers $a$ and $b$ such that $a^2-b^2$ is divisible by $17$.
Now, let's consider what are the value of $x^2 \pmod{17}$ can take .
$x \pmod{17}$ takes value $\{0,1,\ldots, 7,8, -8,-7,\ldots, -1\}.$
Hence $x^2 \pmod{17}$ takes value $\{0^2,1^2,\ldots,8^2\}$.
Notice that  $\{0^2,1^2,\ldots,8^2\}$ has cardinality $9$, hence by pigeonhole principle, if we pick $10$ elements, we can find two numbers, $a$ and $b$ such that $a^2-b^2 \equiv 0 \pmod{17}$.
A: Let $a_1,...,a_{10}$ be such numbers. Let us create the following sets : $\{0\},\{1,16\},\{2,15\},...,\{8,9\}$. 
You can see that there are nine such sets. If we assume that no two elements leave the same remainder $\mod 17$, then when we take the remainders, it will be some set of $10$ numbers between $0$ and $16$.
Since there are $10$ numbers, and $9$ sets above, at least two elements $a_i,a_j$ will have remainders in the same set above. However, you can clearly see that elements in the same set add to a multiple of $17$, so $a_i+a_j$ is a multiple of $17$.
Hence, it follows that either $a_i+a_j$ or $a_i-a_j$ is a multiple of $17$ for some $1 \leq i,j \leq 10$. 

Generalization : Given $n+1$ natural numbers $a_1,...,a_{n+1}$, two of these either have a sum or difference that is a multiple of $2n-1$. Similarly, given $n+2$ natural numbers $a_1,...,a_{n+2}$,  two of these either have a sum or difference that is a multiple of $2n$. 

A: Consider all of the numbers modulo $17$, since any number is equivalent to its remainder after division by $17$, as far as this problem is concerned.
Divide the numbers into groups based on whether their remainder is


*

*$0$

*$1$ or $16$

*$2$ or $15$

*$\cdots$

*$8$ or $9$


What happens when two numbers fall into the same group?  How many numbers must there be before this is guaranteed to happen?
