2006 AMC 10A Problem 20

P16-20~2 minPrint

Modular Arithmetic Basic Probability Pigeonhole principle

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 without answering

Key insight

Two numbers differ by a multiple of 5 exactly when they leave the same remainder when divided by 5. Six numbers but only five remainders, so it always happens.

Solution

Rewrite the condition. Two numbers differ by a multiple of $5$ exactly when they leave the same remainder when divided by $5$ . For example, $17$ and $32$ both leave remainder $2$ , and $32 - 17 = 15$ .
Count the remainders. Dividing by $5$ can leave only $0, 1, 2, 3$ or $4$ : five possible remainders.
Six numbers. Think of the five remainders as five boxes, and put each chosen number into the box of its remainder. Six numbers in five boxes means some box gets at least two numbers.
Conclusion. Those two numbers have the same remainder, so their difference is a multiple of $5$ . This happens for every possible choice of six numbers, so the probability is $1$ .

The answer is $\boxed{\textbf{(E)}\ 1}$ .

Why this works

This is the pigeonhole principle: put more objects than boxes, and some box must hold two. When a probability question has one more object than there are types, suspect that the event is certain. The range $1$ to $2006$ does not matter at all; it is there to distract.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Two integers differ by a multiple of $5$ exactly when they leave the same remainder upon division by $5$ .

There are only five possible remainders: $0, 1, 2, 3, 4$ . We are choosing six integers, so by the pigeonhole principle at least two of them land in the same remainder class. Those two have a difference divisible by $5$ .

This happens for every possible selection, regardless of the range $1$ to $2006$ , so the probability is $1$ .

The answer is $\boxed{\textbf{(E)}\ 1}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Intermediate Counting & Probability, Chapter 5: The Pigeonhole Principle
Introduction to Number Theory, Chapter 10: Units Digits