Spiked Math Games  // Math Fail Blog  // Gauss Facts  // Spiked Math Forums  // Spiked Math Comics

# 221

xkcd Nim - April 16, 2010
• Currently 4.7/5
• 1
• 2
• 3
• 4
• 5

Friday Challenge: If you haven't heard of Nim before, see if you can find the optimal strategy in the general case with multiple piles of coins. [Hint: Consider 1 pile. Then 2 piles.]

Isn't the best strategy always to take off one coin?

If it is, since there are 14 coins he won

It may be me wrongly parsing the rules, but how does this game actually end?

If you are not allowed to take more coins from one pile than remaining there – and it's in my opinion obvious the "remaining there" applies to the state of the pile after I took the coins – how do you take a coin from a one-coin-pile?

If you take the coin, there is no coin remaining there, which is less than one, and if you don't take a coin…well, you don't take one then.

Help?

Ok, so I'm confused by the statement "up to the number of coins remaining in that pile"... is it the coins remaining after you take some, or before?

If "remaining" refers to the number of coins AFTER you take some, then I take it to mean that for a number of coins taken, N, there must be a number of coins remaining, M where M >= N. If that is the case you could never take the last coin.

If "remaining" refers to the number of coins BEFORE you take some, then the statement itself is redundant, because it follows logically from these two statements: "they may remove any number of coins from one of the piles" and "they can only take from a single pile on a given turn".

You can take an entire pile, if you wish :P

one pile: grab the whole pile.
two piles: do not grab a whole pile, then the other person has won. you may grab all but one from one pile, so the other person cannot use the last coin. so he grabs all but one from the other pile, you grab one, he grabs one ... does not work out for you,

so you leave two on the pile, he grabs at least one from one of the piles ... hmmmmm

you need to preserve symmetry. use brute force for leaving less then 2

I've always played this 4 piles of 1,3,5,7

I've called a similar and very fun game Nim and Cross-out. 5 lines of 1, 2, 3, 4, and 5 lines each. You can cross out however many in one line. If you cross out the middle 3, let's say, in the line of 5, then the other two left over become separate lines and can't be crossed out together.

If we take the nim value of this game you get 0. This means that the 2nd player will always win if he plays smart. No matter what the 1st player does the 2nd player can win.

If you play the game of 1 3 5 7 then the 2nd player will win again. Nim value of 0.

The only hope is if the 2nd player stuffs up. If I was the 1st player I would just take all the coins and run

I don't get the joke. I believe Randall has a winning strategy, where Mike does not.

Okay, sorry, I misread the 6 for an 8. He is screwed.

Yay Mike!

Try playing nim with the edges of a graph instead --- you can remove any positive number of edges you wish, so long as all the edges have a vertex in common. Much more challenging game....

A strange game. The only winning move is to not play.

How about a nice game of chess?

No, it's NOT a reference to the A Day in the Life of a Turret machinima. It's a reference to the movie Wargames. Know your pop culture, man.

sounds like a job for binary addition with no carrying.

this show helps explain how to win, along with why you'll always win. http://revision3.com/scamschool/nim/

But don't get forced into a duel against a professional!

The optimal strategy is when you say "You can go first" :D

Oh, and why xkcd?

Prolly because it's another math- and logic-themed strip.

the captcha however has always remained same and it is remembered by the autocomplete in whatever browser i try it with... or i could be a bot.

I guess xkcd is rational...

Haha, I used to use this game to win free drinks in an inconspicuous manner.

Where is Mike?????

I'm still here ^_^
I skipped the weekend (and for the record, in my time zone the Monday comic was up on time haha :P)

What's the solution for this???? Apart from of course not playing and/or switching the option of playing first??

3 ^ 5 ^ 6 = 0 [XOR of three gives a zero] , that means no matter what the first player removes from one of the piles , he is sure going to lose :D

Your Friday challenge invaded my head while I was in bed on Sunday night, and I couldn't get to sleep until I had solved it for three piles! That took quite a while because I was very tired. This made me more tired. :(
The next day I challenged my Mum to a game. :D

2 things:

- Unfunny comic,

First thing, I take it you are from stumble upon ;-)

Second, the captcha is meant to filter out spam, which it successfully does. Javascript is used to fill in the right answer (which bots have trouble with). The reason for this is so people don't get too annoyed.

hahaha binary.

just with the captcha; couldn't an unscrupulous person hook it into wolfram|alpha?

find optimal strategy for 1 pile. if we have n piles, pick at every turn an entire pile so we reduce the problem to the 1 pile one?

find optimal strategy for 1 pile. if we have n piles, pick at every turn an entire pile so we reduce the problem to the 1 pile one?

Sorry for grammatical errors because English is not my native language.
Frankly speaking this question is just at primary level in China. I've learnt the best solution when I was in primary school (you can always win, but maybe is not the fastest way). Here's how.
If there's odd number of piles (excluding 1 pile), you go SECOND.
If there's even number of piles or there's only 1 pile, you go FIRST.
Since the quantities of each pile are not the same, the strategy is to make every pile has the same quantity of coins. Whatever the opponent take, you take the most large pile and make it equals to the second large one. (e.g. 6, 5, 3 -> 5, 5, 3; 4, 2 -> 2, 2) By doing this turn after turn, you'll always win the game.
For 1 pile, you take the whole pile, you win.
But, wait, what does "take the last coin" mean? If that means "You have to take the last one, the only one coin" but not "You clear the table", then you'll just need to find a way to leave 2 coins for your opponent. Then you win.

Welcome to Spiked Math!

Hello my fellow math geeks. My name is Mike and I am the creator of Spiked Math Comics, a math comic dedicated to humor, educate and entertain the geek in you. Beware though, there might be some math involved :D

New to Spiked Math?
View the top comics.

New Feature: Browse the archives in quick view! Choose from a black, white or grey background.

Other Sites: