Given any $5$ integers, prove that you can pick two among them whose sum or difference is divisible by $6$. (You are not allowed to pick the same number twice.)
I'm trying to solve this problem using the pigeon hole principle.
When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" (remainders of those 5 integers after being divided by 6) as there are "pigeons" I'm not sure how to go about solving this.
Best Answer
HINT: If two of the numbers have the same remainder on division by $6$, their difference is divisible by $6$, so you can focus on the case in which all five integers have different remainders on division by $6$. Try to show that no matter which of the $6$ possible remainders is missing, you must have two numbers whose sum is a multiple of $6$.