HMMT 二月 2022 · ALGNT 赛 · 第 5 题

HMMT February 2022 — ALGNT Round — Problem 5

Given a positive integer k , let ∥ k ∥ denote the absolute difference between k and the nearest perfect square. For example, ∥ 13 ∥ = 3 since the nearest perfect square to 13 is 16. Compute the smallest positive integer n such that ∥ 1 ∥ + ∥ 2 ∥ + · · · + ∥ n ∥ = 100 . n

解析

Given a positive integer k , let ∥ k ∥ denote the absolute difference between k and the nearest perfect square. For example, ∥ 13 ∥ = 3 since the nearest perfect square to 13 is 16. Compute the smallest positive integer n such that ∥ 1 ∥ + ∥ 2 ∥ + · · · + ∥ n ∥ = 100 . n Proposed by: Carl Schildkraut Answer: 89800 2 2 Solution: Note that from n = m to n = ( m + 1) , ∥ n ∥ increases from 0 to a peak of m (which is repeated twice), and then goes back down to 0. Therefore 2 m m − 1 m − 1 X X X k + 1 m + 1 m 2 ∥ n ∥ = 2(1 + 2 + · · · + k ) = 2 = 2 = ( m − 1) . 2 3 3 n =1 k =1 k =1 2 In particular, if n = m − 1, ∥ 1 ∥ + ∥ 2 ∥ + · · · + ∥ n ∥ m = , n 3 2 so n = 300 − 1 satisfies the condition. However, this does not prove that there are not smaller solutions for n . 2 Let N = 300 − 1 and suppose that N − k satisfies the condition. Then, we know that ∥ N ∥ + ∥ N − 1 ∥ + · · · ∥ N − ( k − 1) ∥ = 100 . k Since ∥ N − k ∥ = k + 1 for k ≤ 298, one can show that k = 199 works. By looking at further terms, one 2 can convince oneself that no larger value of k works. Thus, the answer is 300 − 1 − 199 = 90000 − 200 =