Kenneth Rosen Edition 7 Exercise 6.2 Question 12 (Page No. 405)

Question

How many ordered pairs of integers $(a, b)$ are needed to guarantee that there are two ordered pairs $(a_{1}, b_{1})\: \text{and}\: (a_{2}, b_{2})$ such that $a_{1} \mod 5 = a_{2} \mod 5\:\text{and}\: b_{1} \mod 5 = b_{2} \mod 5?$

Answer 1

Let us consider the set of all ordered pairs (a mod 5, b mod 5).

For any integer n, n mod 5 = 0, 1, 2, 3 or 4

So, a mod 5 can take on 5 values and b mod 5 can also take 5 values.

So, the total number of such ordered pairs possible is 5 * 5 = 25 As there are 25 such distinct pairs, the minimum number of pairs required to satisfy this condition ( a1mod5=a2mod5 and b1mod5=b2mod) by the pigeonhole principle is 25 + 1 = 26.

ans should be 26