Hello hello,
I'm currently taking a class called "History of Math," and it has been super duper interesting so far.
In one of our first classes, our professor told us about the game of Nim.
The UI is pretty plain, and some might call "outdated," but the game is very interesting.
The goal is to become the last player to uncheck a box, and in this article, I'm going to show you how to beat the game.
Here are the rules:
- There are 3 rows of check boxes
- When you click on a check box, you uncheck that & the boxes to the right of it
- The goal is to become the player to remove the last check box
- You start the game, and play against the computer, which responds immediately after you make your move
How to beat the game
The key is in understanding the binary XOR operation. Look at the following table:
What you will notice is that when we use the XOR notation, we get 1 as the result when there are odd number of inputs (1). If there are all zeros or two 1s, the output is 0.
Our goal is to leave the computer with all 0 results.
Let's see an example:
Suppose this is our starting point:
If you click on the "Help" button, it will just give you the binary notation for all the rows. It can save you some time, in the sense that you won't have to manually count the boxes.
In this case, the first row is denoted with a 10000, which means that there are 16 checked boxes, 13 checked boxes in the second row, and finally, 8 checked boxes in the third row.
Currently, if I were to perform XOR on the given rows, I would get 10101 as my result, which is definitely what I don't want.
What I want to do is leave the computer with all 0 results. So what I will do is this:
In order to make all 0s, I decided to turn the 10000 into 101. That way, I will have two 1s in all columns except for column #3, which has all 0s. This way I will have all 0s as result.
So I will leave only 5 boxes checked in the first row, and click on the 6th box.
The computer accepts that it was a good move. Then the computer leaves me with 11, 1101, 1000. So my next move will be the following:
Now the computer leaves us with 10, 1011, and 1000. This would result in 0001, which is not what we want. So I will reduce the second row to be 1011 instead, which means that I leave only 11 checked boxes.
The computer then leaves me with 1, 1010, and 1000. As earlier, this would result in 0011, which is not what we are looking for. So I will change the second row from 1010 to be 1001 instead. That will give me two pairs of 1s in two columns, and the rest of the columns as 0. So everything results in 0 using the XOR notation.
Then the computer removes all the checked boxes from the first row, and leaves me with 0, 1001, and 1000. So I will make the second row also 1000, since I can reduce it.
The computer leaves me with 0, 10, 1000. So I will just make it the same by reducing the third row to be 10 also.
Then I have 0, 1, 10. I will make same by making third row as 1.
Then there's just one checked box in the third row.
I click it, and then see this.
We won the game.
Once you play for a few times, you will know how to beat the game everytime. Good luck!!
Warmly,
Suraj