China National Team Selection Test

Proof Clearly, if $n$ satisfies the required property, then $1 \le n \le p-1$. Denote all such $n$'s by $n_1 < n_2 < \cdots < n_k$; we shall show that $k \le 12 p^{\frac{2}{3}}$. If $k \le 12$ there is nothing to prove. In what follows, we assume that $k > 12$.

Rename $n_{i+1} - n_i$ ($1 \le i \le k-1$) in nondecreasing order as
$1 \le \mu_1 \le \mu_2 \le \cdots \le \mu_{k-1}$. It is clear that
$$\sum_{i=1}^{k-1} \mu_i = \sum_{i=1}^{k} (n_{i+1} - n_i) = n_k - n_1 < p. \quad \textcircled{1}$$
First, we show that for any $s \ge 1$,
$$| \{ 1 \le i \le k-1 : \mu_i = s \} | \le s, \qquad \textcircled{2}$$
i.e. there are at most $s$ $\mu_i$'s equal to $s$.
In fact, suppose that $n_{i+1} - n_i = s$; then $n_i! + 1 \equiv n_{i+1}! + 1 \equiv 0 \pmod{p}$, so $(p, n_i!) = 1$, and
$$(n_i + s)(n_i + s - 1)\cdots(n_i + 1) \equiv 1 \pmod p.$$
Thus, $n_i$ is a solution to the congruence equation
$$(x + s)(x + s - 1)\cdots(x + 1) \equiv 1 \pmod p.$$
Since $p$ is a prime number, there are at most $s$ solutions to the above equation, thanks to Lagrange's theorem. Thus, there are at most $s$ $n_i$'s with $n_{i+1} - n_i = s$, i.e. ② holds.

Now, we show that for any nonnegative integer $l$, if $\frac{l(l+1)}{2} + 1 \le k - 1$, then $\mu_{\frac{l(l+1)}{2}+1} \ge l + 1$. Suppose on the contrary that $\mu_{\frac{l(l+1)}{2}+1} \le l$. Then $\mu_1, \mu_2, \dots, \mu_{\frac{l(l+1)}{2}+1}$ are all positive integers between $1$ and $l$. By ②, there is at most one $\mu_i$ equal to $1$, at most two $\mu_i$'s equal to $2$, $\dots$, at most $l$ $\mu_i$'s equal to $l$, and thus there are at most $1+2+\dots+l = \frac{l(l+1)}{2}$ $\mu_i$'s less than or equal to $l$, which contradicts the assumption that $\mu_1, \mu_2, \dots, \mu_{\frac{l(l+1)}{2}+1}$ are all less than or equal to $l$.

Let $m$ be the largest positive integer with $\frac{m(m+1)}{2} + 1 \le k - 1$. Then
$$\frac{m(m+1)}{2} + 1 \le k - 1 < \frac{(m+1)(m+2)}{2} + 1, \quad \text{③}$$
and hence
$$\begin{aligned} \sum_{i=1}^{k-1} \mu_i &\ge \sum_{i=0}^{m-1} (i+1)^2 \\ &= \frac{m(m+1)(2m+1)}{6} > \frac{m^3}{3}. \end{aligned}$$
Since $k > 12$, $m \ge 4$, combining ① and ③ we get
$$\begin{aligned} k &< 2 + \frac{(m+1)(m+2)}{2} \\ &< 4m^2 + 4 \left( 3 \sum_{i=1}^{k-1} \mu_i \right)^{\frac{2}{3}} \\ &< 4 \times (3p)^{\frac{2}{3}}. \end{aligned}$$
This completes our proof.