# Why does the 1st player in this subset take-away game always have a winning strategy?

This is a HW problem of mine that I cannot, for the life of me, figure out. There is a take-away game where there are a number of elements A, and the person that wins is that last person to remove a subset. The question is:

If the whole set A is a possible move in a game, why does the 1st player have a winning strategy?

The part of the answer I don't understand goes as follows:

We reason by cases to show that player 1 has a winning strategy.Suppose game G includes A as a possible move. Let G' be the same game as G except that A is removed from the set of possible moves.

Case 1: Player 1 has a winning strategy in the game G'. Then the first move of Player 1’s winning strategy will also be a legal move in game G. Moreover, after this move in game G, the set A will no longer be a possible move, so the move will lead to the same winning situation for Player 1 as in game G'. So Player 1 has a winning strategy in this case.

I do not understand why the legal move that is a part of a winning strategy in G' is also a part of a winning strategy in G.

• A small technicality: player 1 only has a winning strategy if the set $A$ contains more than $2$ elements, assuming players must take non-empty sets away. Otherwise player $1$ is forced to take away $A$ and then it's a draw (because no one has removed a proper subset). Also, are you missing a case 2? – Colm Bhandal Aug 19 '15 at 22:52
• What is case 2 in the proposed answer? And are you sure the rule about who wins says "proper subset" rather than "non-empty subset"? – Rob Arthan Aug 19 '15 at 23:42
• I am missing a 2nd case because that made sense to me. The proper set part was a part of the first part of the question. For the second part, any set was allowed including the entire set. I'll change that. Also--yes, you're right Colm. – wcarvalho Aug 20 '15 at 4:06

Observe that no player should want to remove all the elements of $A$ in his turn. If he does, he loses. So we consider the game $G^{\prime}$, in which removing every element of $A$ is not an option. The reasoning of the players' will be the same amongst $G$ and $G^{\prime}$.
So in $G^{\prime}$, player $1$ removes $A \setminus \{a\}$, where $a \in A$. Player $2$ then has no valid move in $G^{\prime}$, thus losing.
In $G$, player $2$ must remove $a$, the only remaining element in the set, thus losing.
• Yes, my answer was based upon the important quantifier of "proper subset." Your edit changes things. My answer also assumes $A$ has at least two elements. – ml0105 Aug 20 '15 at 4:23