HMMT 二月 2026 · COMB 赛 · 第 9 题
HMMT February 2026 — COMB Round — Problem 9
题目详情
- Let A , A , A , . . . be a sequence of finite nonempty sets of positive integers. Given that | A ∩ A | = 1 2 3 i j gcd( i, j ) for all (not necessarily distinct) positive integers i and j , compute the minimum possible value of ∑ max A , d d | 250 where the sum ranges over all positive integer divisors d of 250 . (For a finite nonempty set S , we define max S as the largest element of S .)
解析
- Let A , A , A , . . . be a sequence of finite nonempty sets of positive integers. Given that | A ∩ A | = 1 2 3 i j gcd( i, j ) for all (not necessarily distinct) positive integers i and j , compute the minimum possible value of ∑ max A , d d | 250 where the sum ranges over all positive integer divisors d of 250 . (For a finite nonempty set S , we define max S as the largest element of S .) Proposed by: Jackson Dryg Answer: 499 Solution: First we characterize the sets A . i Set i = j to obtain | A | = i for all i . If i | j , then | A ∩ A | = i , so A ⊆ A . For any i, j , it is true that i i j i j A ∩ A = A . This is because A is a subset of both A and A , and | A | = gcd( i, j ) . i j gcd( i,j ) gcd( i,j ) i j gcd( i,j ) For all n , let B be the set of all elements of A that do not appear in A for any k ≤ n . By definition, n n k all B are disjoint. i ∪ Claim 1. For all positive integers n , A = B . n d d | n Proof. Note that B ⊆ A ⊆ A for all d | n . d d n By construction of the B , any element of A must be in some B with k ≤ n . It suffices to show that i n k if k ∤ n , then A ∩ B = ∅ . n k Note that A ∩ B ⊆ A ∩ A = A . If k ∤ n , gcd( n, k ) < k , so no element of A appears n k n k gcd( n,k ) gcd( n,k ) in B (by definition of B ). This implies A ∩ B = ∅ , as needed. k k n k Claim 2. We have | B | = φ ( n ) for all positive integers n , where φ is Euler’s totient function. n ∑ Proof. The first claim gives n = | A | = | B | . n d d | n ∑ It can be shown that f ( n ) = φ ( n ) is the unique function f satisfying f ( n ) = n (by induction, or d | n Mobius inversion). Given this characterization of the A , we’re ready to solve the main problem. The answer is 499 . i The construction is B = { 1 } , B = { 2 } , B = { 3 , 4 , 5 , 6 } , B = { 7 , 8 , 9 , 10 } , B = { 11 , . . . , 30 } , 1 2 5 10 25 B = { 31 , . . . , 50 } , B = { 51 , . . . , 150 } , B = { 151 , . . . , 250 } . 50 125 250 ∑ ∑ For the bound, note that max( A ) ≥ max( B ) . These B ’s have 250 elements in total; d d i d | n d | n clearly it is optimal to have them be the numbers 1 , 2 , . . . , 250 in some order. We have the following claim. Claim 3. Let S , S , . . . , S be disjoint sets of positive integers with sizes n ≤ n ≤ · · · ≤ n 1 2 k 1 2 k ∪ ∑ k k respectively, and let S = S . Then max( S ) is minimized when S contains the n smallest i k 1 1 i =1 i =1 elements of S , S contains the n next smallest elements of S , etc. 2 2 Proof. Induct on k , with the base case k = 1 being trivial. For the inductive step, suppose the claim is true for k − 1 ; we’ll show it’s true for k . Let the elements of S be a < a < · · · < a . Suppose the maximum of S is a , for m < n + n + · · · + n . 1 2 n + n + ··· + n k m 1 2 k 1 2 k Suppose also that a is the maximum of S . Take all elements greater than a in S , and n + n + ··· + n ℓ m ℓ 1 2 k swap them with elements in S . (This is possible because | S | > | S | . This swaps the maxima of S k k ℓ k and S , so this doesn’t change the sum.) ℓ Now that the maximum of S is a , swap S ’s elements with elements the other sets so that k n + n + ··· + n k 1 2 k S contains the n largest elements in S . These moves don’t change the maximum of S , and they can k k k ∑ k only increase the maxima of the other sets. So these moves do not increase the sum max( S ) . k i =1 Now apply the inductive hypothesis on S , S , . . . , S . 1 2 k − 1 ©2026 HMMT Because | B | < | B | < | B | < | B | < | B | < | B | < | B | < | B | , the claim gives that the sum is 1 2 5 10 25 50 125 250 minimized with the construction given above, so we are done.