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: September 13, 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

Six integers but only five residues mod 5, so two must share a residue and their difference is a multiple of 5: the event is certain.

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}.

Why this works

When a "probability" problem asks about n+1n + 1 objects sorted into nn classes, suspect that the event is forced rather than random. Translating "difference is a multiple of 55" into "same residue mod 55" reveals the five classes; six objects cannot avoid a collision. The large number 20062006 is a distraction.

The trap

Launching into a probability computation (counting residue patterns or estimating 4/5) instead of noticing the event always happens.

Common mistakes

  • Launching into a probability computation (counting residue patterns or estimating 4/54/5) instead of noticing the event always happens.
  • Reading the problem as asking about five integers, where the probability really is less than 11 and requires work.

Techniques

Pigeonhole principle