AMC 10 Step by Step
Log inSign up
Printable

2006 AMC 10A Problem 20

Problem onlyBack to the problem
2006 AMC 10A Problem 20AMC 10 Step by Step
Name:                             Date: October 28, 2026
Modular Arithmetic · difficulty 3 of 5 · about 2 min · position P16-20

Six distinct positive integers are randomly chosen between 11 and 20062006 , inclusive. What is the probability that some pair of these integers has a difference that is a multiple of 55 ?

  1. A)12\frac{1}{2}
  2. B)35\frac{3}{5}
  3. C)23\frac{2}{3}
  4. D)45\frac{4}{5}
  5. E)11

Answer

E

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

  1. Rewrite the condition. Two numbers differ by a multiple of 55 exactly when they leave the same remainder when divided by 55. For example, 1717 and 3232 both leave remainder 22, and 32−17=1532 - 17 = 15.
  2. Count the remainders. Dividing by 55 can leave only 0,1,2,30, 1, 2, 3 or 44: five possible remainders.
  3. 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.
  4. Conclusion. Those two numbers have the same remainder, so their difference is a multiple of 55. This happens for every possible choice of six numbers, so the probability is 11.

The answer is (E) 1\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 11 to 20062006 does not matter at all; it is there to distract.

The trap

Starting a long probability calculation, or guessing a value like 4/5, instead of noticing that six numbers can never all have different remainders.

Concise solution

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

There are only five possible remainders: 0,1,2,3,40, 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 55.

This happens for every possible selection, regardless of the range 11 to 20062006, so the probability is 11.

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

Review in the AoPS books

Techniques

Pigeonhole principle