1
$\begingroup$

Question:
How many ordered pairs of integers $(a, b)$ are needed to guarantee that there are two ordered pairs $(a_1, b_1)$ and $(a_2, b_2)$ such that $a_1 \bmod 5 = a_2 \bmod 5$ and $b_1 \bmod 5 = b_2 \bmod 5$?

This is my first time with pigeon hole principle and this is a book exercise without an answer key. Thus I need someone kindly to point out if anything is wrong with my proof and how to make it more straight forward next time.

My Attempt:
For each $a, b$ in $(a, b)$, there are 5 different congruence classes in $\mod 5$. To answer the question of How many ordered pairs of integers of the form $(a, b)$?, we need to consider 25 different congruence classes that both $a, b$ will form. Thus the problem is now reduced to pigeon hole problem,

$$\lceil \dfrac{n}{25}\rceil = 2$$

By solving the inequality of of the ceil function (I don't have to but just to be formal),

$$\lceil \dfrac{n}{25}\rceil-1 < \dfrac{n}{25} \leq \dfrac{n}{25}$$ $$2-1 < \dfrac{n}{25} \leq 2$$ $$25 < n \leq 50$$

Thus have to be $25+1 = 26$ by the Pigeon hole principle.

$\endgroup$
1
$\begingroup$

Yes, the answer is correct. There are $5$ options for the congruence of $a$ and $5$ options for the congruence of $b$ modulo $5$ so there are $25$ options for the congruence of the pair $(a,b)$. Clearly if you have $26$ then at least two will be in the same "congruence pair class". However with $25$ it could be we had one pair of each class, so the answer is 26 as you claim.

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