Maths Olympiad Prep

Library / /203 of 1394

Number theory Difficulty 4.9 AIME Find the answer United States

Problem:
A subset SS of {1,2,3,,2025}\{1,2,3,\ldots ,2025\} is called balanced if for all elements aa and bb both in SS, there exists an element cc in SS such that 20252025 divides a+b2ca + b - 2c. Compute the number of nonempty balanced subsets.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
We work mod 20252025, so the condition becomes that for any aa, bSb \in S, we have a+b2S\frac{a + b}{2} \in S.

First, we prove that SS must be an arithmetic sequence. Observe that if SS is balanced, then so is the shift S+k={s+ksS}S + k = \{s + k \mid s \in S\} for all kk, so we can assume 0S0 \in S. Let ss be an element of SS such that d=gcd(s,2025)d = \gcd (s, 2025) is minimal. Observe that for any tSt \in S, we have t2=0+t2S\frac{t}{2} = \frac{0 + t}{2} \in S. Thus, s2n\frac{s}{2^n} is in SS for all nn. Because gcd(2,2025)=1\gcd (2, 2025) = 1, this implies 2nsmod2025S2^n s \bmod 2025 \in S for all nn. We prove the following claim.

Claim 1. For all positive integers mm, we have msSms \in S.

Proof. We proceed with induction on the number of 1's in the binary representation of mm.

Base Case: mm has one 1 in binary, so mm is a power of 2. Then msSms \in S as noted above.

Induction Step: Assume the claim holds for all mm which have kk 1's in their binary representations. Suppose mm has k+1k + 1 1's in its binary representation. Let 2n2^{n} be the largest power of 2 which is at most mm. Then m2nm - 2^{n} has kk 1's in its binary representation, so 2(m2n)2(m - 2^{n}) does as well. By the induction hypothesis, 2(m2n)sS2(m - 2^{n})s \in S. Also, 2n+1sS2^{n + 1}s \in S, so
ms=2n+1s+2(m2n)s2S, m s = \frac{2^{n + 1}s + 2(m - 2^{n})s}{2} \in S,
as desired. \square

It follows that every multiple of ss is in SS. The multiples of ss are precisely the multiples of dd, so SS contains every multiple of dd. Now assume for sake of contradiction that SS contains some element tt which is not a multiple of dd, so we can write t=cd+rt = cd + r such that 0<r<d0 < r < d. Then 2tS2t \in S, so
r=2t+(2c)d2S. r = \frac{2t + (- 2c)d}{2} \in S.
But then gcd(r,2025)r<d\gcd (r, 2025) \leq r < d, contradicting the minimality of dd. Thus SS is precisely the multiples of dd.

It can be verified that for any d2025d \mid 2025, the set of multiples of dd is balanced. Indeed, as dd is odd, for any adad, bdSbd \in S, their average (a+b)d2\frac{(a + b)d}{2} is a multiple of dd and hence also in SS. Thus, any shift of such a set is also balanced; as seen above, these classify all balanced sets. For each d2025d \mid 2025, there are dd choices for SS, so the answer is
d2025d=35125314=37512. \sum_{d \mid 2025} d = \frac{3^5 - 1}{2} \cdot \frac{5^3 - 1}{4} = \left\lceil \frac{3751}{2} \right\rceil.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.