Winning at NIMDate: 06/09/97 at 19:22:39 From: Brett Wilson Subject: Puzzles Dear Dr. Math, Our teacher gave us a game called NIM. In the game you are given a series of dots in rows. There can be any number of dots per row and any number of rows. Each player must remove any amount of dots, but they must all be from the same row. The winner of the game is the person who takes the last dot out of the game. For example: . ... .... ..... ....... With this diagram, I might take the one dot on top and then, you could take any other dot/dots from another row. Please help us if you have any idea of the strategy to a guaranteed winning game. Thanks Date: 06/10/97 at 11:18:01 From: Doctor Anthony Subject: Re: Puzzles The strategy for winning the game of Nim has been extensively studied. Express the number of dots in any row in binary notation, so if we had three rows with 3, 4, 5 dots respectively we could write this as: 3 1 1 4 1 0 0 5 1 0 1 ---------- 2 1 2 This position is 'unsafe' because one of the columns sums to an odd number. This can be made 'safe' by the first player by taking two dots from the top row leaving the table in the form: 1 1 4 1 0 0 5 1 0 1 ---------- 2 0 2 This is 'safe', but the next player by making any move whatever will of necessity go to an 'unsafe' position, and the first player can again calculate column totals and get back to a 'safe' position. The winning strategy requires that if you have the next move, the situation be 'unsafe', i.e. that there be an odd number in one of the column totals, and you then take dots from one of the rows so as to make all the column totals even. You are now safe, because the next move will of necessity go back to an unsafe position. You continue in this way, such that AFTER your move, the column totals will be even, and you will win. -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/