HMMT 二月 2014 · COMB 赛 · 第 6 题

英文解析

6. We have a calculator with two buttons that displays an integer x . Pressing the first button replacesxx by ⌊ ⌋ , and pressing the second button replaces x by 4 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 2
   presses? (It is permitted for the number displayed to exceed 2014 during the sequence. Here, ⌊ y ⌋
   denotes the greatest integer less than or equal to the real number y .)
   Answer: 233 We consider the integers from this process written in binary. The first operationtruncates 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
   ′
   1 s . Note that any number generated by this process is valid, as truncating the rightmost digit andappending 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 digitsis at most 10111111111 = 1535. Therefore, our problem reduces to finding the number of eleven-digitvalid strings. Let F denote the number of valid strings of length n . For any valid string of length n , wencan create a valid string of length n + 1 by appending a 0, or we can create a valid string of length n + 2
   by appending 01. This process is clearly reversible, so our recursion is given by F = F + F , withn n − 1 n − 2
   F = 2 , F = 3. This yields a sequence of Fibonacci numbers starting from 2, and some computation
   1 2
   shows that our answer is F = 233.
   11