\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*}
Fix a strategy for Hobbes and an integer $0 \le k \le n$.
Then there are at least $\binom{n}{k} 2^k$
sets with $k$ numbers that Calvin can 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*}
%
%\bigskip
\textbf{Alternate proof of bound}:
Fix a strategy for Hobbes, as before.
We proceed by induction on $n$ to show there are at least $3^n$ missing sets
(where a ``missing set'', like in the previous proof,
is a set that Calvin can necessarily reach).
Suppose that if Calvin picks $1$ then Hobbes picks $2$.
Then the induction hypothesis on the remaining game gives that:
\begin{itemize}
\ii there are $3^{n-1}$ missing sets that contain $1$ but not $2$;
\ii there are also $3^{n-1}$ missing sets that contain neither $1$ nor $2$.
\ii But imagining Calvin picking $2$ first instead,
applying the induction hypothesis again
we find that there are $3^{n-1}$ missing sets which contain $2$.
\end{itemize}
These categories are mutually exclusive,
so we find there are at least $3^n$ missing sets, as needed.
\end{document}