HMMT 二月 2014 · 冲刺赛 · 第 17 题

英文解析

17. [ 11 ] Let f : N → N be a function satisfying the following conditions:
    (a) f (1) = 1.
    (b) f ( a ) ≤ f ( b ) whenever a and b are positive integers with a ≤ b .
    (c) f (2 a ) = f ( a ) + 1 for all positive integers a .
    How many possible values can the 2014-tuple ( f (1) , f (2) , ..., f (2014)) take?
    Answer: 1007 Note that f (2014) = f (1007)+1, so there must be exactly one index 1008 ≤ i ≤ 2014
    such that f ( i ) = f ( i − 1) + 1, and for all 1008 ≤ j ≤ 2014 , j 6 = i we must have f ( j ) = f ( j − 1). Wefirst claim that each value of i corresponds to exactly one 2014-tuple ( f (1) , . . . , f (2014)). To provethis, note that f (1024) = 11, so each i uniquely determines the values of f (1007) , . . . , f (2014). Thenall of f (1) , . . . , f (1006) can be uniquely determined from these values because for any 1 ≤ k ≤ 1006,
    there exists a unique n such that 1007 ≤ k · 2 ≤ 2014. It’s also clear that these values satisfy thencondition that f is nondecreasing, so we have a correspondence from each 1008 ≤ i ≤ 2014 to a unique
    2014-tuple.
    Also, given any valid 2014-tuple ( f (1) , . . . , f (2014)), we know that f (1) , . . . , f (1006) can be uniquelydetermined by f (1007) , . . . , f (2014), which yields some 1008 ≤ i ≤ 2014 where f ( i ) = f ( i − 1) + 1, sowe actually have a bijection between possible values of i and 2014-tuples. Therefore, the total numberof possible 2014-tuples is 1007.