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

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

\section*{Problem}
A finite set $S$ of points in the coordinate plane
is called \emph{overdetermined} if $|S| \ge 2$
and there exists a nonzero polynomial $P(t)$,
with real coefficients and of degree at most $|S|-2$,
satisfying $P(x)=y$ for every point $(x,y) \in S$.

For each integer $n \ge 2$,
find the largest integer $k$ (in terms of $n$) such that
there exists a set of $n$ distinct points
that is \emph{not} overdetermined,
but has $k$ overdetermined subsets.

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

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

\newpage

\section*{Solution}
We claim the answer is $k = 2^{n-1}-n$.
We denote the $n$ points by $A$.

Throughout the solution we will repeatedly use the following fact:
\begin{lemma*}
  If $S$ is a finite set of points in the plane
  there is at most one polynomial with real coefficients
  and of degree at most $|S|-1$
  whose graph passes through all points of $S$.
\end{lemma*}
\begin{proof}
  If any two of the points have the same $x$-coordinate
  then obviously no such polynomial may exist at all.

  Otherwise, suppose $f$ and $g$ are two such polynomials.
  Then $f-g$ has degree at most $|S|-1$,
  but it has $|S|$ roots, so is the zero polynomial.
\end{proof}
\begin{remark*}
  Actually Lagrange interpolation implies
  that such a polynomial exists
  as long as all the $x$-coordinates are different!
\end{remark*}

\medskip

\textbf{Construction}:
Consider the set $A = \left\{ (1,a), (2,b), (3,b), (4,b), \dots, (n,b) \right\}$,
where $a$ and $b$ are two distinct nonzero real numbers.
Any subset of the latter $n-1$ points with at least one element
is overdetermined, and there are $2^{n-1}-n$ such sets.

\medskip

\textbf{Bound}:
Say a subset $S$ of $A$ is \emph{flooded}
if it is not overdetermined.
For brevity, an \emph{$m$-set}
refers simply to a subset of $A$ with $m$ elements.

\begin{claim*}
  If $S$ is an flooded $m$-set for $m \ge 3$,
  then at most one $(m-1)$-subset of $S$ is not flooded.
\end{claim*}
\begin{proof}
  Let $S = \left\{ p_1, \dots, p_m \right\}$ be flooded.
  Assume for contradiction that $S - \{p_i\}$
  and $S - \{p_j\}$ are both overdetermined.
  Then we can find polynomials $f$ and $g$ of degree at most $m-3$
  passing through $S - \{p_i\}$ and $S - \{p_j\}$, respectively.

  Since $f$ and $g$ agree on $S - \{p_i, p_j\}$,
  which has $m-2$ elements, by the lemma we have $f = g$.
  Thus this common polynomial (actually of degree at most $m-3$)
  witnesses that $S$ is overdetermined,
  which is a contradiction.
\end{proof}

\begin{claim*}
  For all $m = 2, 3, \dots, n$ there are at least $\binom{n-1}{m-1}$
  flooded $m$-sets of $A$.
\end{claim*}
\begin{proof}
  The proof is by downwards induction on $m$.
  The base case $m = n$ is by assumption.

  For the inductive step, suppose it's true for $m$.
  Each of the $\binom{n-1}{m-1}$ flooded $m$-sets
  has at least $m-1$ flooded $(m-1)$-subsets.
  Meanwhile, each $(m-1)$-set has exactly $n-(m-1)$ parent $m$-sets.
  We conclude the number of flooded sets of size $m-1$ is at least
  \[ \frac{m-1}{n-(m-1)} \binom{n-1}{m-1} = \binom{n-1}{m-2} \]
  as desired.
\end{proof}

This final claim completes the proof,
since it shows there are at most
\[ \sum_{m=2}^n \left( \binom nm - \binom{n-1}{m-1} \right)
  = 2^{n-1} - n \]
overdetermined sets, as desired.

\begin{remark*}
  [On repeated $x$-coordinates]
  Suppose $A$ has two points $p$ and $q$ with repeated $x$-coordinates.
  We can argue directly that $A$ satisfies the bound.
  Indeed, any overdetermined set contains at most one of $p$ and $q$.
  Moreover, given $S \subseteq A - \{p,q\}$,
  if $S \cup \{p\}$ is overdetermined
  then $S \cup \{q\}$ is not, and vice-versa.
  (Recall that overdetermined sets always
  have distinct $x$-coordinates.)
  This gives a bound $\left[ 2^{n-2}-(n-2)-1 \right]
  + \left[ 2^{n-2}-1 \right] = 2^{n-1}-n$ already.
\end{remark*}

\begin{remark*}
  [Alex Zhai]
  An alternative approach to the double-counting
  argument is to show that any overdetermined $m$-set
  has an flooded $m$-superset.
  Together with the first claim,
  this lets us pair overdetermined sets in a way
  that implies the bound.
\end{remark*}

\end{document}
