Prove that $|S|< \frac{2p}{k+1}$ Given a prime number $p$. Let $a_1,a_2 \cdots a_k$ ($k \geq 3$) be integers not divisible by $p$ and having different residuals when divided by $p$. Let
$$ S= \{ 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$. How can one prove that $|S|< \frac{2p}{k+1}$?
 A: If anything is wrong or incomprehensible, feel free to comment. I'm a novice in english, so some sentence I make might have lots of grammar mistakes and fuzziness in reading it. I'll try to explain my thoughts as best as possible :D
First, we let $a_0 = 0$ and $a_{k+1} = p$, thus extending the sequence $\{a_i\}$.
We define $\{b_l\}_{l=0}^k$ to be $b_l = a_{l+1}- a_l$.
Note that for all $n \in S$,
$$\begin{align}
\sum_{l=0}^k (n b_l)_p = {} & (na_1)_p + \left((na_2)_p - (na_1)_p\right) + \\ 
{} & \cdots + \left( (na_k)_p - \left(na_{k-1} \right)_p \right) + \left(p - (na_k)_p\right) \\
= {} & p
\end{align}$$
Now we evaluate 
$$T = \sum_{n \in S}\sum_{l=0}^k (n b_l)_p$$
in two different ways. First way is to evaluate it straightforward using the formula above.
$$T = \sum_{n \in S}\sum_{l=0}^k (n b_l)_p = \sum_{n \in S} p = p |S|$$
Second way is the following. 
$$
\begin{align*}
T = & \sum_{n \in S}\sum_{l=0}^k (n b_l)_p = \sum_{l=0}^k\sum_{n \in S} (n b_l)_p \geq \sum_{l = 0}^k \sum_{m = 1}^{|S|} m = \frac{(k+1)|S|(|S|+1)}{2}
\end{align*}
$$
Note that the inequality holds because for every $0 \leq l \leq k$ and $n_1, n_2 \in S$, if $n_1 \neq n_2$, $n_1b_l \not\equiv n_2b_l \mod p$. Therefore every $(nb_l)_p$ are different from each other and are bigger than 0 for each $l$.
Combining the results, we get
$$p|S| = T \geq \frac{(k+1)|S|(|S|+1)}{2}$$ then $$\frac{2p}{k+1} \geq |S| + 1 >  |S|$$
