China-TST-B

Proof. Let the solutions to the congruence equation $kx \equiv y \pmod{p}$ in $S \times T$ be $(x_1, y_1), \dots, (x_n, y_n)$, where $n \ge 1 + \lambda s \ge 1$. Hence, we know that $S$ and $T$ are both non-empty, implying that $n \ge 2$. Since $T$ is contained in a complete residue system modulo $p$, we know that the $x_i$'s are distinct. Without loss of generality, let's assume $x_1 < x_2 < \dots < x_n$. Let $u_i = x_i - x_1$ and $v_i = y_i - y_1$. Then we have
$$ku_i \equiv v_i \pmod{p}, \quad 0 \le u_i \le s, \quad |v_i| \le t.$$
Let $a = \frac{u_2}{\gcd(u_2, v_2)}$ and $b = \frac{v_2}{\gcd(u_2, v_2)}$. Thus, $\gcd(a, b) = 1$, and we have
$$0 < a \le s, \quad |b| \le t, \quad ka \equiv b \pmod{p}.$$
Combining with $ku_i \equiv v_i \pmod{p}$, we obtain
$$bu_i \equiv kau_i \equiv av_i \pmod{p}.$$
Let $bu_i = av_i + pw_i$. Then we have
$$|w_i| \le \frac{|b|s + at}{p}.$$
Let $L = \frac{|b|s + at}{p}$.

(1) If $L < 1$, then $w_i = 0$ for all $i$, and hence $bu_i = av_i$. Since $\gcd(a, b) = 1$, it follows that $u_i$ must be multiples of $a$. Combining with the fact that $u_i \in [0, s]$ are distinct non-negative integers, we have
$$s \ge \max u_i \ge a(n-1) \ge a\lambda s,$$
which implies $a \le \frac{1}{\lambda}$. Furthermore, from
$$at \ge \max |av_i| = \max |bu_i| \ge |b| \cdot (a\lambda s),$$
we have $|b| \le \frac{t}{\lambda s}$.

(2) If $L \ge 1$, then $w_i$ can take at most $2L+1 \le 3L$ integer values in the range $[-L, L]$. By the pigeonhole principle, at least $\frac{n}{3L}$ of the $w_i$'s take the same value. Let $E$ be the set of indices $i$ where $w_i$ takes the same value, and let $u_{i_0}$ be the smallest value in $\{u_i : i \in E\}$. From
$$b(u_i - u_{i_0}) = a(v_i - v_{i_0}) + p(w_i - w_{i_0}) = a(v_i - v_{i_0}), \quad \forall i \in E,$$
we obtain $a \mid u_i - u_{i_0}$. Combining $0 \le u_i - u_{i_0} = x_i - x_{i_0} \le s$, we have
$$s \ge \max_{i \in E} (u_i - u_{i_0}) \ge a(|E| - 1).$$
Also, from $|v_i - v_{i_0}| = |y_i - y_{i_0}| \le t$, we have
$$at \ge \max (a|v_i - v_{i_0}|) = |b| \max_{i \in E} (u_i - u_{i_0}) \ge |b|(a(|E| - 1)).$$
Note that
$$L = \frac{|b|s + at}{p} \le \frac{2st}{p} < \frac{\lambda s}{6},$$
which implies $1 < \frac{\lambda s}{6L}$. Thus, we have
$$|E| - 1 \ge \frac{\lambda s}{3L} - \frac{\lambda s}{6L} = \frac{\lambda s}{6L}.$$
Substituting back into the previous inequalities, we obtain
$$\lambda a \le 6L, \quad \lambda |b|s \le 6Lt,$$
which leads to
$$\lambda p = \frac{\lambda |b|s + \lambda at}{L} \le 12t,$$
contradicting the condition $t < \frac{\lambda p}{12}$!

Thus, we have shown that $L \ge 1$ is not possible, and only $L < 1$ holds true in this case. $\square$