AMC 10 · 2007 · #21

Grade 7 countingnumber-theory

Archetype Branching State Enumeration └ Sub-archetype Ordered Placement Count

base-conversiondigit-countingfundamental-counting-principle identify-subproblemscomplementary-counting ↑ Prerequisites: base-conversionfundamental-counting-principle

📏 Long solution 💡 4 insights

Problem

Every number up to a given ceiling is written in base three. Count how many of those strings read the same both ways.

Pick an answer.

(A)

100

(B)

101

(C)

102

(D)

103

(E)

104

How to solve

Strategy Identify Subproblems

The ceiling 2007 is written in base 10, which tells us nothing about base-3 digits, so Tool #15 (Organize Information in More Ways) says: rewrite the ceiling in base 3 first. It turns out to have 7 digits, which splits the job in two (Tool #7, Identify Subproblems). Strings of 6 digits or fewer are all far below the ceiling, so they need no checking at all — just counting, and a palindrome is completely determined by its front half, so Tool #2 (Make a Systematic List) counts each length in one multiplication. Only the 7-digit strings feel the ceiling. There are just 54 of them, and far fewer are too big than are small enough, so Tool #16 (Change Focus / Count the Complement) counts the ones to throw away instead. Comparing two 7-digit strings digit by digit is the one step that needs proof rather than assertion, and Tool #14 (Extreme Principle) supplies it: even the largest possible tail cannot make up for losing one unit at a higher place.

1STEP 1

Rewrite the ceiling in base 3

Rewriting the ceiling in the same base shows where it bites.

2007 = 2·3⁶ + 2·3⁵ + 0·3⁴ + 2·3³ + 1·3² + 0·3 + 0 = 2202100₃

2STEP 2

Split at seven digits

Shorter lengths fit entirely inside the range.

1 … 728_ ≤ 6 digits, all in range | 729 … 2007₇ digits, ceiling bites here

3STEP 3

Count palindromes by their front half

Counting by front halves gives 52 from those.

2 + 2 + 6 + 6 + 18 + 18 = 52

4STEP 4

Why digit-by-digit comparison is valid

Digit-by-digit comparison is valid because a full tail cannot carry.

2(3^k-1 + … + 3 + 1) = 3^k - 1 ＜ 3^k

5STEP 5

Throw away the seven-digit palindromes that are too big

Trimming the too-large longest ones leaves 48.

54 - 2 · 3_{a=b=2, c ∈ {1,2}} = 48

6STEP 6

Add the two blocks

Adding gives 100, choice (A).

52 + 48 = 100 → (A)

Answer

100

The five answer choices are 100 through 104, so this problem is built to punish a small miscount at the ceiling — which makes the boundary block the thing to double-check. The tightest case was a = b = 2, c = 0, d = 2, giving 2202022₃ = 2006. That is the largest palindrome in the whole range, and it lands exactly one below 2007: the boundary was neither cut short nor overrun. Dropping those three c = 0 palindromes by mistake would give 97, and keeping all 54 seven-digit palindromes would give 106; both miss the choice list entirely, which is a sign that the 6 excluded strings were exactly the right ones to exclude. It also does not matter whether the range is read as "up to 2007" or "below 2007", since 2007 = 2202100₃ ends in 0 and no palindrome can. A rough size check agrees too: palindromes of length L number about 2 · 3^L/2, so they thin out fast, and roughly 100 of them below 2187 is the right order of magnitude.

💡Key takeaway

A palindrome is just its front half written twice, so count front halves — and when a ceiling cuts through the longest block, it is usually faster to count the few strings that overshoot than the many that fit.

Rewrite the ceiling in base 3
Split at seven digits
Count palindromes by their front half
Why digit-by-digit comparison is valid
Throw away the seven-digit palindromes that are too big
Add the two blocks