Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Nim
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Proof of the winning formula == The soundness of the optimal strategy described above was demonstrated by C. Bouton. '''Theorem'''. In a normal nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is not zero. Otherwise, the second player has a winning strategy. ''Proof:'' Notice that the nim-sum (β) obeys the usual [[associativity|associative]] and [[commutativity|commutative]] laws of addition (+) and also satisfies an additional property, ''x'' β ''x'' = 0. Let {{nowrap|''x''<sub>1</sub>, ..., ''x<sub>n</sub>''}} be the sizes of the heaps before a move, and ''y''<sub>1</sub>, ..., ''y<sub>n</sub>'' the corresponding sizes after a move. Let ''s'' = ''x''<sub>1</sub> β ... β ''x<sub>n</sub>'' and ''t'' = ''y''<sub>1</sub> β ... β ''y<sub>n</sub>''. If the move was in heap ''k'', we have ''x<sub>i</sub>'' = ''y<sub>i</sub>'' for all {{nowrap|''i'' β ''k''}}, and ''x<sub>k</sub>'' > ''y<sub>k</sub>''. By the properties of β mentioned above, we have <math display=block> \begin{align} t & = 0 \oplus t \\ & = s \oplus s \oplus t \\ & = s \oplus (x_1 \oplus \cdots \oplus x_n) \oplus (y_1 \oplus \cdots \oplus y_n) \\ & = s \oplus (x_1 \oplus y_1) \oplus \cdots \oplus (x_n \oplus y_n) \\ & = s \oplus 0 \oplus \cdots \oplus 0 \oplus (x_k \oplus y_k) \oplus 0 \oplus \cdots \oplus 0 \\ & = s \oplus x_k \oplus y_k \\[10pt] (*) \quad t & = s \oplus x_k \oplus y_k \end{align} </math> That is, to update the total nim sum <math> s </math> after updating the <math> x_k </math> heap, we need to cancel it from <math> s </math> by nim summing with <math> x_k </math>, and then nim sum in <math> y_k </math>. The theorem follows by induction on the length of the game from these two lemmas. '''Lemma 1'''. If ''s'' = 0, then ''t'' β 0 no matter what move is made. ''Proof:'' If there is no possible move, then the lemma is [[vacuous truth|vacuously true]] (and the first player loses the normal play game by definition). Otherwise, any move in heap ''k'' will produce ''t'' = ''x<sub>k</sub>'' β ''y<sub>k</sub>'' from (*). This number is nonzero, since ''x<sub>k</sub>'' β ''y<sub>k</sub>''. '''Lemma 2'''. If ''s'' β 0, it is possible to make a move so that ''t'' = 0. ''Proof:'' Let ''d'' be the position of the leftmost (most significant) nonzero bit in the binary representation of ''s'', and choose ''k'' such that the ''d''th bit of ''x<sub>k</sub>'' is also nonzero. (Such a ''k'' must exist, since otherwise the ''d''th bit of ''s'' would be 0.) Then letting ''y<sub>k</sub>'' = ''s'' β ''x<sub>k</sub>'', we claim that ''y<sub>k</sub>'' < ''x<sub>k</sub>'': all bits to the left of ''d'' are the same in ''x<sub>k</sub>'' and ''y<sub>k</sub>'', bit ''d'' decreases from 1 to 0 (decreasing the value by 2<sup>''d''</sup>), and any change in the remaining bits will amount to at most 2<sup>''d''</sup>β1. The first player can thus make a move by taking ''x<sub>k</sub>'' β ''y<sub>k</sub>'' objects from heap ''k'', then ''t'' = ''s'' β ''x<sub>k</sub>'' β ''y<sub>k</sub>'' (by (*)) = ''s'' β ''x<sub>k</sub>'' β (''s'' β ''x<sub>k</sub>'') = 0. The modification for misΓ¨re play is demonstrated by noting that the modification first arises in a position that has only one heap of size 2 or more. Notice that in such a position ''s'' β 0, and therefore this situation has to arise when it is the turn of the player following the winning strategy. The normal play strategy is for the player to reduce this to size 0 or 1, leaving an even number of heaps with size 1, and the misΓ¨re strategy is to do the opposite. From that point on, all moves are forced.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)