HMMT 二月 2021 · 冲刺赛 · 第 23 题
HMMT February 2021 — Guts Round — Problem 23
题目详情
- [14] Let f : N → N be a strictly increasing function such that f (1) = 1 and f (2 n ) f (2 n + 1) = 9 f ( n ) + 3 f ( n ) for all n ∈ N . Compute f (137). 3
解析
- [14] Let f : N → N be a strictly increasing function such that f (1) = 1 and f (2 n ) f (2 n + 1) = 2 9 f ( n ) + 3 f ( n ) for all n ∈ N . Compute f (137). Proposed by: Sheldon Kieren Tan Answer: 2215. Solution: Plugging in n = 1 gives f (2) f (3) = 12, therefore ( f (2) , f (3)) = (2 , 6) or (3 , 4). However, the former implies 2 f (4) f (5) ≥ (6 + 1)(6 + 2) > 42 = 9 · 2 + 3 · 2 , which is impossible; therefore f (2) = 3 and f (3) = 4. We now show by induction with step size 2 that f (2 n ) = 3 f ( n ) and f (2 n + 1) = 3 f ( n ) + 1 for all n ; the base case n = 1 has already been proven. Assume the statement is true for n < 2 k . Applying the given and the inductive hypothesis, we have f (4 k ) f (4 k + 1) = (3 f (2 k ))(3 f (2 k ) + 1) = (9 f ( k ))(9 f ( k ) + 1) f (4 k + 2) f (4 k + 3) = (3 f (2 k + 1))(3 f (2 k + 1) + 1) = (9 f ( k ) + 3)(9 f ( k ) + 4) √ Let x = f (4 k + 1). Since f is strictly increasing, this implies x ≥ f (4 k ) f (4 k + 1) > 9 f ( k ) and √ x ≤ f (4 k + 2) f (4 k + 3) − 1 < 9 f ( k ) + 3. So x = 9 f ( k ) + 1 or x = 9 f ( k ) + 2. Since 9 f ( k ) + 2 does not divide 9 f ( k )(9 f ( k ) + 1), we must have f (4 k + 1) = x = 9 f ( k ) + 1 and f (4 k ) = 9 f ( k ). A similar argument shows that f (4 k + 2) = 9 f ( k ) + 3 and f (4 k + 3) = 9 f ( k ) + 4, and this completes the inductive step. Now it is a straightforward induction to show that f is the function that takes a number’s binary digits 7 3 and treats it as base 3. Since 137 = 10001001 in binary, f (137) = 10001001 = 3 + 3 + 1 = 2215. 2 3 Remark: 137 = 2021 . 4 3