help me beat this game

[dolor]

okay...there's this game here: nim and I heard that there was a way to beat it using some binary stuff or somethin. help. thanks.

[Judd]

You can't beat this game if you are made to play first.

It is easy to win by responding to your opponents plays.

[Yonatan]

Play first, and keep trying to make the XOR of the amounts of pearls of each row equal to 0, until you can easily make it so that the computer is left with 1-1-1.
I start by removing all of the pearls from row 2. The computer variably responds to that.

Example:

Me: Remove 4 from row 2
Computer: Remove 2 from row 1
Me: Remove 2 from row 4
Computer: Remove 1 from row 4
Me: Remove 3 from row 3 (1-2-3 formation, can't lose now)
Computer: Remove 1 from row 3
Me: Remove 2 from row 4 (1-1-1 formation)
Computer: Remove 1 from row 1
Me: Remove 1 from row 4, *wins*

[NoteMe]

Originally posted by Judd
You can't beat this game if you are made to play first.

It is easy to win by responding to your opponents plays.

You don't have too start...you can pick the computer too start...

[dolor]

okay..from what i've heard is that if you start first, you always win unless you make a mathematicall error. supposedly you should leave your oppononent with a number of gems so their total value has all the same digits (ie: 222, 111, 22...)

the values are as follows:

1 gem = 1
2 gems = 10
3 gems = 11
4 gems = 100
5 gems = 101 ...and so on... (that's where the binary thing comes in)

[sql_lall]

I remember playing a similar game, with 3 rows, of 5, 4 and 3 objects each. In this the winner started, but i can't remember how. All i know is that whoever could get to 3-2-1 or 1-1-1, 2-2-2, 3-3-3 would win. However, with 4 rows, i am not exactly sure.

[Guv]

I assume we are talking about Nim, which has the following rules.

• Start with any number of piles.
• Each pile has an arbitrary number of pieces.
• A play consists of removing one or more pieces from a pile.
• A player must remove at least one piece. He may remove an entire pile. He is not allowed to take pieces from two or more piles during one play.
• Two players take turns.

The winner depends on the initial configuation. Some configurations are a win for the first player. Other configurations are a win for the second player.

Except for certain trivial games, a winning configuation for the first player has odd parity, where parity is defined as follows.

• Express the number of pieces in each pile as a binary number.
• Count the number of 1-bits, the number of 2-bits, the number of 4-bits, et cetera.
• If all the counts are even numbers, you have an even parity configuration.

For example

• Three piles with 4, 5, 5 pieces (100, 101, 101) is an odd parity configuation. There are three 4-bits, no 2-bits, and two 2-bits.
• Four piles with 4, 5, 6, 7 pieces (100, 101, 110, 111) is an even parity configuration. There are four 4-bits, two 2-bits, and two 1-bits.

Note that a player presented with an even parity configuration must always present an odd parity configuration to his opponent.

Note that a player presented with an odd parity configuation can present his opponent with either an odd or an even parity configuration. This player controls the game.


There are two basic variations of Nim. In one variation, the winner is the one who takes the last piece (or obviously) the last pile. In the other variation, the loser is the one who takes the last piece.

In the game where the winner takes the last piece, the strategy is simple. Always present your opponent with an even parity configuration. He will sooner or later give you a single pile, which you take.

In the game where the loser takes the last piece, the initial strategy is to present your opponent with even parity configurations. Late in the game, you present you opponent with an odd parity configuration consisting of piles with single pieces.