Maths Olympiad Prep

Library / /421 of 520

Number theory Difficulty 3.8 AMC 10/12 Find the answer

The first 20072007 positive integers are each written in base 33. How many of these base-33 representations are palindromes? (A palindrome is a number that reads the same forward and backward.)

Pick one

Solution

200710=220210032007_{10} = 2202100_{3}
All numbers of six or less digits in base 3 have been written.
The form of each palindrome is as follows
1 digit - aa
2 digits - aaaa
3 digits - abaaba
4 digits - abbaabba
5 digits - abcbaabcba
6 digits - abccbaabccba
Where a,b,ca,b,c are base 3 digits
Since a0a \neq 0, this gives a total of 2+2+23+23+232+232=522 + 2 + 2\cdot 3 + 2\cdot 3 + 2\cdot 3^2 + 2\cdot 3^2 = 52 palindromes so far.
7 digits - abcdcbaabcdcba, but not all of the numbers are less than 220210032202100_{3}
Case: a=1a=1
All of these numbers are less than 220210032202100_3 giving 333^3 more palindromes
Case: a=2a=2, b2b\neq 2
All of these numbers are also small enough, giving 2322\cdot 3^2 more palindromes
Case: a=2a=2, b=2b=2
It follows that c=0c=0, since any other cc would make the value too large. This leaves the number as 220d0223220d022_3. Checking each value of d, all of the three are small enough, so that gives 33 more palindromes.
Summing our cases there are
52+33+232+3=100(A)52 + 3^3 + 2\cdot 3^2 + 3 = 100 \Rightarrow \mathrm{(A)}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.