What is the minimum number of ordered pairs of non-negative integers that should be chosen to ensure that there are two ...

Question

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

Accepted Answer

Minimum 16 ordered pairs are needed to guarantee two with a ≡ c (mod 3) and b ≡ d (mod 5). Each ordered pair (a, b) of non-negative integers gets a 'label' (a mod 3, b mod 5). There are 3 choices for a mod 3 and 5 choices for b mod 5, giving 3*5 = 15 distinct labels. If we pick 16 pairs, by the pigeonhole principle two of them must share the same label, meaning a ≡ c (mod 3) and b ≡ d (mod 5) simultaneously.