HMMT 二月 2014 · COMB 赛 · 第 6 题
HMMT February 2014 — COMB Round — Problem 6
题目详情
- We have a calculator with two buttons that displays an integer x . Pressing the first button replaces x x by b c , and pressing the second button replaces x by 4 x + 1. Initially, the calculator displays 0. 2 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, b y c denotes the greatest integer less than or equal to the real number y .)
解析
- We have a calculator with two buttons that displays an integer x . Pressing the first button replaces x x by ⌊ ⌋ , and pressing the second button replaces x by 4 x + 1. Initially, the calculator displays 0. 2 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 ⌋ 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 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 ′ 1 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 = 1535. Therefore, our problem reduces to finding the number of eleven-digit valid strings. Let F denote the number of valid strings of length n . For any valid string of length n , we n can 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 , with n 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