AMC 10 Step by Step

2010 AMC 10B Problem 21

P21-25~3 minPrint

A palindrome between 10001000 and 10,00010,000 is chosen at random. What is the probability that it is divisible by 77 ?

Log in to save your progress.
Show solution without answering

Key insight

A palindrome abba equals 1001a + 110b. 1001 is a multiple of 7, so only the middle digit b matters, and b must be 0 or 7.

Solution

A four-digit palindrome reads the same both ways, like 34433443. It has the form abbaabba: first digit aa from 11 to 99 and middle digit bb from 00 to 99. That makes 9⋅10=909 \cdot 10 = 90 palindromes.

1. Split by place value. Take 34433443:
3443=3000+400+40+3=3⋅1001+4⋅110.3443 = 3000 + 400 + 40 + 3 = 3 \cdot 1001 + 4 \cdot 110.
In the same way every palindrome abbaabba equals 1001a+110b1001a + 110b.
2. The first part is always a multiple of 77, because 1001=7⋅1431001 = 7 \cdot 143 (in fact 1001=7⋅11⋅131001 = 7 \cdot 11 \cdot 13).
3. So the palindrome is a multiple of 77 exactly when 110b110b is. Since 110=2⋅5⋅11110 = 2 \cdot 5 \cdot 11 has no factor of 77, the factor 77 must come from bb itself. So bb is a multiple of 77: b=0b = 0 or b=7b = 7.
4. For every first digit aa, 22 of the 1010 middle digits work. The probability is 210=15\frac{2}{10} = \frac15.

Check two examples: 1771=7⋅2531771 = 7 \cdot 253 and 3003=7⋅4293003 = 7 \cdot 429.

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

Why this works

Writing a number in terms of its digits (place value) shows which digits actually matter for a divisibility question. The fact 1001=7⋅11⋅131001 = 7 \cdot 11 \cdot 13 is worth memorizing: it is why every four-digit palindrome is a multiple of 1111, and why here only the middle digit decides divisibility by 77.

Concise solution

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

A four-digit palindrome has the form abba‾\overline{abba} with digits a∈{1,…,9}a \in \{1,\dots,9\} and b∈{0,…,9}b \in \{0,\dots,9\}, so there are 9090 of them. In terms of place value,
abba‾=1000a+100b+10b+a=1001a+110b.\overline{abba} = 1000a + 100b + 10b + a = 1001a + 110b.

Since 1001=7⋅11⋅131001 = 7 \cdot 11 \cdot 13, the term 1001a1001a is always a multiple of 77. So the palindrome is divisible by 77 exactly when 110b110b is. Because gcd⁡(110,7)=1\gcd(110, 7) = 1, this means 7∣b7 \mid b, i.e. b=0b = 0 or b=7b = 7.

For each of the 99 choices of aa, exactly 22 of the 1010 choices of bb work, so the probability is 210=15\frac{2}{10} = \frac15.

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

Review in the AoPS books

Similar problems

Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.