Yahoo Answers: Answers and Comments for Why does the Nim strategy always work? [Board Games]
Copyright © Yahoo! Inc. All rights reserved.
https://answers.yahoo.com/question/index?qid=20110410163011AAA9AH1
From Andy Cano
enUS
Sun, 10 Apr 2011 16:30:11 +0000
3
Yahoo Answers: Answers and Comments for Why does the Nim strategy always work? [Board Games]
292
38
https://answers.yahoo.com/question/index?qid=20110410163011AAA9AH1
https://s.yimg.com/zz/combo?images/emaillogous.png

From Ian: In Nim, one begins with stacks of counters. P...
https://answers.yahoo.com/question/index?qid=20110410163011AAA9AH1
https://answers.yahoo.com/question/index?qid=20110410163011AAA9AH1
Tue, 12 Apr 2011 20:58:04 +0000
In Nim, one begins with stacks of counters. Players alternately take turns choosing a stack and removing one or more counters from it. The player who takes the last counter (or counters) wins.
The winning strategy is based on the binary system, which is amazing considering the simplicity of the rules of the game! The binary system uses only the digits 0 and 1, and the place values of the digits are powers of 2. So starting from the units digit and going to the left, the place values are 1, 2, 4, 8, 16, 32, ... .
Convert the number of counters in each stack to the binary system and line up the binary numbers (by place value) in columns. Then count the number of 1's in each column.
If the numbers of 1's in every column is even, the player to move will lose against proper play by his opponent.
If at least one column has an odd number of 1's, then the player to move has a winning strategy. This player should consider the leftmost column with an odd number of 1's, choose one of the binary numbers that has a 1 in that column, change that 1 to a 0, and change the other digits in that number in any other columns containing an odd number of 1's (from 0 to 1 or from 1 to 0). This will certainly decrease the size of one of the stacks and result in an even number of 1's in every column, leaving the opponent with a losing position.
Example: Suppose we start off with stacks of 7, 8, and 10.
7 = 0111 (binary)
8 = 1000 (binary)
10 = 1010 (binary)
Only the 4's column (third from the right) and 1's column (far right) each have odd numbers of 1's. Of these "odd" columns, the leftmost column is the 4's column. Of the three binary numbers, only 7 = 0111 (binary) has a 1 in the 4's column. This means that the only good stack to remove counters from is the stack of 7.
In the binary number 0111, change the 1 in the 4's column to a 0, and change the digit in the 1's column since it is the only other "odd" column. The result is the binary number 0010, which is the regular number 2. For the player to move, the winning move is reducing the 7 counter stack to a 2 counter stack (by removing 5 counters from it).
Why this works: Note that the player who is left with a position with all "even" columns is forced to make at least one column "odd" (because that player must change at least one digit of exactly one binary number). The player who is left with a position with at least one "odd" column certainly has an available move and can always make all the columns "even" by the winning strategy described above (of which I gave the numerical example).
Thus, the player who is left with a position with all "even" columns will eventually be left without a move and lose the game against proper play by the other player. The player who is left with a position with at least one "odd" column, with proper play, will always have an available move throughout the game and thus will eventually win.