返回题库

HMMT 十一月 2017 · THM 赛 · 第 10 题

HMMT November 2017 — THM Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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 .
解析

英文解析

  1. 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.