Technical Background

It has been proven that one of the players of Nim, let us say Player A, can leave a certain number of objects in play in a way such that Player B cannot win. This is called a safe-combination (Bouton). This safe-combination is also what theorists call p-games (the “p” standing for previous player). In other words, a safe-combination is a set of objects left in play that could result in the player who just played (or previous player) winning. N-games (where the “n” stands for next player) represent a set of objects left in play that could result in the player who is about to make a move will win the game. N-games are also called unsafe-combinations (Bouton). It has also been proven that within in any p-game, there exists some move such that an n-game will result.

NEED TO INSERT THE PROOF OF P + P = P, N + P = N, N + P = N, N + N = ?

Two finite impartial games, A and B, are said to be equivalent if and only if for all games C, A + C and B + C have the same characteristics (i.e. A + C and B + C are either both p-games or both n-games).

Let us take an example of this—let us compare the 1-pile Nim game with 3 objects in one pile (III) and the 2-pile Nim game with 1 object in one pile and 2 objects in another pile (I+II). It is my goal to prove (using the definition of equivalence) that III is equivalent to I + II. First let us explain that in order for III to be equivalent to I + II, this means that for all n element of the Natural Numbers, for all finite games, A with at most n moves such that A + I + II has the same characteristic as A + III.

Let us show that III is equivalent to I+II. By definition, this means that some game, A can be added to both games and A + III and A + I + II will have the same characteristic. The base case of this proof is the zero case. When the zero game is added to III and I + II, they both have the same characteristic. Now, assume that when a game with n moves, A, is added to both III and I + II, A + III and A + I + II have the same characteristic. We need to show that when a game with n + 1 moves, A, is added to both the III game and I + II game, A + III and A + I + II have the same characteristic.

First, let us assume that A + III is a p-game. This means that in order for A + III and A + I + II to be equivalent, we must show A + I + II is also a p-game. Since A + III is a p-game and by one of our definitions of a p-game (that there exists some move in a p-game that will make it n-game), we can look at possible outcomes of sets of objects after a move is made in A + III, all of which will be n-games: A + II, A + I, A, A^l + III (where A^l is the game A after a move has been made). If we assume A + I + II is also a p-game, find the same possible outcomes of sets of objects after a move is made and do not get a contradiction, we have shown this side of assumption to be true. If A + I + II is a p-game, then A + II, A + I, A + I + I, and A^l + I + II (again, where A^l is the game A after a move has been made).

By our assumption, we know A + II and A + I are n-games and that A is an n-game. Based on our earlier proof, we know that a n-game + p-game results in an n-game. We also know that 1 + 1 is a p-game. Therefore, A + I + I is an n-game. This leaves A^l + I + II as the only possible contradiction. However, based on our inductive hypothesis, we know that A^l + I + II has the same characteristics as A^l + III. Since A^l + III is an n-game, A^l + I + II is also an n-game. Because we arrived at no contradictions and all games resulting after a move from a p-game are in fact n-games, A + I + II is a p-game and therefore has the same characteristic as A + III.

Now, we must start with the assumption that A + I + II is a p-game and continue with the same process. After a move is made in A + I + II, we are left with the n-games A + II, A + I, A + I + I, and A^l + I + II (where A^l is the game A after a move has been made). Now let us show that A + III is also a p-game. In other words, let us show that each of the resulting games after a move has been made are n-games. We are left with the set of objects A + II, A + I, A, A^l + III (where A^l is the game A after a move has been made). If A + III is a p-game, then A + II, A + I, A, A^l + III should all be n-games and we should not arrive at any contradictions. By our assumption, we know that A + II and A + I are both n-games. By our inductive hypothesis, we know that A^l + III has the same characteristics as A^l + I + II. Since A^l + I + II is an n-game, A^l + III is also an n-game. This leaves A as a possible contradiction. Let us assume that A is a p-game and by our assumption, we know that A + I + I is an n-game. We also know that I + I is a p-game. This makes A + I + I the sum of two p-games. However, we know by our earlier proof that the sum of two p-games is a p-game. Therefore, A is an n-game. Because every game that resulted from a move in a p-game was an n-game, A + III was in fact a p-game and therefore, A + III and A + I + II have the same characteristics. Thus, III is equivalent to I + II.

Because we are using addition, and addition holds the Reflexive, Transitive, and Symmetric Properties, we can prove this to be true by showing this to be true for each property.

INSERT THE THREE PROOFS (I CAN’T READ MY HANDWRITING).

I am not sure where I am going with this yet (meaning, I do not know what my problem is yet), but I hope that this information and these proofs will help inform my readers of the characteristics of Nim games. I think I want to modify another game and show that it is equivalent to a Nim game. So, I think that these proofs will help establish how I will do this in other cases.