Question 5
Let $p$ be a prime number and let $a_1,a_2,\ldots,a_k$ be distinct integers chosen from $1,2,\ldots,p-1$. For $1\le i\le k$, let $r_i^{(n)}$ denote the remainder of $na_i$ upon division by $p$, so $0\le r_i^{(n)}\lt p$. Define
$$S=\{n:1\le n\le p-1,\ r_1^{(n)}\lt \cdots\lt r_k^{(n)}\}.$$
Show that $S$ has fewer than $\frac{2p}{k+1}$ elements.
$$S=\{n:1\le n\le p-1,\ r_1^{(n)}\lt \cdots\lt r_k^{(n)}\}.$$
Show that $S$ has fewer than $\frac{2p}{k+1}$ elements.