Alice and Bob have a large bag of coins which they use to play a game called HT-2. In this game, Alice and Bob take turns placing one coin at a time on the table, each to the right of the previous one; thus they build a row of coins that grows to the right. Alice always places the first coin. Each coin is placed head-up (H) or tail-up (T), and cannot be flipped or moved once it has been placed.
A player loses the game if he or she places a coin that results in two adjacent coins having the same pattern of heads and tails as another adjacent pair somewhere in the row (reading a pattern from left to right). For example, Bob has lost this game by producing a second instance of HT (where \(a\) and \(b\) denote coins placed by Alice and Bob respectively): \[\begin{array}{cccccc} a&b&a&b&a&b\\ H&H&T&T&H&T \end{array}\] and Alice has lost this game by producing a second instance of TT (overlapping pairs can count as repeats): \[\begin{array}{ccccc} a&b&a&b&a\\ T&H&T&T&T \end{array}\]
What is the smallest number of coins that might be placed in a game of HT-2 (including the final coin that causes a player to lose)? What is the largest number? Justify each answer.
Bob can always win a game of HT-2 by adopting a particular strategy. Describe the strategy.
For any positive integer \(n\), there is a game HT-\(n\) with the same rules as HT-2, except that the game is lost by a player who creates an unbroken sequence of \(n\) heads and tails that appears elsewhere in the row. For example, Bob has lost this game of HT-3 by producing a second instance of THT: \[\begin{array}{cccccccc} a&b&a&b&a&b&a&b\\ H&H&T&T&H&T&H&T \end{array}\]
- Suppose \(n\) is odd, and Bob chooses to play by always duplicating Alice’s previous play (and Alice knows that this is Bob’s strategy). Show that Alice can always win.
In these games, a maximum time of one minute is allowed for each turn.
- Can we be certain that a game of HT-6 will be finished within two hours? Justify your answer.
