Existence Problem of pigeonhole, selecting among a set of 50 numbers.

Question

I have, a Problem related to the box (pigeonhole) principle. Let me show you the statement:

Prove that any given 50 positive integers, it is always possible to select out 4 numbers $a_{1}$, $a_{2}$, $a_{3}$, $a_{4}$ from them, such that $(a_{2} - a_{1}) \cdot ( a_{4} - a_{3} )$ is divisible by 2009.

To be honest, I'm kind of clueless in how to start to attack this problem, because, I'd usually start with "getting my hands dirty" and checking some cases to try to find a patter and the use box principle. But in this case the set of numbers is too big and to check even a single case would spend many many time, so it's obviously not the way to go.

There is though, a pretty similar problem of selecting 51 arbitrarily chosen number of a set from 100 numbers but again, the solution it's based on looking the fact that any single number can be rewritten as $2^{q} \cdot m$ ...

So, I believe the solution is just based on looking at a clever "pigeonhole" like in the above problem.

Would please anyone of you give me a hint? I don't really want a complete solution, just, a hint.

Thanks y'all for your time (:

Answer 1

Since $2009 = 41 \times 49$, it is sufficient to select out four numbers $a_1, a_2, a_3, a_4$ such that $a_1 \equiv a_2 \pmod{41}$ and $a_3 \equiv a_4 \pmod{49}.$ The pigeonhole principle guarantees the existence of such pairs $(a_1, a_2)$ and $(a_3, a_4)$ since there are $50$ distinct integers. You can formally prove this proposition by associating pigeons with given integers and holes with possible values modulo $49$ (and $41$). However, we should check the case in which these pairs share a common element. This case can be handled as follows: Select the pair $(a_3, a_4)$ first. Among the remaining $48$ integers, select the other pair.

Answer 2

A good way to start is by trying to prove the simpler result: when arbitrarily selecting 51 numbers there are always two among them (called $a_1, a_2$) so that $a_1 - a_2$ is divisible by 49.

Answer 3

Denote $r_i$ the remainder of the Euclidean division of $a_i$ by $49$. How many different values $r_i$ can take? How many $r_i$ are there? What can you conclude with the pigeonhole principle? Deduce that you can find $a_i$ and $a_j$ such that $49$ divides $a_j-a_i$ (or equivalently the remainder of $a_j-a_i$ by $49$ is $0$).

Why $49$? Because $2009=49\times41$.