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 ∣ ∣ 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 . Each k k vertex m is given the value f ( m ). The inequality | f (( n + 1)2 ) − f ( n 2 ) | ≤ 1 means that any two adjacent vertices of this graph must have values which differ by at most 1. Then it follows that for all m , f ( m ) ≤ number of edges in shortest path from 0 to m because 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 valid function because for any two adjacent vertices, the lengths of their respective shortest paths to 0 differ by 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, so k 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 of k 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 are k − 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.