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

HMMT February 2014 — Guts Round — Problem 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?

解析

[ 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). We first claim that each value of i corresponds to exactly one 2014-tuple ( f (1) , . . . , f (2014)). To prove this, note that f (1024) = 11, so each i uniquely determines the values of f (1007) , . . . , f (2014). Then all of f (1) , . . . , f (1006) can be uniquely determined from these values because for any 1 ≤ k ≤ 1006, n there exists a unique n such that 1007 ≤ k · 2 ≤ 2014. It’s also clear that these values satisfy the condition 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 uniquely determined by f (1007) , . . . , f (2014), which yields some 1008 ≤ i ≤ 2014 where f ( i ) = f ( i − 1) + 1, so we actually have a bijection between possible values of i and 2014-tuples. Therefore, the total number of possible 2014-tuples is 1007.