Problem: Let $p$ be a prime, and let $a_1$, \dots, $a_p$ be integers.
Show that there exists an integer $k$ such that the numbers
\[ a_1 + k, \; a_2 + 2k, \; \dots, \; a_p + pk \]
produce at least $\half p$ distinct remainders upon division by $p$.

Solution: For each $k = 0, \dots, p-1$ let $G_k$ be the graph
on $\{1, \dots, p\}$ where we join $\{i,j\}$ if and only if
\[ a_i + ik \equiv a_j + jk \pmod p
  \iff k \equiv - \frac{a_i - a_j}{i-j} \pmod p. \]
So we want a graph $G_k$ with at least $\half p$ connected components.

However, each $\{i,j\}$ appears in exactly one graph $G_k$,
so some graph has at most $\frac 1p \binom p2 = \half(p-1)$ edges
(by ``pigeonhole'').
This graph has at least $\half(p+1)$ connected components, as desired.

\begin{remark*}
  Here is an example for $p=5$ showing equality can occur:
  \[
    \begin{bmatrix}
      0 & 0 & 3 & 4 & 3 \\
      0 & 1 & 0 & 2 & 2 \\
      0 & 2 & 2 & 0 & 1 \\
      0 & 3 & 4 & 3 & 0 \\
      0 & 4 & 1 & 1 & 4
    \end{bmatrix}.
  \]
  Ankan Bhattacharya points out more generally
  that $a_i = i^2$ is sharp in general.
\end{remark*}