There are 83 match sticks on the floor, and you have to clean them up

1.	There are 83 match sticks on the floor, and you have to clean them up with a friend. To make it fun (instead of the chore that it is), you decide to make a game out of it. You take turns to pick up the matches and put it back in the box. The rule is that each turn, the player must take at least one match stick, but not more than 4. Both you and your opponent can see the exact number of matches that were taken. The one who picks up the last match stick wins. You flip a coin and it’s decided that you get to make the first move.It looks like a game, but this "game" is actually flawed: Player 1 of this game has a sure-win strategy. Explain the theory behind the strategy, and write an algorithm that ensures you will win this game.
Answer» Answer: Nim is a popular strategy game the world over. Play is simple: Players take turns REMOVING counters (coins or matchsticks are perfect playing pieces) from any one of three piles. The loser is the person who is forced to take the last object. An equally popular variant is to have the person taking the last object win the game rather than lose. The strategic concepts for either version are essentially the same. Nim is one of the oldest strategy games known. Its origins date back to at least the 1500s and possibly earlier. It’s very similar to an ancient Chinese game USING only two piles of stones called Tsyan-shizi (Picking Stones). Although there are potentially dozens of starting arrangements, we’ll examine the one I was first shown by my father, an excellent Nim player. He arranged three piles of matchsticks. Pile A had 3 matchsticks, Pile B had 5 and Pile C had 7. He explained that the person who took the last matchstick would lose. My father also added the STIPULATION that players could only remove 1, 2 or 3 matchsticks at a time. I’ll EXPLAIN why he did this in a moment. The starting setup LOOKED like this:

There are 83 match sticks on the floor, and you have to clean them up with a friend. To make it fun (instead of the chore that it is), you decide to make a game out of it. You take turns to pick up the matches and put it back in the box. The rule is that each turn, the player must take at least one match stick, but not more than 4. Both you and your opponent can see the exact number of matches that were taken. The one who picks up the last match stick wins. You flip a coin and it’s decided that you get to make the first move.It looks like a game, but this "game" is actually flawed: Player 1 of this game has a sure-win strategy. Explain the theory behind the strategy, and write an algorithm that ensures you will win this game.

Answer»

Answer:

Nim is a popular strategy game the world over. Play is simple: Players take turns REMOVING counters (coins or matchsticks are perfect playing pieces) from any one of three piles. The loser is the person who is forced to take the last object. An equally popular variant is to have the person taking the last object win the game rather than lose. The strategic concepts for either version are essentially the same. Nim is one of the oldest strategy games known. Its origins date back to at least the 1500s and possibly earlier. It’s very similar to an ancient Chinese game USING only two piles of stones called Tsyan-shizi (Picking Stones).

Although there are potentially dozens of starting arrangements, we’ll examine the one I was first shown by my father, an excellent Nim player. He arranged three piles of matchsticks. Pile A had 3 matchsticks, Pile B had 5 and Pile C had 7. He explained that the person who took the last matchstick would lose. My father also added the STIPULATION that players could only remove 1, 2 or 3 matchsticks at a time. I’ll EXPLAIN why he did this in a moment. The starting setup LOOKED like this:

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment