The Game of Nim

[phil1882]

not sure if it's been posted before but this is an interesting little puzzle.

the game of nim has very basic rules.

you start off with a pile of pennies, and separate them into several usually uneven stacks.

(they don't have to be uneven, but for the most part are.)

you can take as many pennies as you desire form any particular stack.

you cannot however take from more than 1 stack. and you must always take at least 1 penny.

the object of the game is to leave your opponent with only 1 penny left. whoever takes the last penny loses.

can you come up with a general winning strategy?

[phil1882]

it's been several days and it looks like no one is gonna attempt this so i'll just post the solution.

in general:

convert the number of pennies in each stack into a binary number.

remove an amount such that the result of xoring them together equals zero.

example

stack 1: 3 pennies,

stack 2: 8 pennies,

stack 3: 9 pennies.

   11

1000

1001

so remove 2 from stack 1.

there is an exception to this rule. if 2 or more stacks contain a single penny, you may want to remove pennies such that there is yet another 1 penny stack, even if it breaks the xor rule.

in the example above, after removing 2 from stack 1, if you opponent removes 7 form stack 2, you need to remove 8 from stack 3.

[Yoruichi-san]

It's an interesting game, but I think a lot of people already knew the general strategy, hence it would of seemed unfair to answer and ruin the fun for everyone else. *shrugs*

[Pickett]

It's an interesting game, but I think a lot of people already knew the general strategy, hence it would of seemed unfair to answer and ruin the fun for everyone else. *shrugs*

Agreed...my dad used to frustrate me as a kid playing this game...because he would always end up winning. I finally figured out the strategy after a little while, except I didn't know anything about logical operators or anything like that...I just learned states that would work and ones that didn't. Finally, in high school, I revisited the game and figured out the logical/mathematical strategy to win. It is a great game to play with people that don't know the strategy, though :c)

Edited September 28, 2012 by Pickett