CombinatoricsDifficulty 6.0AIME, harderFind the answerItaly
Problem:
Pierino's calculator has a display, which initially shows the number 0, and two keys: the key +1, which adds 1 to the number written on the display, and the key ×3, which multiplies the number written on the display by 3. If the +1 key is pressed twice in a row, the calculator explodes. If the calculator's display holds at most 5 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 and ×3 without two consecutive +1's are all and only those that in base 3 are written with only digits 0 and 1. 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 3 and press +1 for the first 1, then ×3 every time a 0 is encountered, ×3 followed by +1 every time a 1 is encountered. In base 3, in fact, multiplying by 3 means shifting one position to the left. In this way, to each string of 0's and 1's in base 3 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's, which would insert a 2 among the digits of the number. It remains only to count how many numbers with at most 5 digits in base 10 are written in base 3 with only digits 0 and 1. We note that 311>105 while 310+39+…+30=2311−1<105, so these are all and only those with at most 11 digits in base 3. Since there are 2 choices (0 and 1) for each digit, such numbers are 211=2048. Note that in this way we have counted both the numbers with 11 digits (with the first digit equal to 1), and those with fewer than 11 digits (which correspond to those with 11 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.