How do you win the game of Nim from the standard position of rows of 1, 3, 5 and 7 pieces?
competition/games/nim.1357 New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
How do you win the game of Nim from the standard position of rows of 1, 3, 5 and 7 pieces? Nim is generally played with one specific set up. It is called, in this paper, "1, 3, 5, 7," which shall be called "standard position." It is arranged with one piece in the first row, three in the second, five in the third, and seven in the fourth. The rows may be rearranged without any effect on the actual game play. The game play of Nim is very simple. You are allowed to take as many pieces from any single row, ranging from one piece to the entire row. However, you may only take pieces from one row per turn. Your opponent then follows with the same rules. You and your opponent alternate turns until the game is over. The game ends when one player wins by removing the last piece remaining. [ Editor: from "The Game of Nim", a Web page by Eric Berry and Soon Chung (Summer Odyssey '96 student projects, Mathematics Directed Research Class). The rules are quoted from the page. ] [ Editor: problem statement reconstructed from the postings. ]
Show solution
[ Editor: the text of "The Game of Nim" by Eric Berry and Soon Chung,
converted from HTML. The page's pictures of the board are lost; the
tables are redrawn in plain text. ]
Nim is one of the simplest mathematical games. However, it contains
very intricate mathematical secrets to winning in virtually every
situation. What these situations are, how to win, and much more are
contained in this paper.
Nim is one of the most intriguing mathematical games ever. It
challenges one's intuition and perception skills to learn its secrets.
By playing Nim alone, one will not learn its inner secrets. However by
reading this paper, an entire new horizon of Nim will be opened up to
the player.
[...] Winning Nim may not seem as easy as it sounds. There are many
mathematical factors involved for one to actually know how to win Nim in
almost any position, like "1,2,4,7,8." In certain positions, you will
lose under any circumstance if it is your turn. Standard position is,
in fact, one position where if you are going first, you should lose
under any condition assuming that your opponent knows what moves to make
as well.
[ Editor: the rules, quoted in the problem, are omitted here. ]
An example of an entire game of Nim, in the standard position (1, 3, 5,
7) would look as follows. The board starts out in standard position
(1, 3, 5, 7):
1 - The first player takes 1 piece from the top row (the entire row)
2 - The second player takes one piece from the top remaining row
3 - The first player takes three pieces from the bottom row
4 - The second player takes one piece from the top row
5 - The first player takes the entire remaining second row (five
pieces)
6 - The second player takes three pieces from the bottom row
7 - The first player takes the top row (1 piece)
8 - The second player takes the last remaining piece and wins
This depiction showed a 1, 3, 5, 7 Nim game and the second player
winning. How the second player knew what moves to make is a very
complex process. First of all, the player needs to know the binary
number system. Binary is a representation of numbers in the form of
1's and 0's. The Binary number system, much like the base 10 number
system we use, uses columns to illustrate numbers. However, beyond
that, the two are very different. The Binary number system uses only
1's and 0's. It is also divided into columns of second powers. The
first column to the right is 2^0, which is 1. The next column to the
left is 2^1, which is two. Each next column to the left, the power is
raised one from the previous one. So, the third column is 2^2, the
fourth 2^3. Each column is then either turned "on" or "off." By being
"on," it is represented by a 1. It means that the value of the column
that is "on" is needed to represent the entire number which you are
representing in binary. When a column is turned "off," it means that
the number value of that column is not used in the binary representation
of your number. Thus, the number five would be represented in binary as
101. The first 1 in the rightmost column stands for the 1's column
(2^0) being turned "on." Thus a 1 is needed to represent five in powers
of two. The 2's column (2^1) is turned "off" so a two is not needed to
represent five in binary. The four's column (2^2) is turned on, so a
four is needed to represent five in binary. Because the one's and
four's columns are turned "on," you add the 1 and the four together, but
not the two, to get five.
Also needed in knowing how to win in Nim is the "similar, dissimilar"
operation, known as S/D. This operation is rather simple, however, it
takes place only in the binary number system. The S/D operation
involves the one-ness and zero-ness of the various columns. In the
example shown below, the binary representation of the numbers 3 and 5
will go through the S/D operation. 3 is represented by "11" and five is
represented by a "101". The actual mechanics of the S/D operation shall
be explained later.
Example:
011
S/D 101
---
110
In this specific example, the two numbers in the rightmost column were
the same, so they were represented by a "0" after the S/D operation.
The 1 and the 0 in the second and third column are both different from
each other, thus they were represented by a "1" in both columns.
[ Editor: S/D is the operation usually called "exclusive or" or
"nim-addition". ]
A winning position is any of a certain type of setup when you can win
with the position of the board that your opponent has left you after his
turn. A losing position is the same except the position you inherit is
one where you lose the game. It has also been noticed that any position
where the final S/D representation of all the rows is 0000 is a losing
position and any position whose final S/D representation is anything
other than 0000 is a winning position. Thus, the object of the game is
to take away enough pieces so that the final S/D representation of all
the rows is 0000 for the other player. An actual win leaves your
opponent with 0 pieces, which also has an S/D of 0000. So, the goal is
to leave your opponent with an S/D of 0 at all points. This theorem is
proved later in this paper.
In order to show that many losing positions have a final S/D of 0000, we
shall show a few specific cases. The examples shown here are two rows
which both have the same number of pieces in each row, which we shall
call a "pair." Also, positions that have any number of "pairs" are also
0000 and known losing positions.
Theorem A: Any "pair" has a S/D of 0000.
Proof A
1. Every number must have the same binary representation of itself.
2. The S/D representation of a column whose digits are the same is
always 0.
3. Since two numbers always have the same binary representation, every
column of their binary representation matches up exactly with the
same column of the other number's binary representation to make the
S/D of every column "0."
4. Thus, the S/D representation of two rows with the same number of
pieces in each row, which are known losing positions, is 0000.
Theorem B: any number of "pairs" have a final S/D of 0000
Proof B
1. Assuming that you are using four rows, with row lengths "X" and
"Y", in any random order, you can rearrange the rows, without
changing the final S/D to be X, X, Y, Y.
2. Knowing that order does not matter, the S/D for the rows containing
both X's is 0000.
3. Knowing that order does not matter, you can find the S/D
representation of both Y rows before find the S/D representation of
0000 (from step 2) and Y.
4. Using (Proof A), you can find that the S/D of the two Y rows is also
0000.
5. The S/D of 0000 and 0000 is always 0000.
These proofs can then be generalized further to any N "pairs" where N is
a positive integer by simply finding the S/D of every pair of rows with
the same number of pieces, which will always be 0 (Proof A). You then
find the S/D of N "0000"'s, which is always 0000. From this you can
gather that many losing positions have a S/D of 0000.
It is also very important to notice that the order in which the rows are
set up does not affect the final S/D representation. Because each
column is treated individually with the S/D operation, only one column
is needed to prove that order does not matter in the S/D function. This
specific example is when there is the case 1, 0, 1, 0, 1 (column 4).
The answer here is 1 and should be if we rearrange the 1's and the 0's
every way possible. A table was made up to show how the final S/D
representation will not change no matter the order of the 1's and 0's.
In the table that follows, a simulation of five rows being rearranged is
shown. Because each column works individually of every other column in
the S/D function, only one column needs to be shown. In this column,
there are three 1's and two 0's which are rearranged in every way
possible, which is 10, to show that the order of the 1's and 0's does not
matter.
1 2 3 4 5 6 7 8 9 10
Row 1 1 1 1 1 1 1 0 0 0 0
Row 2 1 1 1 0 0 0 1 1 1 0
-----------------------------
S/D Total 1 0 0 0 1 1 1 1 1 1 0
Row 3 1 0 0 1 1 0 1 1 0 1
-----------------------------
S/D Total 2 1 0 0 0 0 1 0 0 1 1
Row 4 0 0 1 1 0 1 0 1 1 1
-----------------------------
S/D Total 3 1 0 1 1 0 0 0 1 0 0
Row 5 0 1 0 0 1 1 1 0 1 1
-----------------------------
S/D Final 1 1 1 1 1 1 1 1 1 1
One must also prove that in order to be able to win in any non-zero
position, you must be able to show that any change you make to any
number in any column will reverse the S/D of that column. Proof C shows
that this is true.
Theorem C: Any change you make in 1 row of a specific column will
reverse the final S/D of that column
Proof C
1. If one changes the S/D function of any number in a two row column,
the answer will obviously be reversed as shown in the following
table.
Original Changed
1 1
0 1 Changed row
--- ---
1 0 Final S/D
One must note the difference between the two numbers here.
2. Thus, if one changes any number, it will change the S/D at least
once in the entire series of S/D's needed to achieve the final S/D.
3. Looking at column of n number of rows, and all the S/D totals, one
can see that the numbers must remain the same in set of adjacent
rows in order to keep the S/D total the same (as shown in step 1).
4. If you change any one piece, you are changing what the S/D of what
it and the row before it is (step 1). You are also changing the S/D
of it and the row after it (also step 1). This chain reaction
continues and every S/D that used to be 1 is now 0 and every S/D
that used to be 0 is now 1.
Example
Original Changed
1 1 Row 1
S/D 1 1 Row 2
--- ---
0 0 S/D 1
S/D 1 0 Row 3 change
--- ---
1 0 S/D 2
5. Now from here on, as it works in every single case, the S/D of the
next row will be the opposite for the original and the changed
columns. Thus the S/D for the row after that will be the opposite
and it will continue throughout the entire column. The answers will
then end up as opposites.
In order to prove that the only move you need to make is to get the
opponent to a 0000 position, you must prove that from the 0000 position
that your opponent is in, he cannot then make a move which will give you
a 0000 S/D representation and thus put you in a losing position (Proof
D). And you must also prove that from every non-0000 position, there is
always a move that will give your opponent a 0000 position (Proof E).
Proof D - This proof shows that for any move that your opponent makes
while the S/D of all the rows is 0000, he cannot make a move that will
keep the S/D at 0000 for you.
1. In order for a position to be losing (S/D of 0000), the last row has
to be equal to the S/D of all other rows in order to make it 0000.
2. Supposing that your change effects only one column of a row (it
always has to effect at least one) it will change the S/D of every
row up until the last row. An example of how this works is shown
below.
Example:
Column before move Column after move
1 1
0 0
1 0 Changed row
1 1
1 1
0 0
Now we look at the actual effect this has on the S/D:
Column before move Column after move
1 1 Row 1
S/D 0 0 Row 2
--- ---
1 1 S/D Total 1
S/D 1 0 Row 3
--- ---
0 1 S/D Total 2
S/D 1 1 Row 4
--- ---
1 0 S/D Total 3
S/D 1 1 Row 5
--- ---
0 1 S/D Total 4
S/D 1 0 Row 6
--- ---
0 1 S/D Total 5
The S/D has now been completely changed from what it was before, so
clearly the S/D cannot remain the same if even one column has been
changed. Thus, the S/D of all the rows except the last one can no
longer equal the last row and thus the S/D of all the rows can no
longer be equal to 0.
[ Editor: the two tables of this example do not agree: the first
gives Row 6 before the move as 0, the second as 1. The S/D
totals in the second table (S/D Total 4 = 0, S/D Total 5 = 0)
require 0. Both are reproduced as in the original. ]
3. Supposing you take at least one away from the last row, you will
not be able to get to 0000 any more. This is because you are
changing what all the other numbers are supposed to S/D up to, but
since the S/D total up to the last row is not changing, only the
last row itself, the two can no longer be equal. This is because
there is only one binary representation for each number and only
one number would fit in the case of making the S/D 0. Because that
number is changed, the S/D can no longer be equal to 0.
Proof E - This proof shows that whatever non-zero position you are in,
there is a move that will make it a 0000 position for your opponent.
1. Suppose that the position you inherit from your opponent is not a
0000 position.
2. As shown in the example from Proof D, any move that you make will
change the final S/D outcome.
3. One can assume that every possible binary number represents a base
10 number.
4. Knowing that whatever move you make, it will change the S/D of that
column, you simply take one piece from each column where the S/D is
not 0. If that number is too large (it cannot be taken from 1 row)
then you take an amount so that you change that leftmost row
without actually taking any pieces from the leftmost row.
Proof F - This proof shows that 0000 is a losing position if the
player who has the winning moves knows what moves to make.
1. Assume that your opponent has a 0000 position.
2. Using proof D, you can know that he cannot give you a 0000 position
back.
3. Using proof E, you then can know that you will be able to put him
back into a 0000 position.
4. Assume that with 0 pieces left, it is a 0000 position.
5. Proofs D and E will repeat (your opponent will keep on getting 0000
positions) until there are 0 pieces left.
6. Thus, your opponent will lose with a 0000 position because he will
only receive the board with 0 pieces left and cannot win.
-- Eric Berry and Soon Chung