\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USAMO 1999/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 37}
\maketitle

\section*{Problem}
Let $p > 2$ be a prime and let $a$, $b$, $c$, $d$ be integers not divisible by $p$,
such that
\[ \left\{ \dfrac{ra}{p} \right\} + \left\{ \dfrac{rb}{p} \right\}
  + \left\{ \dfrac{rc}{p} \right\} + \left\{ \dfrac{rd}{p} \right\} = 2  \]
for any integer $r$ not divisible by $p$.
(Here, $\{t\} = t - \left\lfloor t \right\rfloor$ is the fractional part.)
Prove that at least two of the numbers
$a+b$, $a+c$, $a+d$, $b+c$, $b+d$, $c+d$ are divisible by $p$.

\section*{Video}
\href{https://www.youtube.com/watch?v=LNBcuBMmN9g&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/LNBcuBMmN9g}}

\section*{External Link}
\url{https://aops.com/community/p340038}

\newpage

\section*{Solution}
First of all, we apparently have $r(a+b+c+d) \equiv 0 \pmod p$
for every prime $p$, so it automatically follows that $a+b+c+d \equiv 0 \pmod p$.
By scaling appropriately, and also replacing each number with its remainder modulo $p$,
we are going to assume that
\[ 1 = a \le b \le c \le d < p. \]
We are going to prove that $d = p-1$, which will solve the problem.

\begin{claim*}
  For each integer $r = 1, 2, \dots, p-1$ we have
  \[ 2(r-1) = \left\lfloor \frac{rb}{p} \right\rfloor
    + \left\lfloor \frac{rc}{p} \right\rfloor
    + \left\lfloor \frac{rd}{p} \right\rfloor. \]
\end{claim*}
\begin{proof}
  By plugging in $r=1$ to the given we have $a+b+c+d=2p$.
  Now, we have
  \[ 2 = \sum_{\text{cyc}} \left( \frac{ra}{p}
    - \left\lfloor \frac{ra}{p} \right\rfloor \right) \]
  and since $a+b+c+d=2p$ the conclusion follows.
\end{proof}

%We now define $x = b/p$, $y = c/p$, $z = d/p$.
%Hence $0 < x \le y \le z < 1$.
%Our goal it show that $z = (p-1)/p$.

We vaguely outline the approach now, before giving a formalization.
Imagine the interval $[0,1]$.
One by one, for each $r = 1, 2, 3, \dots, p-1$,
we mark the fractions with denominator $r$ on this number line;
the resulting pictures may be better known as \emph{Farey fractions}.
At each step, we can place the three numbers $b/p$, $c/p$, $d/p$
into one of the resulting sub-intervals.
Our goal is to show that $d/p$ is always in the rightmost interval,
while $b/p$ and $c/p$ are always to the right of symmetrically mirrored points.
An example of a possible diagram is shown below (not to scale).
\begin{center}
\begin{asy}
  unitsize(11cm);
  real h = 0.05;
  draw( (0,0)--(1,0) );
  void tick(string s, real x, real t, pen p) {
    label(s, (x,-t), dir(-90), p);
    draw((x,-t)--(x,t), p);
  }
  tick("$0$", 0, h, black);
  tick("$1$", 1, h, black);
  tick("$\frac{1}{2}$", 1/2, h, black);
  tick("$\frac{1}{3}$", 1/3, 0.7*h, blue);
  tick("$\frac{2}{3}$", 2/3, 0.7*h, blue);
  tick("$\frac{1}{4}$", 1/4, 0.5*h, deepgreen);
  tick("$\frac{3}{4}$", 3/4, 0.5*h, deepgreen);
  tick("$\frac{1}{5}$", 1/6, 0.3*h, grey); // white lie
  tick("$\frac{2}{5}$", 2/5, 0.3*h, grey);
  tick("$\frac{3}{5}$", 3/5, 0.3*h, grey);
  tick("$\frac{4}{5}$", 5/6, 0.3*h, grey); // white lie
  dot("$\boxed{\frac{b}{p}}$", (0.3,0), dir(90), red);
  dot("$\boxed{\frac{c}{p}}$", (0.72,0), dir(90), red);
  dot("$\boxed{\frac{d}{p}}$", (0.95,0), dir(90), red);
\end{asy}
\end{center}

In symbols, it will be enough to prove the following.
\begin{claim*}
  For each $r = 1, 2, \dots, p-2$ we have
  $\frac{r-1}{r} < \frac dp < 1$.

  Equivalently, for each $r = 1, 2, \dots, p-2$
  we have $\left\lfloor \frac{rb}{p} \right\rfloor
  + \left\lfloor \frac{rc}{p} \right\rfloor = r-1$.
\end{claim*}
\begin{proof}
  Assume this is not true and take the minimal counterexample $r > 1$.
  Then evidently
  \[ r-1 > \left\lfloor \frac{rd}{p} \right\rfloor
    \ge \left\lfloor \frac{(r-1)d}{p} \right\rfloor
    = r-2.  \]
  Now, we have that
  \[ 2(r-1) = \left\lfloor \frac{rb}{p} \right\rfloor
    + \left\lfloor \frac{rc}{p} \right\rfloor
    + \underbrace{\left\lfloor \frac{rd}{p} \right\rfloor}_{= r-2}.  \]
  Thus
  $\left\lfloor \frac{rb}{p} \right\rfloor >
  \left\lfloor \frac{(r-1)b}{p} \right\rfloor$,
  and $\left\lfloor \frac{rc}{p} \right\rfloor >
  \left\lfloor \frac{(r-1)b}{p} \right\rfloor$.
  An example of this situation is illustrated below with $r = 7$
  (not to scale).
  \begin{center}
  \begin{asy}
    unitsize(11cm);
    real h = 0.05;
    draw( (0,0)--(1,0) );
    void tick(string s, real x, real t, pen p) {
      label(s, (x,-t), dir(-90), p);
      draw((x,-t)--(x,t), p);
    }
    tick("$0$", 0, h, black);
    tick("$1$", 1, h, black);
    tick("$\frac{1}{2}$", 1/2, h, black);
    tick("$\frac{1}{3}$", 1/3, 0.7*h, blue);
    tick("$\frac{2}{3}$", 2/3, 0.7*h, blue);
    tick("$\frac{1}{4}$", 1/4, 0.5*h, deepgreen);
    tick("$\frac{3}{4}$", 3/4, 0.5*h, deepgreen);
    tick("$\frac{1}{5}$", 1/6, 0.3*h, grey);
    tick("$\frac{2}{5}$", 2/5, 0.3*h, grey);
    tick("$\frac{3}{5}$", 3/5, 0.3*h, grey);
    tick("$\frac{4}{5}$", 5/6, 0.3*h, grey);
    tick("$\frac{1}{6}$", 1/8, 0.3*h, grey);
    tick("$\frac{5}{6}$", 7/8, 0.3*h, grey);
    dot("$\boxed{\frac{b}{p}}$", (0.31,0), dir(90), red);
    dot("$\boxed{\frac{c}{p}}$", (0.725,0), dir(90), red);
    dot("$\boxed{\frac{d}{p}}$", (0.92,0), dir(90), red);
    tick("$\dfrac{2}{7}$", 2/7, 1.5*h, red+1);
    tick("$\dfrac{5}{7}$", 0.7, 1.5*h, red+1);
    tick("$\dfrac{6}{7}$", 0.9, 1.5*h, red+1);

    tick("$\dfrac{7}{8}$", 0.95, 2*h, orange+1);
    tick("$\dfrac{3}{8}$", 0.375, 2*h, orange+1);
    tick("$\dfrac{6}{8}$", 0.75, 2*h, orange+1);
  \end{asy}
  \end{center}
  Right now, $\frac bp$ and $\frac cp$
  are just to the right of
  $\frac ur$ and $\frac vr$ for some $u$ and $v$ with $u+v=r$.
  The issue is that the there is some fraction just to the right of
  $\frac bp$ and $\frac cp$ from an earlier value of $r$,
  and by hypothesis its denominator is going to be strictly greater than $1$.

  It is at this point we are going to use the properties of Farey sequences.
  When we consider the fractions with denominator $r+1$,
  they are going to lie outside of the interval
  they we have constrained $\frac bp$ and $\frac cp$ to lie in.

  Indeed, our minimality assumption on $r$ guarantees that there is no
  fraction with denominator less than $r$ between $\frac ur$ and $\frac bp$.
  So if $\frac ur < \frac bp < \frac st$
  (where $\frac ur$ and $\frac st$ are the closest fractions
  with denominator at most $r$ to $\frac bp$)
  then Farey theory says the next fraction
  inside the interval $[\frac ur, \frac st]$
  is $\frac{u+s}{r+t}$, and since $t > 1$, we have $r+t > r+1$.
  In other words, we get an inequality of the form
  \[ \frac ur < \frac bp < \underbrace{\text{something}}_{=s/t} \le \frac{u+1}{r+1}. \]

  The same holds for $\frac cp$ as
  \[ \frac vr < \frac cp < \text{something} \le \frac{v+1}{r+1}. \]
  Finally,
  \[ \frac dp < \frac{r-1}{r} < \frac{r}{r+1}. \]
  So now we have that
  \[ \left\lfloor \frac{(r+1)b}{p} \right\rfloor
    + \left\lfloor \frac{(r+1)c}{p} \right\rfloor
    + \left\lfloor \frac{(r+1)d}{p} \right\rfloor
    \le u + v + (r-1) = 2r-1 \]
  which is a contradiction.
\end{proof}
Now, since
\[ \frac{p-3}{p-2} < \frac dp
  \implies d > \frac{p(p-3)}{p-2} = p - 1 - \frac{2}{p-2} \]
which for $p > 2$ gives $d = p-1$.

\end{document}
