Review question

# Who should win the game HT-2? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R7878

## Question

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}$

1. 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.

2. 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}$

1. 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.

1. Can we be certain that a game of HT-6 will be finished within two hours? Justify your answer.