HMMT 二月 2025 · 冲刺赛 · 第 19 题
HMMT February 2025 — Guts Round — Problem 19
题目详情
- [11] A subset S of { 1 , 2 , 3 , . . . , 2025 } is called balanced if for all elements a and b both in S , there exists an element c in S such that 2025 divides a + b − 2 c . Compute the number of nonempty balanced subsets.
解析
- [11] A subset S of { 1 , 2 , 3 , . . . , 2025 } is called balanced if for all elements a and b both in S , there exists an element c in S such that 2025 divides a + b − 2 c . Compute the number of nonempty balanced subsets. Proposed by: Jacob Paltrowitz Answer: 3751 a + b Solution: We work mod 2025, so the condition becomes that for any a , b ∈ S , we have ∈ S . 2 First, we prove that S must be an arithmetic sequence. Observe that if S is balanced, then so is the shift S + k = { s + k | s ∈ S } for all k , so we can assume 0 ∈ S . Let s be an element of S such that t 0+ t s d = gcd( s, 2025) is minimal. Observe that for any t ∈ S , we have = ∈ S . Thus, is in S for all n 2 2 2 n n . Because gcd(2 , 2025) = 1, this implies 2 s mod 2025 ∈ S for all n . We prove the following claim. Claim 1. For all positive integers m , we have ms ∈ S . Proof. We proceed with induction on the number of 1’s in the binary representation of m . Base Case: m has one 1 in binary, so m is a power of 2. Then ms ∈ S as noted above. Induction Step: Assume the claim holds for all m which have k 1’s in their binary representations. n Suppose m has k + 1 1’s in its binary representation. Let 2 be the largest power of 2 which is at most n n m . Then m − 2 has k 1’s in its binary representation, so 2( m − 2 ) does as well. By the induction n +1 n 2 s +2( m − 2 ) s n n +1 hypothesis, 2( m − 2 ) s ∈ S . Also, 2 s ∈ S , so ms = ∈ S , as desired. 2 It follows that every multiple of s is in S . The multiples of s are precisely the multiples of d , so S contains every multiple of d . Now assume for sake of contradiction that S contains some element t which is not a multiple of d , so we can write t = cd + r such that 0 < r < d . Then 2 t ∈ S , so 2 t +( − 2 c ) d r = ∈ S . But then gcd( r, 2025) ≤ r < d , contradicting the minimality of d . Thus S is 2 precisely the multiples of d . It can be verified that for any d | 2025, the set of multiples of d is balanced. Indeed, as d is odd, for ( a + b ) d any ad , bd ∈ S , their average is a multiple of d and hence also in S . Thus, any shift of such 2 a set is also balanced; as seen above, these classify all balanced sets. For each d | 2025, there are d P 5 3 3 − 1 5 − 1 choices for S , so the answer is d = · = 3751 . d | 2025 2 4