HMMT 二月 2019 · ALGNT 赛 · 第 4 题

HMMT February 2019 — ALGNT Round — Problem 4

Let N be the set of positive integers, and let f : N → N be a function satisfying • f (1) = 1; • for n ∈ N , f (2 n ) = 2 f ( n ) and f (2 n + 1) = 2 f ( n ) − 1. Determine the sum of all positive integer solutions to f ( x ) = 19 that do not exceed 2019.

解析

Let N be the set of positive integers, and let f : N → N be a function satisfying • f (1) = 1; • for n ∈ N , f (2 n ) = 2 f ( n ) and f (2 n + 1) = 2 f ( n ) − 1. Determine the sum of all positive integer solutions to f ( x ) = 19 that do not exceed 2019. Proposed by: Yuan Yao Answer: 1889 a a a a a a 0 1 k 0 1 k For n = 2 + 2 + · · · + 2 where a > a > · · · > a , we can show that f ( n ) = 2 − 2 − · · · − 2 = 0 1 k a +1 0 2 − n by induction: the base case f (1) = 1 clearly holds; for the inductive step, when n is even n n a a +1 0 0 we note that f ( n ) = 2 f ( ) = 2(2 − ) = 2 − n as desired, and when n is odd we also have 2 2 n − 1 n − 1 a a +1 0 0 f ( n ) = 2 f ( ) − 1 = 2(2 − ) − 1 = 2 − n , again as desired. 2 2 a a +1 0 0 Since 19 = f ( n ) ≤ 2 ≤ n , we have a ≥ 5 and n = 2 − 19 ≤ 2019 gives a ≤ 9. So the answer is 0 0 9 ∑ a +1 11 6 (2 − 19) = (2 − 2 ) − 19 · 5 = 1889. a =5