Problem: Suppose the sequence of nonnegative integers
$a_1, a_2, \dots, a_{1997}$ satisfies
\[ a_i + a_j \leq a_{i+j} \leq a_i + a_j + 1  \]
for all $i,j \geq 1$ with $i + j \leq 1997$.
Show that there exists a real number $x$ such that
$a_n = \lfloor nx \rfloor$ for all $1 \leq n \leq 1997$.

\end{enumerate}

Solution: We are trying to show there exists an $x \in \RR$
such that
\[ \frac{a_n}{n} \le x < \frac{a_n+1}{n} \qquad \forall n. \]
This means we need to show
\[ \max_i \frac{a_i}{i} < \min_j \frac{a_j+1}{j}. \]
Replace 1997 by $N$.
We will prove this by induction,
but we will need some extra hypotheses on the indices $i,j$
which are used above.

\begin{claim*}
  Suppose that
  \begin{itemize}
    \ii Integers $a_1$, $a_2$, \dots, $a_N$ satisfy the given conditions.
    \ii Let $i = \opname{argmax}_n \frac{a_n}{n}$;
    if there are ties, pick the smallest $i$.
    \ii Let $j = \opname{argmin}_n \frac{a_n+1}{n}$;
    if there are ties, pick the smallest $j$.
  \end{itemize}
  Then \[ \frac{a_i}{i} < \frac{a_j+1}{j}. \]
  Moreover, these two fractions are in lowest terms,
  and are adjacent in the Farey sequence of order $\max(i,j)$.
\end{claim*}
\begin{proof}
  By induction on $N \ge 1$ with the base case clear.
  So suppose we have the induction hypothesis
  with numbers $a_1$, \dots, $a_{N-1}$,
  with $i$ and $j$ as promised.

  Now, consider the new number $a_N$.
  We have two cases:
  \begin{itemize}
    \ii Suppose $i+j > N$.
    Then, no fraction with denominator $N$
    can lie strictly inside the interval;
    so we may write for some integer $b$
    \[ \frac bN \le \frac{a_i}{i}
      < \frac{a_j+1}{j} \le \frac{b+1}{N}. \]
    For purely algebraic reasons we have
    \[ \frac{b-a_i}{N-i} \le \frac bN \le \frac{a_i}{i}
      < \frac{a_j+1}{j} \le \frac{b+1}{N}
      \le \frac{b-a_j}{N-j}. \]
    Now,
    \begin{align*}
      a_N &\ge a_i + a_{N-i}
        \ge a_i + (N-i) \cdot \frac{a_i}{i} \\
      &\ge a_i + (b-a_i) = b \\
      a_N &\le a_j + a_{N-j} + 1
        \le (a_j+1) + (N-j) \cdot \frac{a_j+1}{j} \\
      &= (a_j+1) + (b-a_j) = b+1.
    \end{align*}
    Thus $a_N \in \{b,b+1\}$.
    This proves that $\frac{a_N}{N} \le \frac{a_i}{i}$
    while $\frac{a_N+1}{N} \ge \frac{a_j+1}{j}$.
    Moreover, the pair $(i,j)$ does not change,
    so all inductive hypotheses carry over.

    \ii On the other hand, suppose $i+j = N$.
    Then we have
    \[ \frac{a_i}{i} < \frac{a_i + a_j + 1}{N} < \frac{a_j+1}{j}.  \]
    Now, we know $a_N$ could be either $a_i + a_j$ or $a_i + a_j + 1$.
    If it's the former, then $(i,j)$ becomes $(i,N)$.
    If it's the latter, then $(i,j)$ becomes $(N,j)$.
    The properties of Farey sequences ensure that
    the $\frac{a_i + a_j + 1}{N}$ is reduced, either way.
  \end{itemize}
\end{proof}