HMMT 二月 2014 · 团队赛 · 第 10 题

英文解析

10. [ 40 ] Fix a positive real number c > 1 and positive integer n . Initially, a blackboard contains then − 1
    numbers 1 , c, . . . , c . Every minute, Bob chooses two numbers a, b on the board and replaces themwith ca + c b . Prove that after n − 1 minutes, the blackboard contains a single number no less than 2
    ( )
    n/LLc − 1
    ,
    1 /Lc − 1
    √
    1+ 5
    where φ = and L = 1 + log ( c ).
    2φ
    Answer: N/A By a simple reverse induction, we can show that at any instant, any number on
    ∑
    r ααthe board takes the form c c for a certain A ⊆ { 0 , . . . , n − 1 } for non-negative integer weightsα ∈ A
    ∑
    − rαr satisfying φ = 1, where these subsets A partition { 0 , . . . , n − 1 } , and after each minuteαα ∈ A − 1 − 2
    the number of parts decreases by 1 . (Note that 1 = φ + φ , and when we “merge” two of thesesets A, B corresponding to a, b → ca + c b , we add 1 to all the weights of A , and 2 to all the weights 2
    ∑
    n − 1
    t iiof B ). Therefore, the final number takes the form c c for positive integer weights t , . . . , t
    0 n − 1
    i =0
    ∑
    n − 1 − tisatisfying φ = 1.
    i =0
    Let M = log ( c ) > 0 (so L = 1 + M ). Then c = φ , so by Holder’s inequality,Mφ
    ( ) ( ) ( )
    1 M L
    ( )
    n − 1 n − 1 n − 1Ln/L
    ∑ ∑ ∑
    c − 1
    t i − t i − M t 1 /Li i ic c φ ≥ [ c ( cφ ) ] = ,
    1 /Lc − 1
    i =0 i =0 i =0
    as desired.
    Comment: Note that the same method applies for any choice of initial numbers x , x , . . . , x (the
    1 2 n
    ∑
    0 1 n − 1 − tichoice c , c , . . . , c simply gives a relatively clean closed form). The invariant φ = 1 was
    ∑
    − tiinspired by the corresponding invariant 2 = 1 for ISL 2007 A5, where the relevant operation is
    1 1 1 2
    { a, b } 7 → { c a + c b } (specifically, for c = 2, but this is not important) rather than { a, b } 7 → { c a + c b } .
    L 2 L L L
    Alternate solution: We have cx + c y ≥ ( x + y ) for any nonnegative reals x, y , since ( cx +
    2 L − 1 / ( L − 1) − 2 / ( L − 1) L − 1 L 1 / ( L − 1) 1 / log ( c )
    c y )( c + c ) ≥ ( x + y ) by Holder’s inequality, c = c = φ , and ofφ − 1 − 2
    course φ + φ = 1.
    ∑
    n − 1
    2 1 /L 1 /L 1 /L i 1 /L 1 /L
    In particular, ( ca + c b ) ≥ a + b . Thus ( c ) ≤ N , where N is the final (nonnegative)
    i =0
    n/L
    1 /L c − 1
    number on the board. Hence N ≥ .
    1 /Lc − 1