返回题库

HMMT 二月 2019 · ALGNT 赛 · 第 4 题

HMMT February 2019 — ALGNT Round — Problem 4

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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.
解析

英文解析

  1. 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