When I was a kid, I used to watch the very famous TV show Fort Boyart. It was when I was first introduced to the game of Nim.
A small description of the game: You have a set of sticks (in Fort Boyart, it was about 20). 2 players in turn take 1, 2 or 3 sticks at a time. The one who picks the last one loses the game.
When you have a set of 20 or more sticks, the game appears to be complicated. But in fact, if you follow some rules, you are assured of winning the game, if you start first!
A small observation when it is your turn to play:
If there is 1 stick letf, you lose the game.
2 sticks left, you can win the game (take 1 and the remainder goes to the opponent)
3 sticks left, you can win the game (take 2 and the remainder goes to the opponent)
4 sticks left, you can still win the game (take 3. The remainder is for the opponent)
5 sticks left, ah! Whatever you play, if the opponent is good enough, you will lose the game.
In simple terms, when you have 1 or 5 sticks left, they are losing positions for you. If you continue building the losing positions, you will still find other losing positions: 9, 13, 17, …
The rule will be, if (n modulus 4) = 1 then it is a losing position.
To win the game of Nim, you have to simply force your opponent to a losing position when it is his turn to play.
But, this is not the only version of the game of Nim and many other versions exist, which you can try:
- The one picking the last stick wins.
- You can remove from a set of {1, 2, 5} sticks etc.
I remember solving a problem (in C++) called the Bachet Game [ http://acm.uva.es/p/v104/10404.html ], which is nothing else than the game of Nim. The problem says if you have n sticks and you can pick k sticks from a given set, can you win the game of Nim if you start first?
In another post, I will try to write on the general way of solving the game of Nim.
