Maths Olympiad Prep

Library / /713 of 860

Combinatorics Difficulty 5.4 AIME, harder Find the answer

We have a calculator with two buttons that displays an integer xx. Pressing the first button replaces xx by x2\left\lfloor\frac{x}{2}\right\rfloor, and pressing the second button replaces xx by 4x+14 x+1. Initially, the calculator displays 0. How many integers less than or equal to 2014 can be achieved through a sequence of arbitrary button presses? (It is permitted for the number displayed to exceed 2014 during the sequence. Here, y\lfloor y\rfloor denotes the greatest integer less than or equal to the real number yy.)

A number or a short expression. Spacing and $ signs are ignored.

Solution

We consider the integers from this process written in binary. The first operation truncates the rightmost digit, while the second operation appends 01 to the right. We cannot have a number with a substring 11. For simplicity, call a string valid if it has no consecutive 1s1^{\prime} s. Note that any number generated by this process is valid, as truncating the rightmost digit and appending 01 to the right of the digits clearly preserve validity. Since we can effectively append a zero by applying the second operation and then the first operation, we see that we can achieve all valid strings. Note that 2014 has eleven digits when written in binary, and any valid binary string with eleven digits is at most 10111111111=153510111111111=1535. Therefore, our problem reduces to finding the number of eleven-digit valid strings. Let FnF_{n} denote the number of valid strings of length nn. For any valid string of length nn, we can create a valid string of length n+1n+1 by appending a 0, or we can create a valid string of length n+2n+2 by appending 01. This process is clearly reversible, so our recursion is given by Fn=Fn1+Fn2F_{n}=F_{n-1}+F_{n-2}, with F1=2,F2=3F_{1}=2, F_{2}=3. This yields a sequence of Fibonacci numbers starting from 2, and some computation shows that our answer is F11=233F_{11}=233.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.