HMMT 十一月 2017 · THM 赛 · 第 10 题
HMMT November 2017 — THM Round — Problem 10
题目详情
- D enote φ = and consider the set of all finite binary strings without leading zeroes. Each string S 2 3 2 has a “base- φ ” value p ( S ). For example, p (1101) = φ + φ + 1. For any positive integer n , let f ( n ) be 48 n f ( n +1) φ − 1 the number of such strings S that satisfy p ( S ) = . The sequence of fractions approaches 48 φ − 1 f ( n ) a real number c as n goes to infinity. Determine the value of c .
解析
- D enote φ = and consider the set of all finite binary strings without leading zeroes. Each string S 2 3 2 has a “base- φ ” value p ( S ). For example, p (1101) = φ + φ + 1. For any positive integer n , let f ( n ) be 48 n f ( n +1) φ − 1 the number of such strings S that satisfy p ( S ) = . The sequence of fractions approaches 48 φ − 1 f ( n ) a real number c as n goes to infinity. Determine the value of c . Proposed by: Ashwin Sah √ 25+3 69 Answer: 2 We write everything in base φ . Notice that 48 n φ − 1 = 10 . . . 010 . . . 01 . . . 10 . . . 01 , 48 φ − 1 where there are n − 1 blocks of 47 zeros each. We can prove that every valid base- φ representation comes from replacing a consecutive string 100 with a 011 repeatedly. Using this, we can easily classify what base- φ representations are counted by f ( n ). Notice that 10000000 = 01100000 = 01011000 = 01010110 and similar, so that in each block of zeros we can choose how many times to perform a replacement. It turns out that we can do anywhere from 0 to 24 such replacements, but that if we choose to do 24 then the next block cannot have chosen 0 replacements. (An analogy with lower numbers is 10001000 = 01101000 = 01100110 = 01011110, with the first block ”replaced twice,” which was only allowed since the second block had ”replaced once,” opening up the slot which was filled by the last 1 in the final replacement 011). n − 1 Thus we have a bijection from f ( n ) to sequences in { 0 , . . . , 24 } such that (a) the sequence does not end in 24 and (b) the sequence never has a 24 followed by a 0. We let a denote the number of length- n sequences starting with a 0, b for the number of such n n sequences starting with any of 1 to 23, and c for the number of such sequences starting with 24. We n know a = 1 , b = 23 , c = 0 and that f ( n ) = a + b + c . 1 1 0 n − 1 n − 1 n − 1 Now, a = a + b + c n n − 1 n − 1 n − 1 b = 23( a + b + c ) n n − 1 n − 1 n − 1 c = b + c n n − 1 n − 1 so b = 23 a for all n . Substituting gives a = 24 a + c , c = 23 a + c . Solving for n n n n − 1 n − 1 n n − 1 n − 1 c = a − 24 a and plugging in gives n n +1 n − 1 a − 24 a = a − a , n +1 n n n − 1 2 n which gives a characteristic polynomial of λ − 25 λ + 1 = 0. We easily find that a grows as λ (where n λ is the larger solution to the quadratic equation) and thus b , c do as well, implying that f ( n ) grows n n n as λ , where √ √ 2 25 + 25 − 4 25 + 3 69 λ = = , 2 2 which is our answer.