2006 AMC 10A Problem 20

Six distinct positive integers are randomly chosen between

1

and

2006,

inclusive. What is the probability that some pair of these integers has a difference that is a multiple of

5?

Show solution

Solution

Group the integers by their remainder modulo

5.

There are only

5

possible remainders but

6

integers, so by the Pigeonhole Principle two share a remainder. Their difference is then a multiple of

5.

This always happens, so the probability is

1.

Thus, the correct answer is E.

Tagged: pigeonhole principle · modular arithmetic