CMO, 2024

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 < \dots < i_m$. If
$$X_{i_1} \cup X_{i_2} \cup \dots \cup X_{i_m} \neq X, \quad (*)$$
take $x \in X \setminus (X_{i_1} \cup X_{i_2} \cup \dots \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 \dots \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. \quad (**)$$
The last inequality in ($**$) requires $\lambda a_{i_j} \le \lambda M_j - \lambda M_{j-1} - 1 \Leftrightarrow \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 \Leftrightarrow (2u - 3)(v - 1) \ge 3$. Given $u > v > 1$, this inequality holds, so ($**$) 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.