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 ka +1
2 − n by induction: the base case f (1) = 1 clearly holds; for the inductive step, when n is even 0
n na 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