2023 Chinese IMO National Team Selection Test

(1) When $m$ is large, we expect that the summation in (i) is very close to the following integral: $${\int }_0^m\left\{\frac{ax}{m}\right\}\left\{\frac{bx}{m}\right\}dx=m\cdot {\int }_0^1\{ax\}\{bx\}dx.$$ Hence, we will prove the inequality (i) for $$\lambda ={\int }_0^1\{ax\}\{bx\}dx,\beta =2(a+b).$$ To do this, we divide the summation and integral into several segments, and it suffices to prove that $$\begin{array}{rl}& \left|\sum _{k=1}^{m-1}\left\{\frac{ak}{m}\right\}\left\{\frac{bk}{m}\right\}-{\int }_0^m\left\{\frac{ax}{m}\right\}\left\{\frac{bx}{m}\right\}dx\right|\\ & =\left|\sum _{k=0}^{m-1}\frac{1}{2}\left(\left\{\frac{ak}{m}\right\}\left\{\frac{bk}{m}\right\}+\left\{\frac{a(k+1)}{m}\right\}\left\{\frac{b(k+1)}{m}\right\}\right)-{\int }_0^m\left\{\frac{ax}{m}\right\}\left\{\frac{bx}{m}\right\}dx\right|\\ & (ii)\le \sum _{k=0}^{m-1}\left|\frac{1}{2}\left(\left\{\frac{ak}{m}\right\}\left\{\frac{bk}{m}\right\}+\left\{\frac{a(k+1)}{m}\right\}\left\{\frac{b(k+1)}{m}\right\}\right)-{\int }_k^{k+1}\left\{\frac{ax}{m}\right\}\left\{\frac{bx}{m}\right\}dx\right|\end{array}$$ is less than or equal to $2(a+b)$. If $m\le a+b$, each term in (ii) is not greater than 1, so the total sum is not greater than $2a+2b$. We now assume $m>a+b$. For each $k$, we divide the discussion into two cases: (a) If there exists a $k$ such that $\{\frac{ak}{m}\}$ or $\{\frac{bk}{m}\}$ is discontinuous on $(k,k+1]$. There are at most $a+b-1$ such $k$. Moreover, since the product $\{\frac{ak}{m}\}\{\frac{bk}{m}\}$ always takes values in $[0,1]$, the contribution of each corresponding term in () is at most $a+b-1$. (b) If there exists a $k$ such that $\{\frac{ak}{m}\}$ or $\{\frac{bk}{m}\}$ is continuous on $(k,k+1]$. Let $x=k+\delta$ ($\delta \in [0,1]$), then $\{\frac{ak}{m}\}=\{\frac{bk}{m}\}+\frac{a\delta }{m}$ or $\{\frac{bk}{m}\}=\{\frac{ak}{m}\}+\frac{b\delta }{m}$. Let $\alpha =\{\frac{ak}{m}\}$ and $\beta =\{\frac{bk}{m}\}$.

The corresponding term in (ii) is then $$\begin{array}{rl}& \frac{1}{2}\left(\alpha \beta +(\alpha +\frac{a}{m})(\beta +\frac{b}{m})\right)-{\int }_0^1(\alpha +\frac{a\delta }{m})(\beta +\frac{b\delta }{m})d\delta \\ & =(\alpha \beta +\frac{a\beta }{2m}+\frac{b\alpha }{2m}+\frac{ab}{2m^2})-(\alpha \beta +\frac{a\beta }{2m}+\frac{b\alpha }{2m}+\frac{ab}{3m^2})=\frac{ab}{6m^2}.\end{array}$$ Combining the discussions in (a) and (b), we know that the summation in (ii) (when $m>a+b$) is less than or equal to $$a+b-1+m\cdot \frac{ab}{6m^2}<2(a+b)-1.$$ This completes the proof of (1).

(2) Step 1: A refined estimation of (1). We first calculate the value of $\lambda ={\int }_0^1\{ax\}\{bx\}dx$. Intuitively, this corresponds to integrating along the diagonal of the $a\times b$ grid, as shown in the left figure ($a=4,b=3$). Since the function inside the integral actually only depends on the small square where the diagonal lies, we can translate the diagonal to a small square, as shown in the middle figure (here, the small square is appropriately enlarged). However, this small square can also be divided into $ab$ rectangular blocks such that the path of integration exactly follows the diagonal, as shown in the right figure. This essentially corresponds to partitioning the integral ${\int }_0^1$ into integrals from $\frac{i}{ab}$ to $\frac{i+1}{ab}$ ($0\le i\le ab-1$). Note that inside each small square, $\{ax\}$ and $\{bx\}$ are both continuous.



We calculate specifically: $$\begin{array}{rl}\lambda & ={\int }_0^1\{ax\}\{bx\}dx=\frac{1}{ab}\sum _{i=0}^{ab-1}{\int }_i^{i+1}\left\{\frac{x}{b}\right\}\left\{\frac{x}{a}\right\}dx\\ (iii)& =\frac{1}{ab}\sum _{i=0}^{ab-1}\left\{\frac{i+\frac{1}{2}}{b}\right\}\left\{\frac{i+\frac{1}{2}}{a}\right\}+\frac{1}{ab}\sum _{i=0}^{ab-1}{\int }_i^{i+1}\left(\left\{\frac{x}{b}\right\}\left\{\frac{x}{a}\right\}-\left\{\frac{i+\frac{1}{2}}{b}\right\}\left\{\frac{i+\frac{1}{2}}{a}\right\}\right)dx\end{array}$$ where each term on the right side of (iii) equals $$\begin{array}{rl}& {\int }_{-\frac{1}{2}}^{\frac{1}{2}}\left(\left\{\frac{i+\frac{1}{2}+x}{b}\right\}\left\{\frac{i+\frac{1}{2}+x}{a}\right\}-\left\{\frac{i+\frac{1}{2}}{b}\right\}\left\{\frac{i+\frac{1}{2}}{a}\right\}\right)dx\\ & ={\int }_{-\frac{1}{2}}^{\frac{1}{2}}\left(\left\{\frac{i+\frac{1}{2}}{b}\right\}\frac{x}{a}+\left\{\frac{i+\frac{1}{2}}{a}\right\}\frac{x}{b}+\frac{x^2}{ab}\right)dx\\ & =0+0+\frac{1}{3ab}\left({\left(\frac{1}{2}\right)}^3-{\left(-\frac{1}{2}\right)}^3\right)=\frac{1}{12ab}.\end{array}$$ Regarding the preceding summation in (iii), note that when $i$ takes values from $\{0,1,\dots ,ab-1\}$, the pairs of numbers $\left(\left\{\frac{i}{b}\right\},\left\{\frac{i}{a}\right\}\right)$ exactly cover all the points in the set $$\left\{0,\frac{1}{a},\dots ,\frac{a-1}{a}\right\}\times \left\{0,\frac{1}{b},\dots ,\frac{b-1}{b}\right\}.$$ From this, we know that $$\sum _{i=0}^{ab-1}\left\{\frac{i+\frac{1}{2}}{b}\right\}\left\{\frac{i+\frac{1}{2}}{a}\right\}=\sum _{j=0}^{a-1}\sum _{k=0}^{b-1}\left\{\frac{k+\frac{1}{2}}{b}\right\}\left\{\frac{j+\frac{1}{2}}{a}\right\}=\frac{a}{2}\cdot \frac{b}{2}=\frac{ab}{4}.$$ Combining the above results, we obtain $$\lambda =\frac{1}{ab}\cdot \frac{ab}{4}+\frac{1}{ab}\cdot ab\cdot \frac{1}{12ab}=\frac{1}{4}+\frac{1}{12ab}.$$ That is, $$\left|\sum _{k=1}^{m-1}\left\{\frac{ak}{m}\right\}\left\{\frac{bk}{m}\right\}-\left(\frac{m}{4}+\frac{m}{12ab}\right)\right|\le 2|a|+2|b|-1.$$ Note that when $m$ is coprime to both $a$ and $b$, since $\{\frac{ak}{m}\}+\{\frac{-ak}{m}\}=1$, the sum corresponding to $(a,b)$ and the sum corresponding to $(-a,b)$ add up to $\frac{m-1}{2}$. Therefore, the inequality holds when $a,b$ are taken as negative integers coprime to $m$. $$(\ast )\left|\sum _{k=1}^{m-1}\left\{\frac{ak}{m}\right\}\left\{\frac{bk}{m}\right\}-\left(\frac{m}{4}+\frac{m}{12ab}\right)\right|\le 2|a|+2|b|.$$

Step 2: Transform the problem into a summation similar to (1). Let $p$ be a sufficiently large prime number (e.g., $p>10^{15}$). The congruence symbol $\equiv$ used below denotes congruence modulo $p$. Let $a,b$, and $c$ represent $a_1,a_2$, and $a_3$ respectively, and let $a_4$ be chosen such that $a_1+a_2+a_3+a_4\equiv 0$. For $k\in \{1,2,\dots ,p-1\}$, let $$h_k=\left\{\frac{a_{1}k}{p}\right\}+\left\{\frac{a_{2}k}{p}\right\}+\left\{\frac{a_{3}k}{p}\right\}+\left\{\frac{a_{4}k}{p}\right\},$$ It is easy to see that $h_k$ is an integer and $0\le h_k<4$, i.e., $h_k\in \{0,1,2,3\}$. Moreover, $\{\frac{a_{1}k}{p}\}+\{\frac{a_{2}k}{p}\}+\{\frac{a_{3}k}{p}\}\le 1$ is equivalent to $h_k=0$ or 1. Let $L_0,L_1,L_2$, and $L_3$ be the number of occurrences of 0, 1, 2, and 3 respectively among $h_1,h_2,\dots ,h_{p-1}$. We need to prove that $L_0+L_1\ge \lfloor \frac{p}{12}\rfloor$.

If exactly $t$ out of $a_1,a_2,a_3,a_4$ are not multiples of $p$, then $h_{p-k}=t-h_k$. We have the following results: If $t=0$, then $L_0=p-1$. If $t=2$, then $L_1=p-1$. If $t=3$, then $L_1=L_2=\frac{p-1}{2}$. Without loss of generality, we assume that $a_1,a_2,a_3,a_4\ne 0$. In this case, $L_1=L_3$, and $L_1+L_2+L_3=p-1$. We can consider $\{\frac{ak}{p}\}$ as a random variable, and the estimation of $L_1$ will be related to the variance of the sum $h_k$. Specifically, we consider the sum of squares: $$\sum _{k=1}^{p-1}{h}_k^2=L_1+4L_2+9L_3=4(p-1)+2L_1,$$ On the other hand, $$H=\sum _{k=1}^{p-1}{h}_k^2=\sum _{k=1}^{p-1}\left(\sum _{i=1}^4\left\{\frac{a_{i}k}{p}\right\}\right)\left(\sum _{j=1}^4\left\{\frac{a_{j}k}{p}\right\}\right)=\sum _{i=1}^4\sum _{j=1}^4\left(\sum _{k=1}^{p-1}\left\{\frac{a_{i}k}{p}\right\}\left\{\frac{a_{j}k}{p}\right\}\right).$$ For any $a,b\ne 0$, let's define the function $f(a,b)={\sum }_{k=1}^{p-1}\left\{\frac{ak}{p}\right\}\left\{\frac{bk}{p}\right\}$. In particular, $$f(a_i,a_i)=f(1,1)=\frac{1^2+2^2+\cdots +(p-1{)}^2}{p^2}=\frac{p}{3}-\frac{1}{2}+\frac{1}{6p}.$$ Now, let's consider the sum of six terms $F={\sum }_{1\le i<j\le 4}f(a_i,a_j)$. Since $H=2F+4f(1,1)=4(p-1)+2L_1$, the desired inequality $L_1\ge \lfloor \frac{p}{12}\rfloor$ holds if we have $F\ge \frac{17}{12}p$.

Step 3:* Translating into estimates for $a_1,a_2,a_3,a_4$. We define an equivalence relation $(a,b)\sim (u,v)$ if there exists $r\ne 0$ such that $u\equiv ra$ and $v\equiv rb$. In this case, $$f(u,v)=\sum _{k=1}^{p-1}\left\{\frac{uk}{p}\right\}\left\{\frac{vk}{p}\right\}=\sum _{k=1}^{p-1}\left\{\frac{ark}{p}\right\}\left\{\frac{brk}{p}\right\}=\sum _{rk=1}^{p-1}\left\{\frac{a\cdot rk}{p}\right\}\left\{\frac{b\cdot rk}{p}\right\}=f(a,b).$$ Thus, the value of the function $f(a_i,a_j)$ depends only on the equivalence class of $(a_i,a_j)$. In particular, combining with the calculation in Step 1 (), we have $$(\ast \ast \ast )\left|f(a_i,a_j)-\left(\frac{p}{4}+p\frac{\gcd (a_i,a_j{)}^2}{12a_i{a}_j}\right)\right|\le 2\frac{|a_i|+|a_j|}{\gcd (a_i,a_j)}.$$ To obtain a more accurate estimation of the values of $f(a_i,a_j)$, we introduce additional considerations. For any $a,b\ne 0$, let $b^{-1}$ denote the modular inverse of $b$ modulo $p$. Consider the residues modulo $p$ of the set $0,a{b}^{-1},2\times a{b}^{-1},\dots ,\lfloor \sqrt{p}\rfloor \times a{b}^{-1}$. By the pigeonhole principle, there exist two residues whose difference is less than or equal to $\lfloor \sqrt{p}\rfloor$. Therefore, there exist $u,v\in \pm 1,\pm 2,\dots ,\pm \lfloor \sqrt{p}\rfloor$ such that $u\equiv v\times a{b}^{-1}$, i.e., $(u,v)\sim (a,b)$. (Here, we assume $u>0$, and we also assume that $u$ and $v$ are coprime; otherwise, we can replace them with $\frac{u}{(u,v)}$ and $\frac{v}{(u,v)}$.) For $(a_i,a_j)$, let $(u_{ij},v_{ij})$ be one of the pairs that satisfy the above condition. If there are multiple choices, we can select any of them, and let $g_{ij}=\frac{1}{u_{ij}{v}_{ij}}$. In this case, we have $$f(a_i,a_j)=f(u_{ij},v_{ij}),$$ and according to Equation (*), we have: $$\left|f(a_i,a_j)-\left(\frac{p}{4}+\frac{p}{12u_{ij}{v}_{ij}}\right)\right|<4\sqrt{p}.$$ Let $G={\sum }_{1\le i<j\le 4}{g}_{ij}={\sum }_{1\le i<j\le 4}\frac{1}{u_{ij}{v}_{ij}}$, and let $\delta =10^{-5}$. As long as (there exists a choice of $g_{ij}$) $G\ge -1+\delta$, we have $$F=\sum _{i<j}f(a_i,a_j)>\sum _{i<j}\left(\frac{p}{4}+\frac{p}{12u_{ij}{v}_{ij}}-4\sqrt{p}\right)=\frac{18+G}{12}\times p-24\sqrt{p}>\frac{17}{12}p.$$ The condition $p\nmid (a+b)(a+c)(b+c)$ ensures that in the set $a_1,a_2,a_3,a_4$, For each pair $(a_i,a_j)$, since $a_i+a_j\ne 0$, we know that $(u_{ij},v_{ij})\ne (1,-1)$, which implies $g_{ij}\ge -\frac{1}{2}$. We call a pair $(a,b)$ “good” if there exist $u,v\in \pm 1,\pm 2,\dots ,\pm 10$ such that $(a,b)\sim (u,v)$. In this case, if $(a_i,a_j)$ is not a good pair, then $g_{ij}=\frac{1}{u_{ij}{v}_{ij}}\ge -\frac{1}{11}$. If among the six pairs $(a_i,a_j)$, $1\le i<j\le 4$, there are either 0 or 1 good pairs, then $G\ge -\frac{1}{2}+5\times (-\frac{1}{11})=-\frac{21}{22}>-1+\delta$. Therefore, assuming there are at least two good pairs, we know that $a_1+a_2+a_3+a_4\equiv 0$ implies that the four numbers are in a (simple) proportion. For example: If $(a_1,a_2)\sim (u_1,v_1)$ and $(a_1,a_3)\sim (u_2,v_2)$, then the four numbers are proportional to $(u_1{u}_2,v_1{u}_2,v_2{u}_1,-u_1{u}_2-v_1{u}_2-v_2{u}_1)$. If $(a_1,a_2)\sim (u_1,v_1)$ and $(a_3,a_4)\sim (u_2,v_2)$, then the four numbers are proportional to $(u_1(u_2+v_2),v_1(u_2+v_2),-u_2(u_1+v_1),-v_2(u_1+v_1))$. In conclusion, there exists $z_1+z_2+z_3+z_4=0$ such that $(a_1,a_2,a_3,a_4)\sim (z_1,z_2,z_3,z_4)$ and $1\le |z_i|\le 300$, $z_i+z_j\ne 0$. In this case, we have $(a_i,a_j)\sim \left(\frac{z_i}{z_i{z}_j},\frac{z_j}{z_i{z}_j}\right)$, which allows us to choose $g_{i,j}=\frac{(z_i,z_j{)}^2}{z_i{z}_j}$. We still focus on the value of $G={\sum }_{i<j}{g}_{i,j}$, and there are two simple proportions satisfying $G=1$: The four numbers form the “Golden Ratio 1” of $(1:-2:-3:4)$. Let $a_1=p-1$, $a_2=2$, $a_3=3$, $a_4=p-4$. In this case, $h_k=1$ is equivalent to $\frac{2k}{p}+\frac{3k}{p}\le \frac{k}{p}$. Among the values $k\in 1,2,\dots ,p-1$, such $k$ satisfying $\frac{2}{3}p<k<\frac{3}{4}p$ are counted as $L_1=\lfloor \frac{3}{4}p\rfloor -\lfloor \frac{2}{3}p\rfloor \ge \lfloor \frac{p}{12}\rfloor$. The four numbers form the “Golden Ratio 2” of $(1:-3:-4:6)$. Let $a_1=p-1$, $a_2=3$, $a_3=4$, $a_4=p-6$. In this case, $h_k=1$ is equivalent to $\frac{3k}{p}+\frac{4k}{p}\le \frac{k}{p}$. Among the values $k\in 1,2,\dots ,p-1$, such $k$ satisfying $\frac{3}{4}p<k<\frac{5}{6}p$ are counted as $L_1=\lfloor \frac{5}{6}p\rfloor -\lfloor \frac{3}{4}p\rfloor \ge \lfloor \frac{p}{12}\rfloor$. Assuming $(a_1,a_2,a_3,a_4)\sim (z_1,z_2,z_3,z_4)$ does not correspond to the two golden ratios mentioned above, we will prove that $G\ge -1+\delta$. Let's consider the signs of $z_1,z_2,z_3,z_4$. If there are three positive and one negative (or three negative and one positive) numbers, without loss of generality, let $z_1,z_2,z_3>0$ and $z_4=-(z_1+z_2+z_3)$. In this case, among the six terms in $G={\sum }_{1\le i<j\le 4}g(z_i,z_j)$, there are three positive and three negative terms. Specifically, $g(z_i,z_4)=-\frac{(z_i,z_4{)}^2}{z_i|z_4|}\ge -\frac{z_i}{|z_4|}$ for $i=1,2,3$, and $g(z_1,z_2)\ge \frac{1}{z_1{z}_2}>\delta$. Therefore, $G>-1+\delta$. Assuming that $z_1,z_2,z_3,z_4$ consist of two positive and two negative numbers, let $z_1,z_4>0$ and $z_2,z_3<0$. If there exists $\frac{z_j}{z_i}=-2$, without loss of generality, let $z_1=u>0$, $z_2=-2u$. Let $z_3=-v<0$ and $z_4=u+v$ (where $u$ and $v$ are coprime). In this case, $$G=-\frac{1}{2}-\frac{1}{uv}+\frac{1}{u(u+v)}+\frac{(2,v{)}^2}{2uv}-\frac{(2,u+v{)}^2}{2u(u+v)}-\frac{1}{v(u+v)}$$ $$G\ge -\frac{1}{2}-\frac{1}{uv}+\frac{1}{u(u+v)}+\frac{1}{2uv}-\frac{4}{2u(u+v)}-\frac{1}{v(u+v)}=-\frac{1}{2}-\frac{3}{2uv}>-1+\delta .$$ The last step of the above derivation assumes that $(u,v)\ne (1,1),(2,1),(1,3),(3,1)$, which would lead to negations or the four numbers forming a golden ratio. Additionally, when $(u,v)=(1,2)$, we have $G=0$. In any case, we have $G>-1+\delta$. If there exists $\frac{z_j}{z_i}=-3$, without loss of generality, let $z_1=u>0$, $z_2=-3u$. Let $z_3=-v<0$ and $z_4=2u+v$ (where $u$ and $v$ are coprime). In this case, $$G=-\frac{1}{3}-\frac{1}{uv}+\frac{1}{u(2u+v)}+\frac{(3,v{)}^2}{3uv}-\frac{(3,2u+v{)}^2}{3u(2u+v)}-\frac{(2,v{)}^2}{v(2u+v)}$$ $$G\ge -\frac{1}{3}-\frac{1}{uv}+\frac{1}{u(2u+v)}+\frac{1}{3uv}-\frac{9}{3u(2u+v)}-\frac{4}{v(2u+v)}=-\frac{1}{3}-\frac{8}{3uv}>-1+\delta .$$ The last step of the above derivation assumes that $(u,v)\ne (1,1),(1,2),(1,4)$, which would lead to negations or the four numbers forming a golden ratio. Additionally, when $(u,v)=(2,1),(1,3),(3,1),(4,1)$, we have $G=-\frac{4}{5},\frac{2}{5},-\frac{2}{3},-\frac{2}{3}$ respectively. In any case, we have $G>-1+\delta$. If each $\frac{z_j}{z_i}\ne -2,-3$, then the four negative terms in $G$ are all greater than or equal to $-\frac{1}{4}$, and the two positive terms are both greater than $\delta$. Therefore, we still have $G>-1+\delta$. In conclusion, we have $L_1+L_0\ge \lfloor \frac{p}{12}\rfloor$, and thus the conclusion of the problem is established. $\square$