Question

In the game of Nim, stones are arranged in piles of arbitrary size. Each
player in turn takes a few stones from any one pile. Every player must take
at least one stone on every turn. The player who takes the last stone wins.
Games of this type always have a winning strategy. This strategy can be
established by tagging all possible positions in the game with two tags,
“plus” and “minus,” in such a way that any move from a “plus” position
always leads to a “minus” position, and from any “minus” position there is
always a possible move into some “plus” position. The final

Answer 1

In the game of Nim, stones are arranged in piles of arbitrary size. Each
player in turn takes a few stones from any one pile. Every player must take
at least one stone on every turn. The player who takes the last stone wins.
Games of this type always have a winning strategy. This strategy can be
established by tagging all possible positions in the game with two tags,
“plus” and “minus,” in such a way that any move from a “plus” position
always leads to a “minus” position, and from any “minus” position there is
always a possible move into some “plus” position. The final winning
position must be tagged “plus.” Therefore, if the first player begins in a
“minus” position, she can win by moving right away into a “plus” position
and returning to a “plus” position on each subsequent move. If, however, the
first player begins in a “plus” position, then the second player can win,
provided he knows how to play correctly.
In Nim, we can convert the number of stones in each pile into a binary
number and write these binary numbers in one column (so that the “units”
digits are aligned on the right). We can tag the position “plus” if the number
of 1s in each column is even and “minus” if the count of 1s in at least one
column is odd. Prove that this method of tagging “plus” and “minus”
positions defines a winning strategy. Who wins starting with four piles of 1,
3, 5, and 7 stones — the first or the second player? What’s the correct
response if the first player takes five stones from the pile of 7?