Nim

A version of the game Nim works as follows: You start with a collection of Skittles (the sweets), and players take it in turns to eat them, according to three rules:
1. You must eat at least one Skittle on your turn.
2. In any turn, all the Skittles you eat must be of the same colour.
3. If you eat the last Skittle, you lose.

Now suppose your opponent is feeling generous, and lets you decide who should go first. Assuming you want to win, how can you determine, given an arbitary collection of Skittles, whether it is better to go first or second?

This is a fairly well-known puzzle, so please don't shout out the answer if you know it already or have found it on the internet, try to work it out.

Ithink you should go first but i am not sure

Without thinking too much i'd say it doesn't matter. Simply because you have to eat skittles of the same color.

Originally posted by TheMaster37
Without thinking too much i'd say it doesn't matter. Simply because you have to eat skittles of the same color.

Well, no. In each turn you have to eat skittles of the same colour, but in different turns you can eat different-coloured skittles. This game is ALWAYS a win either for player 1 or player 2 (assuming optimal play) based on the inital setup, because it's deterministic, complete-information, and has bounded duration, leaving no possibility of a draw at the end. The question is, given the initial setup of skittles, does the player who goes first win or lose?

For example: if all the skittles are the same colour, player 1 wins by eating all but one of them, if there's more than one skittle; if there's only one, player 1 loses because he has to eat the last one.

Hmm, then i have to think harder. i'll get back to this one 🙂

Ok, in the case that all piles have 3 or more skittles in them i have solved it:

1 pile: Player 1 wins by taking all but one
2 piles: Player 2 wins by making sure both piles are equal in size until he can leave one skittle. If player 1 can do so, he wins.
3 piles: Player 1 takes away one entire pile, or leaves one skittle of a pile, depending the number of skittles in the two piles left, according to the strategy with 2 piles.
4 piles: player 2 wins by keeping piles equal in size, two by two. Or loses if the number of skittles in each pile is equal in his turn (strategy of two piles)

And so on, making the difference between even and odd number of piles.