返回题库

HMMT 十一月 2019 · 冲刺赛 · 第 30 题

HMMT November 2019 — Guts Round — Problem 30

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

题目详情

  1. [15] A function f : Z → Z satisfies: f (0) = 0 and
    ∣ ∣
    k k
    ∣ ∣
    f (( n + 1)2 ) − f ( n 2 ) ≤ 1
    for all integers k ≥ 0 and n . What is the maximum possible value of f (2019)?
    HMMT November 2019, November 9, 2019 — GUTS ROUND
    Organization Team Team ID#

英文原题

[15] A function f : Z → Z satisfies: f (0) = 0 and
∣
∣ f (( n + 1)2 k ) − f ( n 2 k ) ∣
∣ ≤ 1
for all integers k ≥ 0 and n . What is the maximum possible value of f (2019)?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HMMT November 2019, November 9, 2019 — GUTS ROUND
Organization Team Team ID#

解析

英文解析

  1. [15] A function f : Z → Z satisfies: f (0) = 0 and
    ∣ ∣
    k k
    ∣ ∣
    f (( n + 1)2 ) − f ( n 2 ) ≤ 1
    for all integers k ≥ 0 and n . What is the maximum possible value of f (2019)?
    Proposed by: Krit Boonsiriseth
    Answer: 4
    k k
    Consider a graph on Z with an edge between ( n + 1)2 and n 2 for all integers k ≥ 0 and n . Eachk kvertex m is given the value f ( m ). The inequality | f (( n + 1)2 ) − f ( n 2 ) | ≤ 1 means that any twoadjacent vertices of this graph must have values which differ by at most 1. Then it follows that for allm ,
    f ( m ) ≤ number of edges in shortest path from 0 to mbecause if we follow a path from 0 to m , along each edge the value increases by at most 1. Conversely,
    if we define f ( m ) to be the number of edges in the shortest path between 0 and m , then this is a validfunction because for any two adjacent vertices, the lengths of their respective shortest paths to 0 differby at most 1. Hence it suffices to compute the distance from 0 to 2019 in the graph.
    There exists a path with 4 edges, given by
    0 → 2048 → 2016 → 2018 → 2019 .
    Suppose there existed a path with three edges. In each step, the number changes by a power of 2, sok k k
    1 2 3
    we have 2019 = ± 2 ± 2 ± 2 for some nonnegative integers k , k , k and choice of signs. Since
    1 2 3
    0 k k
    1 2
    2019 is odd, we must have 2 somewhere. Then we have ± 2 ± 2 ∈ { 2018 , 2020 } . Without loss ofk k k
    2 1 2
    generality assume that k ≥ k . Then we can write this as ± 2 (2 ± 1) ∈ { 2018 , 2020 } . It is easy
    1 2
    k k k
    2 1 2
    to check that k = k is impossible, so the factorization 2 (2 ± 1) is a product of a power of two
    1 2
    and an odd number. Now compute 2018 = 2 × 1009 and 2020 = 4 × 505. Neither of the odd parts arek − k
    1 2
    of the form 2 ± 1, so there is no path of three steps.
    We conclude that the maximum value of f (2019) is 4.