Problem 1954

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'$ where $1 \le k' \le d - 1$. Then:
$$\left\{ \frac{ak}{n} \right\} + \left\{ \frac{bk}{n} \right\} = \left\{ \frac{bk'}{d} \right\}.$$
Since $\left\{ \frac{bk'}{d} \right\} + \left\{ \frac{b(d-k')}{d} \right\} \in \{0, 1\}$, taking $k' = 1$ or $d - 1$ gives:
$$\left\{ \frac{bk'}{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 \pmod{n}$. Replacing $a$ with $ta \pmod{n}$ and $b$ with $tb \pmod{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 = \left\lfloor \frac{1}{3e} \right\rfloor \le \left\lfloor \frac{n}{3} \right\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}.$$