A Game of Cups and Coins
We will use the following notation: h = heads, t = tails, x = unknown, R=revealed, C=conceiled. Repeating patterns will be denoted in the form . This is a pattern of k values repeated r times. E.g., .
Let us consider .
- Turn 1: Flipping every second coin to heads gives .
- Turn 2: Flipping every second pair to heads gives .
- Turn 3: Lift every second cup. If you see a tails, turn all tails to heads and win. Otherwise, turn all heads to tails and obtain .
- Turn 4: Flip four consecutive coins. From the position of at least one heads, lift every second cup. Turn all to tails. This gives .
- Turn 5: Flip every second pair of cups and turn all to tails. This either wins the game or leaves .
- Turn 6: Flip every second cup. If you find the remaining heads, you win. Otherwise flip all to heads giving you .
- Turn 7: Flip every second pair. If all you see are "ht" or "th" combinations, flip all tails to heads giving . If, on the other hand, you find the "hh" combination, flip the "h" corresponding to the other tails to tails. This leaves . In this case, skip to Turn 11.
- Turn 8: Keep flipping over consecutive cups until you find the first tails. Then you can find all tails and flip them to heads. For this you will need at most 6+m cups.