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

\begin{document}
\title{USAMO 2020/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 16}
\maketitle

\section*{Problem}
Suppose that $(a_1, b_1)$, $(a_2, b_2)$, \dots, $(a_{100}, b_{100})$
are distinct ordered pairs of nonnegative integers.
Let $N$ denote the number of pairs of integers $(i,j)$ satisfying
$1 \le i < j \le 100$ and $\left\lvert a_ib_j - a_jb_i \right\rvert = 1$.
Determine the largest possible value of $N$
over all possible choices of the $100$ ordered pairs.

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

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

\newpage

\section*{Solution}
The answer is $197$.
In general, if $100$ is replaced by $n \ge 2$ the answer is $2n-3$.

The idea is that if we let $P_i = (a_i, b_i)$ be a point
in the coordinate plane, and let $O = (0,0)$
then we wish to maximize the number of triangles
$\triangle O P_i P_j$ which have area $1/2$.
Call such a triangle \emph{good}.

\paragraph{Construction of $197$ points.}
It suffices to use the points
$(1,0)$, $(1,1)$, $(2,1)$, $(3,1)$, \dots, $(99,1)$ as shown.
Notice that:
\begin{itemize}
  \ii There are $98$ good triangles
  with vertices $(0,0)$, $(k,1)$ and $(k+1,1)$ for $k=1, \dots, 98$.

  \ii There are $99$ good triangles
  with vertices $(0,0)$, $(1,0)$ and $(k,1)$ for $k=1, \dots, 99$.
\end{itemize}
This is a total of $98 + 99 = 197$ triangles.
\begin{center}
\begin{asy}
  draw( (6,0)--(0,0)--(0,2), grey, Arrows );
  dot("$O$", (0,0), dir(225), red );
  dot("$(1,0)$", (1,0), dir(-90), blue);
  dot("$(1,1)$", (1,1), dir(90), blue);
  dot("$(2,1)$", (2,1), dir(90), blue);
  dot("$(3,1)$", (3,1), dir(90), blue);
  dot("$(4,1)$", (4,1), dir(90), blue);
  label("$\dotsb$", (5,1), blue);
\end{asy}
\end{center}

\paragraph{Proof that $197$ points is optimal.}
We proceed by induction on $n$ to show the bound of $2n-3$.
The base case $n=2$ is evident.

For the inductive step,
suppose (without loss of generality) that the point $P = P_n = (a,b)$
is the farthest away from the point $O$ among all points.
\begin{claim*}
  This farthest point $P = P_n$ is part of at most two good triangles.
\end{claim*}
\begin{proof}
  We must have $\gcd(a,b) = 1$ for $P$ to be in any good triangles at all,
  since otherwise any divisor of $\gcd(a,b)$ also divides $2[OPQ]$.
  Now, we consider the locus of all points $Q$ for which $[OPQ] = 1/2$.
  It consists of two parallel lines passing with slope $OP$, as shown.
  \begin{center}
  \begin{asy}
    size(10cm);
    int M = 6;
    pair P = (3,2);
    pair O = (0,0);
    draw(O--P, blue);
    draw(arc(O,abs(P),0,90), deepcyan);
    for (int i=-M#2; i<=M; ++i) {
      draw( (-M#2,i)--(M,i), grey);
      draw( (i,-M#2)--(i,M), grey);
    }
    draw( (-M#2,0)--(M,0), black+1.4, Arrows(TeXHead) );
    draw( (0,-M#2)--(0,M), black+1.4, Arrows(TeXHead) );

    pair X = (1,1);
    pair Y = O+P-X;
    dot("$(u,v)$", X, dir(135), red);
    dot("$(u',v')$", Y, dir(-45), red);

    pair X1 = X+P;
    pair X2 = X-P;
    draw(X1--X2, red+dashed, Arrows);

    pair Y1 = Y+P;
    pair Y2 = Y-P;
    draw(Y1--Y2, red+dashed, Arrows);

    dot("$O$", O, dir(225), blue);
    dot("$P=(a,b)$", P, dir(30), blue);
  \end{asy}
  \end{center}
  Since $\gcd(a,b)=1$, see that only two lattice points on this locus
  actually lie inside the quarter-circle centered at $O$ with radius $OP$.
  Indeed if one of the points is $(u,v)$
  then the others on the line are $(u \pm a, v \pm b)$ where the signs match.
  This proves the claim.
\end{proof}
This claim allows us to complete the induction by simply deleting $P_n$.

\end{document}
