Problem:
Six distinct positive integers are randomly chosen between and , inclusive. What is the probability that some pair of these integers has a difference that is a multiple of
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Place each of the integers in a pile based on the remainder when the integer is divided by . Since there are only piles but there are integers, at least one of the piles must contain two or more integers. The difference of two integers in the same pile is divisible by . Hence the probability is .
We have applied what is called the Pigeonhole Principle. This states that if you have more pigeons than boxes and you put each pigeon in a box, then at least one of the boxes must have more than one pigeon. In this problem the pigeons are integers and the boxes are piles.
The problems on this page are the property of the MAA's American Mathematics Competitions