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
3 22
has a “base- φ ” value p ( S ). For example, p (1101) = φ + φ + 1. For any positive integer n , let f ( n ) be
48 nf ( n +1)
φ − 1
the number of such strings S that satisfy p ( S ) = . The sequence of fractions approachesφ − 1 f ( n )48
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
3 22
has a “base- φ ” value p ( S ). For example, p (1101) = φ + φ + 1. For any positive integer n , let f ( n ) be
48 nf ( n +1)
φ − 1
the number of such strings S that satisfy p ( S ) = . The sequence of fractions approachesφ − 1 f ( n )48
a real number c as n goes to infinity. Determine the value of c .
Proposed by: Ashwin Sah
√
25+3 69
Answer:
We write everything in base φ . Notice that 2
48 nφ − 1 = 10 . . . 010 . . . 01 . . . 10 . . . 01 ,
φ − 148
where there are n − 1 blocks of 47 zeros each. We can prove that every valid base- φ representationcomes from replacing a consecutive string 100 with a 011 repeatedly. Using this, we can easily classifywhat base- φ representations are counted by f ( n ).
Notice that 10000000 = 01100000 = 01011000 = 01010110 and similar, so that in each block of zeroswe 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 notend 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 suchn nsequences starting with any of 1 to 23, and c for the number of such sequences starting with 24. Wenknow 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 + cn n − 1 n − 1 n − 1
b = 23( a + b + c )
n n − 1 n − 1 n − 1
c = b + cn n − 1 n − 1
so b = 23 a for all n . Substituting gives a = 24 a + c , c = 23 a + c . Solving forn n n n − 1 n − 1 n n − 1 n − 1
c = a − 24 a and plugging in givesn n +1 n − 1
a − 24 a = a − a ,
n +1 n n n − 1
2 nwhich gives a characteristic polynomial of λ − 25 λ + 1 = 0. We easily find that a grows as λ (whereλ is the larger solution to the quadratic equation) and thus b , c do as well, implying that f ( n ) growsnn nas λ , wheren
√ √
25 + 25 − 4 25 + 3 692
λ = = ,
2 2
which is our answer.