PUMaC 2023 · 数论（A 组） · 第 3 题
PUMaC 2023 — Number Theory (Division A) — Problem 3
题目详情
- Call an arrangement of n not necessarily distinct nonnegative integers in a circle wholesome when, for any subset of the integers such that no pair of them is adjacent in the circle, their average is an integer. Over all wholesome arrangements of n integers where at least two of them are distinct, let M ( n ) denote the smallest possible value for the maximum of the integers in the arrangement. What is the largest integer n < 2023 such that M ( n + 1) is strictly greater than M ( n )?
解析
- Call an arrangement of n not necessarily distinct nonnegative integers in a circle wholesome when, for any subset of the integers such that no pair of them is adjacent in the circle, their average is an integer. Over all wholesome arrangements of n integers where at least two of them are distinct, let M ( n ) denote the smallest possible value for the maximum of the integers in the arrangement. What is the largest integer n < 2023 such that M ( n + 1) is strictly greater than M ( n )? 1 Proposed by Austen Mazenko Answer: 2018 The idea is as follows: consider any k ≤ ⌊ ( n − 1) / 2 ⌋ not pairwise adjacent integers in a wholesome arrangement. By Pigeonhole, at least one of them can be replaced by one of its neighbors to get another subset such that no two are pairwise adjacent; this integer and its neighbor are thus equivalent modulo k , and by symmetry around the circle, this means that all of the intgers are congruent modulo k for all such k . If n is odd, this covers all possible integers; letting them all be 0 except for one which is lcm(1 , 2 , ..., ⌊ ( n − 1) / 2 ⌋ ) is therefore optimal, and M ( n ) equals this least common multiple in such cases. If n is even, we have to consider the two disjoint subsets consisting of n/ 2 of the integers with no two adjacent. In this case, their sum must be a multiple of n/ 2, but evidently generalizing the previous construction such that the integers in the circle are alternating with values 0 and lcm(1 , 2 , ..., ⌊ ( n − 1) / 2 ⌋ ) shows M (2 m ) = M (2 m − 1) (since M (2 m ) ≥ M (2 m − 1) obviously holds by just ignoring one of the extra integers, and we just showed equality is achievable). Now, M (2 m + 1) = M (2 m ) whenever lcm(1 , 2 , ..., m ) = lcm(1 , 2 , ..., m − 1). Thus the desired condition holds precisely when m ∤ lcm(1 , 2 , ..., m − 1), meaning m is a prime power. Specifically, we want to find the largest m such that 2 m < 2023 and m is a prime power. A quick check shows that m = 1009 is prime, so our answer is 2018.