What is the minimum number of ordered pairs of non-negative integers that…
2005
What is the minimum number of ordered pairs of non-negative integers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that a ≡ c (mod 3) and b ≡ d (mod 5)?
- A.
4
- B.
6
- C.
16
- D.
24
Attempted by 3 students.
Show answer & explanation
Correct answer: C
Answer: 16
Reason:
Look at the residues of the first coordinate modulo 3 and the second coordinate modulo 5.
There are 3 possible values for a mod 3 and 5 possible values for b mod 5, so 3 × 5 = 15 possible residue pairs (r, s).
By the pigeonhole principle, if you choose 16 ordered pairs then at least two of them must fall into the same residue pair, which means their first coordinates are congruent modulo 3 and their second coordinates are congruent modulo 5.
Thus the minimum number required is 15 + 1 = 16. Choosing only 15 could select one from each residue pair and avoid any repetition of both residues.