HMMT 二月 2026 · 团队赛 · 第 5 题
HMMT February 2026 — Team Round — Problem 5
题目详情
- [40] The numbers 1 , 2 , . . . , 2026 are written on a blackboard. An operation consists of replacing any number on the blackboard with the positive difference between the largest and smallest numbers currently on the blackboard. Determine, with proof, the least number of operations required to make all the numbers on the blackboard equal.
解析
- [40] The numbers 1 , 2 , . . . , 2026 are written on a blackboard. An operation consists of replacing any number on the blackboard with the positive difference between the largest and smallest numbers currently on the blackboard. Determine, with proof, the least number of operations required to make all the numbers on the blackboard equal. Proposed by: Srinivas Arun Answer: 3037 Solution: Let 2026 = 2 n . Lemma 1. The final number on the board is at most n . Proof. Suppose k is the final number. The numbers on the board before the last operation must be k, k, . . . , k, 2 k . Since the maximum of the numbers of the board can never increase, we have 2 k ≤ 2 n = ⇒ k ≤ n. Lemma 2. For any 0 ≤ k < 2 n , at least 2 n − k − 1 operations are required to make the difference between the largest and smallest numbers equal to k . Proof. Suppose the difference between the largest and smallest numbers is k . There are at most k + 1 distinct numbers on the board, so at least 2 n − k − 1 numbers were originally on the board and are no longer on the board. Hence, at least 2 n − k − 1 operations have been made. Lemma 3. At least 3 n − 2 operations are required to make all numbers on the blackboard equal. Proof. Suppose the final number is k . From the lemmas above, at least 2 n − k − 1 operations are needed before the difference becomes k , and so at most 1 number is k before this point. After this point, at least 2 n − 1 additional operations are required replace the other numbers and finish. Hence, the number of total operations is at least (2 n − k − 1) + (2 n − 1) = 4 n − k − 2 ≥ 3 n − 2 . Lemma 4. The upper bound of 3 n − 2 is achievable. Proof. We can repeatedly replace the smallest number on the board until the numbers are n, n + 1 , n + 1 , . . . , 2 n − 1 , 2 n − 1 , 2 n. Now, replace the remaining numbers with n , replacing 2 n last. This construction saturates all above inequalities and gives the 3 n − 2 bound. Hence, the answer is 3 n − 2 = 3037 . ©2026 HMMT