Given prime number $p$. $a_1,a_2 \cdots a_k$ ($k \geq 3$) are integers not divible by $p$ and have different residuals when divided by $p$. Let
\[ S_n= \{ n \mid 1 \leq n \leq p-1, (na_1)_p < \cdots < (na_k)_p \} \]
Here $(b)_p$ denotes the residual when integer $b$ is divided by $p$. Prove that $|S|< \frac{2p}{k+1}$.
.
Solution: Note that $\{ \frac{na_j}{p} \} < \{ \frac{na_{j+1}}{p}\} \iff \{ \frac{na_j}{p} \} + \{ \frac{n(a_{j+1}-a_j)}{p} \} = \{ \frac{na_{j+1}}{p}\}$
Therefore, if $x_1=a_1, x_j=a_j-a_{j-1}$ for $j=2,\cdots,k$ and $x_{k+1}=p-a_k$ then
$$\sum_{j=1}^{k+1} \{\frac{na_j}{p}\} = 1$$
Consider the sum $\sum_{s\in S} \sum_{j=1}^{k+1} \{\frac{sa_j}{p}\}$. On one hand it is equal to $|S|$. On the other hand, it is $\sum_{j=1}^{k+1} \sum_{s\in S} \{\frac{sa_j}{p}\} \ge (k+1) \frac{|S| (|S|+1)}{2p}$. Hence $|S|+1 \le \frac{2p}{k+1}$, as desired.