# Can this game be won? **URL:** \ **Category:** Factual Questions\ **Created:** [January 27, 2004, 7:46am UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268 "2004-01-27T07:46:01Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![asomihite](https://avatars.discourse-cdn.com/v4/letter/a/848f3c/32.png) [@asomihite](https://boards.straightdope.com/u/asomihite)\ **Post date:** [January 27, 2004, 7:46am UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/1 "2004-01-27T07:46:01Z")
OK, so I tried quite a few times to win at this frustrating little game, and I’m beginning to think that it’s not possible. Could someone please check it out? I’d like to know how to win (if possible), and if it’s not possible, why isn’t it?? thanks ---
**Author:** ![asomihite](https://avatars.discourse-cdn.com/v4/letter/a/848f3c/32.png) [@asomihite](https://boards.straightdope.com/u/asomihite)\ **Post date:** [January 27, 2004, 7:47am UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/2 "2004-01-27T07:47:31Z")
Crap!! I forgot the link to the game. LOL here it is: [http://www.ebaumsworld.com/pearl.shtml](http://www.ebaumsworld.com/pearl.shtml) ---
**Author:** ![MysteryFellow63427](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@MysteryFellow63427](https://boards.straightdope.com/u/MysteryFellow63427)\ **Post date:** [January 27, 2004, 8:01am UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/3 "2004-01-27T08:01:23Z")
Well, I didn’t beat it in the two times I played it, but since the computer offers you a choice of whether or not to go first, we can deduce that it can be won. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [January 27, 2004, 10:46am UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/4 "2004-01-27T10:46:45Z")
This is known as the game of Nim, and if you get the choice of who goes first (as you do here) and play perfect strategy, you’re guaranteed to always win. I’ll try to illustrate the strategy with a game of my own: At the start, the rows are: 3 4 5 6 Write these numbers in binary: 011 100 101 110 Count the number of 1s in each column. If there’s an even number of 1s in each column, let your opponent go first; otherwise, you should go first. On each of your turns, remove a number of pearls so that we make there be an even number of 1s in each column (you can always do this if you play perfect strategy from the start). I have three 1s in the left column, 2 in the middle, and two on the right, so I have to work on the left column. So an acceptable move would be remove four from row 2, 3, or 4. I’ll take 4 from row 4: 011 100 101 010 The computer guy took 2 from row 1: 001 100 101 010 I’ll remove both from row 4: 001 100 101 000 He took 3 from row 3: 001 100 010 000 I’ll take 1 from row 2: 001 011 010 000 He took 1 from row 1: 000 011 010 000 I’ll take 1 from row 2: 000 010 010 000 He took 1 from row 2: 000 001 010 000 All right, once it gets your turn and there’s only one row with two or more left, you want to change your strategy. You want to remove either one or both of the pearls from the row with two, leaving an _odd_ number of 1s in the right column. Obviously, I should remove both from row three, and I win. Now tear him up! ---
**Author:** ![spingears](https://avatars.discourse-cdn.com/v4/letter/s/ebca7d/32.png) [@spingears](https://boards.straightdope.com/u/spingears)\ **Post date:** [January 27, 2004, 1:00pm UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/5 "2004-01-27T13:00:40Z")
Congratulations. I recognized it as Nim. The strategy has long been lost in the fog of time. **"You’re smarter that the average bear."** ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [January 27, 2004, 1:18pm UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/6 "2004-01-27T13:18:59Z")
As a general point, von Neumann proved that in any two-player game in which each player has only finitely many moves at each stage and in which draws are impossible, there is a winning strategy for one player. ---
**Author:** ![terd\_ferguson](https://avatars.discourse-cdn.com/v4/letter/t/8edcca/32.png) [@terd\_ferguson](https://boards.straightdope.com/u/terd_ferguson)\ **Post date:** [January 27, 2004, 5:13pm UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/7 "2004-01-27T17:13:16Z")
[Here](http://www.gametheory.net/html/games.html) is a link to a few game theory type games, including nim, if anyone is interested ---
**Author:** ![ccwaterback](https://avatars.discourse-cdn.com/v4/letter/c/df705f/32.png) [@ccwaterback](https://boards.straightdope.com/u/ccwaterback)\ **Post date:** [January 27, 2004, 11:08pm UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/8 "2004-01-27T23:08:11Z")
Here’s another NIM site. [http://www.cut-the-knot.org/nim\_st.shtml](http://www.cut-the-knot.org/nim_st.shtml) ---
**Author:** ![asomihite](https://avatars.discourse-cdn.com/v4/letter/a/848f3c/32.png) [@asomihite](https://boards.straightdope.com/u/asomihite)\ **Post date:** [January 29, 2004, 7:11pm UTC](https://boards.straightdope.com/t/can-this-game-be-won/226268/9 "2004-01-29T19:11:22Z")
Well, I had originally thought that it had to be possible to win seeing as how I was given the option to start or not, but then I thought maybe it was one of those deals where “that’s what I’m supposed to think.” Ya know? Thanks everyone for your replies and links. I’m off to look up something about writing it in binary, since I don’t really grasp that whole idea. I’m always learnin’ somethin’ here at the Straight Dope though!