A group of n friends (numbered 1 to n) plays the following game: Each of them takes a fair coin, flips it (getting a head or a tail with equal probability), and without looking at it glues it to her forehead. Then everyone is allowed to look at all other players, but all communication is forbidden during this phase. Finally, each of the players takes a piece of paper and writes down one of “head”, “tail”, and “pass”.
A player is correct if she writes down the coin side that is visible on her forehead. A player is wrong if she writes down the opposite side. A player that writes “pass” is neither right nor wrong. The players win the game if at least one of them is right and at the same time none of them is wrong.
Problem specification
One possible strategy is that one of the players guesses “head” and all others pass. With this strategy the players win in exactly 50 percent of all possible cases. Is there a better strategy for n = 3? If yes, find one.
Then, as the harder part of this problem, find optimal strategies for all n from 1 to 8, inclusive.
Strategy format specification
It can be proved that even if we allowed randomized strategies for all players, there would be an optimal deterministic strategy. Hence we will only consider deterministic strategies.
From player i’s point of view, there are 2n-1 different outcomes. Each outcome can be described by a string of n - 1 Hs (heads) and Ts (tails) – for each player from 1 to n except for i, write her coin side. To write down the strategy for player i, order all outcomes alphabetically, and for each of them write down H, T, or P (pass) – the action player i should take when she sees the corresponding outcome.
The strategy for the entire game consists of n lines, with line i containing the strategy for player i.
Input specification
There is no input.
Output specification
For the easy subproblem, find and submit any strategy for n = 3 for which the probability of winning is more than 50 percent. If there is no such strategy, submit any strategy for which the probability of winning is exactly 50 percent.
For the hard subproblem, find and submit optimal strategies for all n from 1 to 8, inclusive, in order. If there are multiple optimal strategies for a given n, pick any of them. (That is, the output for this data set should start with one line of length 1, two lines of length 2 each, three lines of length 4 each, etc.)
Example
This is a syntactically correct strategy for n = 3. In this strategy, player 1 always guesses “head”, player 3 always passes, and player 2 passes except for one case – when she sees a head on player 1 and a tail on player 3, she guesses “tail”.