HMMT 二月 2014 · 团队赛 · 第 10 题
HMMT February 2014 — Team Round — Problem 10
题目详情
- [ 40 ] Fix a positive real number c > 1 and positive integer n . Initially, a blackboard contains the n 1 numbers 1 , c, . . . , c . Every minute, Bob chooses two numbers a, b on the board and replaces them 2 with ca + c b . Prove that after n 1 minutes, the blackboard contains a single number no less than ✓ ◆ L n/L c 1 , 1 /L c 1 p 1+ 5 where = and L = 1 + log ( c ). 2 HMMT 2014 Saturday 22 February 2014 Team Organization Team Team ID#
解析
- [ 40 ] Fix a positive real number c > 1 and positive integer n . Initially, a blackboard contains the n − 1 numbers 1 , c, . . . , c . Every minute, Bob chooses two numbers a, b on the board and replaces them 2 with ca + c b . Prove that after n − 1 minutes, the blackboard contains a single number no less than ( ) L n/L c − 1 , 1 /L c − 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 these 2 sets A, B corresponding to a, b → ca + c b , we add 1 to all the weights of A , and 2 to all the weights ∑ n − 1 t i i of B ). Therefore, the final number takes the form c c for positive integer weights t , . . . , t 0 n − 1 i =0 ∑ n − 1 − t i satisfying φ = 1. i =0 M Let M = log ( c ) > 0 (so L = 1 + M ). Then c = φ , so by Holder’s inequality, φ ( ) ( ) ( ) 1 M L ( ) L n − 1 n − 1 n − 1 n/L ∑ ∑ ∑ c − 1 t i − t i − M t 1 /L i i i c c φ ≥ [ c ( cφ ) ] = , 1 /L c − 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 − t i choice c , c , . . . , c simply gives a relatively clean closed form). The invariant φ = 1 was ∑ − t i inspired 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 /L c − 1