All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
No Repeats (Posted on 2006-09-13) Difficulty: 4 of 5
Andrew and Betty play a game in which they lay out a row of three coins, heads up. They take turns, begining with Andrew, turning over one of the coins at a time. They must not produce a pattern of heads and tails which has already occurred earlier in the game. The first person who cannot make a move is the loser.

1. If they each play as well as possible, who is the winner?

2. If the game were played with four coins instead of three, who would be the winner?

3. If the game is played with three coins but the player who cannot make a move is declared the winner, who wins now?

  Submitted by Charlie    
Rating: 4.5000 (2 votes)
Solution: (Hide)
Based on Enigma 1404, New Scientist, 12 August 2006.

1. The following table illustrates a winning strategy for the first player. From left to right, it shows the status of the pennies after each move. The columns headed by * show the state after the first player's move. The first two moves (one by each player) are arbitrary but do not lose generality, as any two coins to flip would serve equally as well.

     *       *       *       *
hhh hht htt ttt tht thh tth hth
hhh hht htt ttt tht thh
hhh hht htt ttt tth hth
hhh hht htt ttt

There are only two courses shown above for the game to follow. In both, the first player's second move is to turn the last remaining head to tails. At that point the second player will turn one of them back to heads (not the first, as that would result in a repetition), and the first player another. It could play out as in the first row above or the third row. The second and fourth rows merely verify that the final move shown there for the first player is a winning move--not that the game ends there.

The above may seem overly complicated, but it introduces the type of table that will be used for part 2, which is:

2.       *         *         *         *         *         *         *         *
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh tthh hthh htth ttth thth hhth
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh tthh hthh htth ttth
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh tthh hthh
                                                     -----------------------------
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh thth hhth htth ttth tthh hthh
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh thth hhth htth ttth
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh thth hhth
   hhhh hhht hhtt thtt tttt httt htht ttht thht thhh
                                           ---------------------------------------
   hhhh hhht hhtt thtt tttt httt htht ttht tthh hthh htth ttth thth hhth
   hhhh hhht hhtt thtt tttt httt htht ttht tthh hthh htth ttth
   hhhh hhht hhtt thtt tttt httt htht ttht tthh hthh
   hhhh hhht hhtt thtt tttt httt htht ttht
                                 -------------------------------------------------
   hhhh hhht hhtt thtt tttt httt htth ttth thth hhth
                                           ---------------------------------------
   hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh htht ttht thht thhh thth hhth
   hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh htht ttht thht thhh
   hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh htht ttht
   hhhh hhht hhtt thtt tttt httt htth ttth tthh hthh
   hhhh hhht hhtt thtt tttt httt htth ttth
   hhhh hhht hhtt thtt tttt httt
                       -----------------------------------------------------------
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth htth hhth thth thhh tthh hthh
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth htth hhth thth thhh
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth htth hhth
                                                     -----------------------------
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth thth hhth htth hthh tthh thhh
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth thth hhth htth hthh
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth thth hhth
                                                     -----------------------------
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth tthh hthh htth hhth thth thhh
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth tthh hthh htth hhth
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth tthh hthh
   hhhh hhht hhtt thtt thht ttht htht httt tttt ttth
                                           ---------------------------------------
   hhhh hhht hhtt thtt thht ttht htht httt htth hhth thth thhh tthh hthh
   hhhh hhht hhtt thtt thht ttht htht httt htth hhth thth thhh
   hhhh hhht hhtt thtt thht ttht htht httt htth hhth
   hhhh hhht hhtt thtt thht ttht htht httt
                                 -------------------------------------------------
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh tthh thhh thth hhth htth ttth
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh tthh thhh thth hhth
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh tthh thhh
                                                     -----------------------------
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth thth hhth
                                                               -------------------
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth tthh thhh thth hhth
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth tthh thhh
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh htth ttth
   hhhh hhht hhtt thtt thht ttht tttt httt htht hthh
                                           ---------------------------------------
   hhhh hhht hhtt thtt thht ttht tttt httt htth ttth thth hhth
                                                     -----------------------------
   hhhh hhht hhtt thtt thht ttht tttt httt htth ttth tthh thhh thth hhth
   hhhh hhht hhtt thtt thht ttht tttt httt htth ttth tthh thhh
   hhhh hhht hhtt thtt thht ttht tttt httt htth ttth
   hhhh hhht hhtt thtt thht ttht tttt httt
                                 -------------------------------------------------
   hhhh hhht hhtt thtt thht ttht tthh hthh htth hhth thth thhh
   hhhh hhht hhtt thtt thht ttht tthh hthh htth hhth
                                           ---------------------------------------
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth htth hhth thth thhh
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth htth hhth
                                                               -------------------
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth thth thhh
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt tttt ttth
                                                     -----------------------------
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt htth hhth thth thhh
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt htth hhth
   hhhh hhht hhtt thtt thht ttht tthh hthh htht httt
   hhhh hhht hhtt thtt thht ttht tthh hthh
   hhhh hhht hhtt thtt thht ttht
                       -----------------------------------------------------------
   hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh htht ttht thht thhh
   hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh htht ttht tttt httt
   hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh htht ttht
   hhhh hhht hhtt thtt thth hhth htth ttth tthh hthh
                                           ---------------------------------------
   hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht thht thhh tthh hthh
   hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht thht thhh
                                                               -------------------
   hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht tthh hthh
   hhhh hhht hhtt thtt thth hhth htth ttth tttt httt htht ttht
   hhhh hhht hhtt thtt thth hhth htth ttth tttt httt
   hhhh hhht hhtt thtt thth hhth htth ttth
   hhhh hhht hhtt thtt thth hhth
   hhhh hhht hhtt thtt

Again, rows that match those above them, but then do not continue the way those above continue, merely reiterate that that is a winning move for the first player. Again the first two moves are made arbitrarily with no loss of generality: hhhh hhht hhtt, as some two separate coins must be flipped as the first two moves.

3. Getting away from the above-type tables, let's use a tree:

           hhh
            |
       1   hht
            |
       2   htt_______________
            |                \\
       1   ttt               hth
            |  \\              |
       2   tht  tth          tth
            |    |  \\         |  \\
       1   thh  hth thh      thh  ttt
            |    |   |        |    |
       2   tth  --- tht      tht  tht
            |        |        |    |
       1   hth      ---      ttt  thh
            |                 |    |
       2   ---               ---  ---

The numbers at the left indicate which player's move resulted in the state shown on the given line for each path. It is player 1 who has the choice between ttt and hth on his second move. If he chooses hth, player 2 will certainly win this misere game, so he'll choose ttt. But then player 2 will choose tht, forcing the leftmost column and a win for her.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Puzzle Thoughts K Sengupta2023-06-23 01:54:28
QuestionDoes anyone know...JLo2006-09-17 16:45:41
It's obviousKit2006-09-17 12:23:34
SolutionWinning strategy for first partJLo2006-09-14 18:05:53
Some Thoughtsre: Solution -- not so fast!Steve Herman2006-09-14 14:53:29
Hints/TipsA way to solve thisOld Original Oskar!2006-09-13 13:15:19
SolutionSolutionvswitchs2006-09-13 13:13:42
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information