University:
Boston University
Course:
CAS MA 511 | Introduction to Analysis I
Academic year:

2023
Views:

181

Pages:

11
Author:

Annabel Combs

The setup:    2 players take turns picking circles from each row (we call the rows “heaps”). At each turn, at least 1 circle has to be picked. A player cannot pick from more than 1 row.  Variants played since ancient times  resemblance to Chinese “picking stones”  Current name and theory developed by C. Bouton of Harvard in 1901  name taken from German nimm meaning “take” Player 1 is forced to take the last one Player 1 takes 2 from heap 2   Player 2 takes 1 from heap 1 Player 2 wins!  Theory completely solved for any number of heaps/objects by C. Bouton  Based upon binary digital sum of heap sizes  also known as “nim-sum” ▪ Write the size of each heap in binary ▪ Add the sizes without carrying ▪ Simple rule of thumb:  Column w/ even # of 1’s = 0  Column w/ odd # of 1’s = 1 10 11 =0 1 10 10 =0 0  Winning strategy: finish each move such that the nim-sum is zero  If your partner gives you a non-zero nim-sum, it is always possible for you to make it into a zero nimsum.  If your partner gives you a zero nim-sum, it is never possible for you to keep it at a zero nimsum. You will have to change it into a non-zero nim-sum. 010 010 011  011 100 001 = 101 = 000  When the next move will result in heaps of size 1.  Normal play: Move such that an even number of heaps of size 1 remain. Here, you will lose with Normal play!  Misère play: Move such that an odd number of heaps of size 1 remain.