6
$\begingroup$

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 (:

$\endgroup$
0

3 Answers 3

13
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ $50$ rather than $51$? (not that it makes a difference) $\endgroup$
    – Henry
    May 23 at 15:06
  • $\begingroup$ @Henry, yes I was actually considering writing 50 instead of 51. Advantage of 50 is that it is perhaps more suggestive of that and how and where the pigeon hole principle comes in, but 51 keeps the link to the original problem closer in sight, that is why I eventually opted for that $\endgroup$
    – Vincent
    May 24 at 8:20
  • $\begingroup$ The question says "any given $50$ positive integers" not $51$ $\endgroup$
    – Henry
    May 24 at 8:48
  • $\begingroup$ Wait, this is really weird. I was convinced the question said 51, but I see you are right now. $\endgroup$
    – Vincent
    May 24 at 10:59
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.