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$
3
  • 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$ Aug 19, 2015 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, 2015 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, 2015 at 4:06

1 Answer 1

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$
3
  • $\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, 2015 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, 2015 at 4:23
  • $\begingroup$ I think the second assumption is fine. Thank you. $\endgroup$
    – wcarvalho
    Aug 20, 2015 at 4:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .