Two players $A$ and $B$ are playing the Eat the set game. The game is the following:
• The game starts with a set $S$ of $k$ elements i.e. $S = \{1, 2, . . . , k\}.$ Players have to choose subsets of set S except the empty set and the set $S$ itself. Let us call this set as $S_p$ defined as $S_p ∈ \mathcal{P}(S) − \{∅, S\}$
• The game proceeds in turns:
(a) Player $A$ goes first and chooses a subset $S_1 ∈ S_p$. Now, we remove the set $S_1$ and all the supersets of $S_1$ from $S_p$.
(b) Then, player $B$ chooses another subset $S_2 ∈ S_p$ and as before, we remove the set $S_2$ and all its supersets from $S_p$.
(c) The players continue in turns till there is no legal move left. The player who cannot make a legal move loses! For example, let us take the game for $k = 1, k = 2$ and $k = 3$:
(a) $k=1: S = \{1\}$. Since $A$ cannot choose $∅$ or $S$, $A$ loses.
(b) $k=2: S = \{1, 2\}$. $A$ has two choices - either choose $\{1\}$ or $\{2\}$. $B$ simply chooses the other option i.e. $\{2\}$ or $\{1\}$. Now, $A$ has no moves and $B$ wins.
(c) $k=3: S = \{1, 2, 3\}$. A can either pick a $1$-set i.e. either $\{1\}, \{2\}$, or $\{3\}$, or a $2$-set i.e. $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. $B$ simply picks the complement e.g. $\{2,3\}$ if $A$ picks $\{1\}$, or $B$ picks $\{1\}$ if $A$ picks $\{2,3\}$. Now, $A$ can only pick from the only legal $2$-set remaining i.e. from $\{\{1,2\},\{1,3\}\}$ in the example. This is as in the case of $k = 2$ and $B$ still wins.
There is a conjecture that $B$ always has a winning strategy in this game.
(a) Prove this conjecture for $k = 4$ i.e. prove that whatever moves $A$ can come up with, $B$ can always reply such that, in the end, $A$ has no moves. Make sure you cover all the cases in your arguments.