Maths Olympiad Prep

Library / /29 of 39

Combinatorics Difficulty 6.0 AIME, harder Find the answer Italy

Problem:

Pierino's calculator has a display, which initially shows the number 00, and two keys: the key +1+1, which adds 11 to the number written on the display, and the key ×3\times 3, which multiplies the number written on the display by 33. If the +1+1 key is pressed twice in a row, the calculator explodes. If the calculator's display holds at most 55 digits, how many are the numbers that Pierino can obtain with a suitable sequence of key presses (without making the calculator explode)?

Pick one

Solution

Solution:

The answer is (A). The numbers that can be obtained with a suitable sequence of keys +1+1 and ×3\times 3 without two consecutive +1+1's are all and only those that in base 33 are written with only digits 00 and 11. Indeed, given such a number, to obtain it on the calculator it suffices to scan from left to right the digits of its representation in base 33 and press +1+1 for the first 11, then ×3\times 3 every time a 00 is encountered, ×3\times 3 followed by +1+1 every time a 11 is encountered. In base 33, in fact, multiplying by 33 means shifting one position to the left. In this way, to each string of 00's and 11's in base 33 is associated a sequence of key presses that yields the corresponding number without making the calculator explode. The converse is also true: the sequences of keys involved are all and only those without two consecutive +1+1's, which would insert a 22 among the digits of the number. It remains only to count how many numbers with at most 55 digits in base 1010 are written in base 33 with only digits 00 and 11. We note that 311>1053^{11} > 10^{5} while 310+39++30=31112<1053^{10} + 3^{9} + \ldots + 3^{0} = \frac{3^{11} - 1}{2} < 10^{5}, so these are all and only those with at most 1111 digits in base 33. Since there are 22 choices (00 and 11) for each digit, such numbers are 211=20482^{11} = 2048. Note that in this way we have counted both the numbers with 1111 digits (with the first digit equal to 11), and those with fewer than 1111 digits (which correspond to those with 1111 digits but with a suitable number of leading zeros).

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.