Posers and Puzzles

Posers and Puzzles

  1. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    08 May '04 11:08
    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.
  2. The moral highground
    Joined
    06 May '04
    Moves
    34552
    08 May '04 22:58
    Ithink you should go first but i am not sure
  3. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    10 May '04 21:45
    Without thinking too much i'd say it doesn't matter. Simply because you have to eat skittles of the same color.
  4. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    11 May '04 12:45
    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.
  5. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    13 May '04 13:23
    Hmm, then i have to think harder. i'll get back to this one 🙂
  6. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    13 May '04 13:57
    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.
Back to Top