0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Colm Bhandal Aug 19 '15 at 22:52
  • $\begingroup$ 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"? $\endgroup$ – Rob Arthan Aug 19 '15 at 23:42
  • $\begingroup$ 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. $\endgroup$ – wcarvalho Aug 20 '15 at 4:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In my question I state, "the person that wins is that last person to remove a subset," so it seems that your first statement, "Observe that no player should want to remove all the elements of A in his turn. If he does, he loses." is incorrect. I note that I did remove proper from a qualifier for viable subsets. In this problem, removing any subset (not only the proper subset) is allowed. So if player 1 removes a subset with all pieces (A), player 2 has no moves and thus loses. $\endgroup$ – wcarvalho Aug 20 '15 at 4:20
  • $\begingroup$ 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. $\endgroup$ – ml0105 Aug 20 '15 at 4:23
  • $\begingroup$ I think the second assumption is fine. Thank you. $\endgroup$ – wcarvalho Aug 20 '15 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.