GATE CS 2005 Q44 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We can solve this problem using the Pigeonhole Principle.

We are looking for two chosen ordered pairs $(a, b)$ and $(c, d)$ such that:

This condition is equivalent to saying that the remainder of the first element modulo $3$ and the remainder of the second element modulo $5$ are identical for both pairs.

Let's define our "pigeonholes" based on the possible remainder pairs $(r_1, r_2)$ for any chosen pair $(x, y)$, where:

• $r_1 = x \bmod 3 \in \{0, 1, 2\}$ (3 possible values)
• $r_2 = y \bmod 5 \in \{0, 1, 2, 3, 4\}$ (5 possible values)

The total number of distinct remainder pairs (pigeonholes) is:

By the Pigeonhole Principle, if we choose $n$ ordered pairs (pigeons), we need $n > 15$ to guarantee that at least two pairs fall into the same remainder category (pigeonhole).

Thus, the minimum number of ordered pairs required is:

Therefore, the correct option is C.