2024 CGMO

Proof. The minimal $\lambda$ is $\frac{2}{3}$.

First, we show $\lambda \ge \frac{2}{3}$. Consider $n=3$ with $a=b=1$. For $k=1,2$, we have: $$\left\{\frac{k}{3}\right\}+\left\{\frac{k}{3}\right\}=\frac{2k}{3}\ge \frac{2}{3},$$ thus $\lambda$ cannot be smaller than $\frac{2}{3}$.

Now we prove $\lambda \le \frac{2}{3}$. Let $n$ be a positive integer and $a$, $b$ positive integers with $n\nmid a+b$. We need to find $1\le k\le n-1$ satisfying the inequality.

Case 1: $n=2$. Without loss of generality, take $a=1$, $b=1$. For $k=1$: $$\left\{\frac{1}{2}\right\}+\left\{\frac{1}{2}\right\}=\frac{1}{2}<\frac{2}{3}.$$

Case 2: $n\ge 3$.

Subcase 2.1: $\text{gcd}(a,n)=d>1$. Let $k=\frac{n}{d}{k}^{\prime }$ where $1\le k^{\prime }\le d-1$. Then: $$\left\{\frac{ak}{n}\right\}+\left\{\frac{bk}{n}\right\}=\left\{\frac{b{k}^{\prime }}{d}\right\}.$$ Since $\left\{\frac{b{k}^{\prime }}{d}\right\}+\left\{\frac{b(d-k^{\prime })}{d}\right\}\in \{0,1\}$, taking $k^{\prime }=1$ or $d-1$ gives: $$\left\{\frac{b{k}^{\prime }}{d}\right\}\le \frac{1}{2}<\frac{2}{3}.$$

Subcase 2.2: $\text{gcd}(a,n)=1$. Let $t$ be such that $ta\equiv 1(\mathrm{mod}n)$. Replacing $a$ with $ta(\mathrm{mod}n)$ and $b$ with $tb(\mathrm{mod}n)$, we may assume $a=1$ and $1\le b\le n-2$. Let $e=1-\frac{1}{n}-\frac{b}{n}\ge \frac{1}{n}$.

When $e\ge \frac{1}{3}$: Take $k=1$: $$\left\{\frac{1}{n}\right\}+\left\{\frac{b}{n}\right\}=1-e\le \frac{2}{3}.$$

When $e<\frac{1}{3}$: Let $k$ be the smallest positive integer with $ke\ge \frac{1}{3}$. Then: $$k=\lfloor \frac{1}{3e}\rfloor \le \lfloor \frac{n}{3}\rfloor <\frac{n}{3}+1\le n-1.$$ Let $e=\frac{l}{n}$ where $l$ is integer and $3l<n$ (since $e<\frac{1}{3}$). We have: $$ke+\frac{k}{n}\le \frac{(n+3l-1)(l+1)}{3ln}\le \frac{2(l+1)}{3l+1}\le 1.$$

This implies: $$\left\{\frac{k}{n}\right\}+\left\{\frac{kb}{n}\right\}=1-ke\le \frac{2}{3}.$$