HMMT 十一月 2019 · 冲刺赛 · 第 30 题
HMMT November 2019 — Guts Round — Problem 30
题目详情
- [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#
解析
英文解析
- [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.