\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2020/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 34}
\maketitle
\section*{Problem}
Calvin and Hobbes play a game.
First, Hobbes picks a family $\mathcal F$ of subsets
of $\{1, 2, \dots, 2020\}$, known to both players.
Then, Calvin and Hobbes take turns choosing a number
from $\{1, 2, \dots, 2020\}$
which is not already chosen, with Calvin going first,
until all numbers are taken (i.e., each player has $1010$ numbers).
Calvin wins if he has chosen all the elements
of some member of $\mathcal F$, otherwise Hobbes wins.
What is the largest possible size of a family $\mathcal F$ that Hobbes
could pick while still having a winning strategy?
\section*{Video}
\href{https://www.youtube.com/watch?v=5a_XCGKiXnI}{\texttt{https://youtu.be/uj93tNL8f7M}}
\newpage
\section*{Solution}
The answer is $4^{1010} - 3^{1010}$.
In general, if $2020$ is replaced by $2n$, the answer is $4^n - 3^n$.
\bigskip
\textbf{Construction}:
The construction is obtained as follows:
pair up the numbers as $\{1,2\}$, $\{3,4\}$, \dots, $\{2019,2020\}$.
Whenever Calvin picks a numbers from one pair,
Hobbes elects to pick the other number.
Then Calvin can never obtain a subset which has both numbers from one pair.
There are indeed $2^{2n} - 3^n$ subsets with this property,
so this maximum is achieved.
\bigskip
\textbf{Bound}: The main claim is the following.
\begin{claim*}
For every $k$, there are at least $\binom{n}{k} 2^k$
sets with $k$ numbers that Calvin can guarantee to obtain after his $k$th turn.
\end{claim*}
\begin{proof}
[Proof, due to Andrew Gu]
The number of ways that Calvin can choose his first $k$ moves is
\[ 2n \cdot (2n-2) \cdot (2n-4) \cdot \dots (2n-2(k-1)). \]
But each $k$-element set can be obtained in this way in at most $k!$ ways
(based on what order its numbers were taken).
So we get a lower bound of
\[ \frac{2n \cdot (2n-2) \cdot (2n-4) \cdot \dots (2n-2(k-1))}{k!}
= 2^k \binom nk. \qedhere \]
\end{proof}
Thus by summing $k = 0, \dots, n$ the family $S$ is missing
at least $\sum_{k=0}^n 2^k \binom nk = (1+2)^n = 3^n$ subsets, as desired.
\begin{remark*}
[Alternate proof of claim by induction]
It is also possible to phrase the proof above using induction on $n+k$.
Fix any $a \in \{1, \dots, 2n\}$;
suppose Calvin picks $a$ on the first turn,
and Hobbes responds by picking $b$ on the second turn
according to his winning strategy.
We now have the same game with $\{1, \dots, 2n\} \setminus \{a,b\}$;
so we can apply induction hypothesis with $(n-1, k-1)$ and follow through.
\end{remark*}
\end{document}