You die and the devil says he'll let you go to heaven if you beat him in a game. the devil sits you down at a round table. he gives himself and you a huge pile of quarters. he says "ok, we'll take turns putting quarters down, no overlapping allowed, and the quarters must rest on the table surface. the first guy who can't put a quarter down loses." the devil says he wants to go first.
being the smart programmer you are, you realize that if the devil goes first, he may automatically win. so you convince him to let you go first, which makes your day because you know you can't lose. what is your winning strategy?
Solution:
First, put the first quarter exactly in the center of the (perfectly circular) table.
Next, for each quarter the opponent places, place one directly opposite it. That is, place it so that the center of the table is halfway between your piece and the opponent's previous piece.
This will generate a completely symettric (about the center) layout of quarters on the table. This means that whenever the opponent selects a free space to place a quarter in, the space opposite is guaranteed to be free as well. Since we are always guaranteed an open space, we will never lose with this strategy (and thus win when there are finally no more spaces for the opponent to use).
No comments:
Post a Comment