Let \(a_1, a_2, \ldots, a_n\) be integers such that \(a_1 > a_2 > \cdots > a_n > 1\). Let \(M = \operatorname{lcm} \left( a_1, a_2, \ldots, a_n \right)\). For any finite nonempty set $X$ of positive integers, define \[ f(X) = \min_{1 \leqslant i \leqslant n} \sum_{x \in X} \left\{ \frac{x}{a_i} \right\}. \]Such a set $X$ is called minimal if for every proper subset $Y$ of it, $f(Y) < f(X)$ always holds. Suppose $X$ is minimal and $f(X) \geqslant \frac{2}{a_n}$. Prove that \[ |X| \leqslant f(X) \cdot M. \]
Problem
Source: 2025 China Mathematical Olympiad Day 1 Problem 3
Tags: number theory
CeuAzul
27.11.2024 11:38
This is a very hard problem compared to the previous two
EthanWYX2009
27.11.2024 15:22
Definitely difficult problem by WB again, even than the previous year. When I was mocking I spent 2+ hour on this but can't even prove $n=2.$ I wonder if any national team members can solve this during contest.
JupiterZ
28.11.2024 12:06
EthanWYX2009 wrote: Definitely difficult problem by WB again, even than the previous year. When I was mocking I spent 2+ hour on this but can't even prove $n=2.$ I wonder if any national team members can solve this during contest. Maybe Leyan Deng can solve it, it is truely difficult, even more than any p3 in last 5 years in CMO
YaoAOPS
28.11.2024 19:06
Here's a proof for the much much weaker $f(X) \ge n$ or $|X| \ge nM$.
The complete solution has my claim but done a lot stronger (squeezing out a factor of two). It also exploits the condition of minimality a lot better by considering a subset $X \subset X'$ by removing one element each which gives a stronger bound by applying the claim to $X'$ instead of applying to $X$ then subtracting $n$.
This is trivial for $n = 1$ so suppose $n \ge 2$. Claim: For any $M \nmid x$, we have that \[ \sum_{i=1}^n \frac{x \pmod{a_i}}{a_i} \ge \frac{n + 1}{M} \]Proof: Fix $x = x_1m, m \mid M$. If $m = 1$ then $x \pmod{a_i} \ge 1$ for each $i$ so this can be verified. Now suppose $m > 1$. The bound is tightest when you have all $a_i$ which divide $m$, so this becomes \[ \sum_{i=1}^n \frac{\gcd(a_i, m)}{a_i} \ge \frac{n + d(m) - 1 + 1}{M} \]removing all $a_i$ larger. Then note that $\frac{\gcd(a_i, m)}{a_i} \ge \frac{1}{M}$ so the bound is tightest when there's exactly one term not divisible by $m$, say $a$. This this becomes \[ \frac{\gcd(a, m)}{a} \ge \frac{d(m)}{\text{lcm}(a, m)} + \frac{1}{M} \iff \frac{a(m - d(m))}{a \cdot lcm(a, m)} \ge \frac{1}{M}. \](This bound can be tightened a lot I think, which might lead closer to the solution) $\blacksquare$. As such, we get that \[ \sum_i \sum_{x \in X} \left\{ \frac{x}{a_i} \right\} \ge \frac{n+1}{M} \cdot |X| \]Note that by minimality we get that each $\sum_{x \in X} \left\{ \frac{x}{a_i} \right\}$ is within $1$ of each other. As such, we get that \[ nf(X) + n \ge \frac{n+1}{M} \cdot |X| \]which becomes the rearranged equality.
Steven.Sunwen
30.11.2024 13:17
It is said that only Leyan Deng solve it, among so many teams from different provinces.
Photaesthesia
01.12.2024 23:38
Steven.Sunwen wrote: It is said that only Leyan Deng solve it, among so many teams from different provinces. It is said that 6 students get the full score and the average score is 0.3 out of 21.
yobu
14.01.2025 14:43
Isn't there any solution? Is is possible to get the official solutions from somewhere? Even chinese is ok, I am really curious about this problem. BUMP!!
