For every positive integer $M \geq 2$, find the smallest real number $C_M$ such that for any integers $a_1, a_2,\ldots , a_{2023}$, there always exist some integer $1 \leq k < M$ such that \[\left\{\frac{ka_1}{M}\right\}+\left\{\frac{ka_2}{M}\right\}+\cdots+\left\{\frac{ka_{2023}}{M}\right\}\leq C_M.\]Here, $\{x\}$ is the unique number in the interval $[0, 1)$ such that $x - \{x\}$ is an integer. Proposed by usjl
Problem
Source: 2023 Taiwan Round 1 Mock Exam P6
Tags: Taiwan, algebra
19.03.2023 01:27
Hopefully this is at least close: Answer: $1011 + 1/M$ Construction: $(x, x, .... M-x, M-x, .. M-x)$ where $(M, x) = 1$ and there are 1011 of x. Bound: Define the sum when we plug in $x$ to be $F(x)$. It's easy to see that $E[F(x)] \leq 1011 + \frac{1}{2}$. Define P = $a_1 + a_2 + ... + a_{2023}$ and $(M, P) = N$. Now FTSOC $F(x) > 1011 + \frac{1}{M}$ for all $x$. Now notice that $F(x) + F(M-x) $ is an integer and by the assumption is at least 2023. Case 1. N=1 there exist such $x$ that the fractional part of $F(x)$ is $\frac{1}{M}$ hence for that $x$, $F(x) + F(M-x) \geq 2024$. And now we get that the average of all $F(x)$ is more that $1011 + \frac{1}{2}$ contradiction. Case 2. N > 1 There exist $x$ such that $F(x)$ is an integer. Hence $F(x) + F(M-x) \geq 2024$. Finish as in case 1.
19.03.2023 18:14
Cleaner way to get bound: Define $F(x)$ as previously. So $F(x) + F(M-x) \leq 2023$ for all $x$. Define $P = a_1 + a_2 + ... a_{2023}$ and $N = (M, P)$. Case 1. N = 1. Take x such that fractional part of $F(x)$ is $\frac{1}{M}$ then $F(x) + F(M-x) \geq (1012 + \frac{1}{M}) + (1011 + \frac{M-1}{M}) = 2024$ contradiction. Case 2. N > 1. Take such x that the fractional part of $F(x) $ is 0. Then $F(x) + F(M-x) \geq (1012) + (1012) = 2024$. Contradiction.
18.01.2024 13:12
You can also look at residues of the sum which are above average and residues which are below average. Over half of the residues would have to be above average for the bound not to work, but then some residue which is below average would have to be at least $M$ below average, which works.