Friday, August 31, 2007

Matches Piles Puzzle

The matches piles puzzle , actually a game that is very widely played

The game is as follows:
Make three piles of matches, the first pile containing three matches
the second containing four matches
the third containing five matches...

Each player can pick any number of matches from any but one of the pile on his/her turn. For example player 1 picks 1 match from pile 1 , player 2 picks 3 from pile 2 etc...
Both the players keep on picking the matches one by one on their turns. The one picking the last match will be the looser

Given that all the players play a perfect game, who amongst the player starting first and second will win the game!!

1 comment:

  1. if the number of matches in all boxes is same , like (2,2,2) or (3,3,3) , then the first person to pick will definitely lose.
    otherwise , he can always win.

    proof is simple by induction. we can see that (0,1,1) (1,1,1) , (0,1,2) (1,1,2) (1,2,2) are all winning positions for the first player.
    so if the first player is on (2,2,2) - he can only go to one of these in 1 step and then its the second players turn who will def. win
    similarly if (a,b,c) a>=b >=c is the starting position with a>c , the the first player can simply pick (a-c) matches from the first pile and (b-c) matches from the second pile to go to (c,c,c). now its 2nd persons turn who def. looses.


Subscribe via email

Enter your email address:

Delivered by FeedBurner