2024 CMO

Proof. Assume $f(X)=\lambda \ge \frac{2}{a_n}$. By contradiction, suppose $|X|>\lambda M$. Since $\lambda$ is of the form $\frac{k}{a_i}$ ($k\in {\mathbb{Z}}_{>0}$), $\lambda M$ is an integer. We prove that there exists $x\in X$ such that $f(X\setminus \{x\})=f(X)$, which contradicts the minimality of $X$.

For $1\le i\le n$, let $X_i=\{x\in X\mid a_i\nmid x\}$.

Consider all indices $i$ satisfying $|X_i|\le \lceil \lambda a_i\rceil$, and denote these indices by $i_1<i_2<\cdots <i_m$. If $$X_{i_1}\cup X_{i_2}\cup \cdots \cup X_{i_m}\ne X,(\ast )$$ take $x\in X\setminus (X_{i_1}\cup X_{i_2}\cup \cdots \cup X_{i_m})$, and let $Y=X\setminus \{x\}$. Then, $f(Y)=f(X)$.

This is because, letting $Y_i=\{y\in Y\mid a_i\nmid y\}$, we have: If $i\in \{i_1,i_2,\dots ,i_m\}$, then $X_i=Y_i$, and $$\sum _{y\in Y}\left\{\frac{y}{a_i}\right\}=\sum _{y\in Y_i}\left\{\frac{y}{a_i}\right\}=\sum _{x\in X_i}\left\{\frac{x}{a_i}\right\}=\sum _{x\in X}\left\{\frac{x}{a_i}\right\}\ge \lambda .$$ If $i\notin \{i_1,i_2,\dots ,i_m\}$, then $|Y_i|\ge |X_i|-1\ge \lceil \lambda a_i\rceil$, so $$\sum _{y\in Y}\left\{\frac{y}{a_i}\right\}=\sum _{y\in Y_i}\left\{\frac{y}{a_i}\right\}\ge |Y_i|\cdot \frac{1}{a_i}\ge \lceil \lambda a_i\rceil \cdot \frac{1}{a_i}\ge \lambda .$$ Thus, $f(Y)\ge \lambda$. Clearly, $f(Y)\le f(X)=\lambda$, so $f(Y)=f(X)$.

Now, we prove () holds. For $1\le j\le m$, let $T_j=X_{i_1}\cup \cdots \cup X_{i_j}$ and $M_j=\text{lcm}(a_{i_1},\dots ,a_{i_j})$. Clearly, $|T_j|=|X_{i_1}|\le \lceil \lambda a_{i_1}\rceil =\lceil \lambda M_1\rceil$.

For $2\le j\le m$, we have $|T_j\setminus T_{j-1}|\le \lceil \lambda M_j\rceil -\lceil \lambda M_{j-1}\rceil$. Indeed, if $M_j=M_{j-1}$, then $$T_j=\{x\in X\mid M_j\nmid x\}=\{x\in X\mid M_{j-1}\nmid x\}=T_{j-1},$$ so $|T_j\setminus T_{j-1}|=0=\lceil \lambda M_j\rceil -\lceil \lambda M_{j-1}\rceil$. If $M_j>M_{j-1}$, then $a_{i_j}\nmid M_{j-1}$, and let $d=\text{gcd}(a_{i_j},M_{j-1})$, $M_{j-1}=du$, $a_{i_j}=dv$, so $u$ and $v$ are coprime, with $u>v>1$, and $M_j=duv$. $$|T_j\setminus T_{j-1}|\le |X_{i_j}|\le \lceil \lambda a_{i_j}\rceil \le \lceil \lambda M_j\rceil -\lceil \lambda M_{j-1}\rceil .(\ast \ast )$$ The last inequality in ($\ast \ast$) requires $\lambda a_{i_j}\le \lambda M_j-\lambda M_{j-1}-1\iff \lambda d(uv-u-v)\ge 1$. Since $\lambda \ge \frac{2}{a_n}\ge \frac{2}{a_{i_j}}=\frac{2}{dv}$, it suffices to show $\frac{2}{v}(uv-u-v)\ge 1\iff (2u-3)(v-1)\ge 3$. Given $u>v>1$, this inequality holds, so ($\ast \ast$) holds. Therefore, $$|T_m|=|T_1|+\sum _{j=2}^m|T_j\setminus T_{j-1}|\le \lceil \lambda M_1\rceil +\sum _{j=2}^m(\lceil \lambda M_j\rceil -\lceil \lambda M_{j-1}\rceil )=\lceil \lambda M_m\rceil \le \lceil \lambda M\rceil =\lambda M.$$ This proves (), so the assumption by contradiction fails, and the original proposition is proved.