Calvin and Hobbes play a game. First, Hobbes picks a family $\mathcal{F}$ of subsets of $\{1,2, \ldots, 2020\}$, known to both players. Then, Calvin and Hobbes take turns choosing a number from $\{1,2, \ldots, 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?
The answer is $4^{1010}-3^{1010}$. In general, if 2020 is replaced by $2 n$, the answer is $4^{n}-3^{n}$.

『 Construction. The construction is obtained as follows: pair up the numbers as $\{1,2\}$, $\{3,4\}, \ldots,\{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^{2 n}-3^{n}$ subsets with this property, so this maximum is achieved.
Bound. The main claim is the following.
Claim - Fix a strategy for Hobbes and an integer $0 \leq k \leq n$. Then there are at least $\binom{n}{k} 2^{k}$ sets with $k$ numbers that Calvin can obtain after his $k$ th turn.

Proof, due to Andrew Gu. The number of ways that Calvin can choose his first $k$ moves is
$$
2 n \cdot(2 n-2) \cdot(2 n-4) \cdot \ldots(2 n-2(k-1)) \text {. }
$$

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{2 n \cdot(2 n-2) \cdot(2 n-4) \cdot \ldots(2 n-2(k-1))}{k!}=2^{k}\binom{n}{k} .
$$

Thus by summing $k=0, \ldots, n$ the family $S$ is missing at least $\sum_{k=0}^{n} 2^{k}\binom{n}{k}=(1+2)^{n}=3^{n}$ subsets, as desired.

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:
- there are $3^{n-1}$ missing sets that contain 1 but not 2 ;
- there are also $3^{n-1}$ missing sets that contain neither 1 nor 2 .
- 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 .

These categories are mutually exclusive, so we find there are at least $3^{n}$ missing sets, as needed.