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., .
- Turn 1: Reveal n-3 adjacent [R...RCCC] and turn all to heads. This yields [h...hxxx].
- Turn 2: Reveal [R...RCRCC] and turn all to heads. This yields (i) [h...hxx], (ii) [h...hxhx], or (iii) [h...hx]. If not won, (iii) is [h...ht]
- Turn 3: Reveal [R...RCRRCC] and turn all to heads. This yields (i) win, [h...ht], or [h...hxx], (ii) win or [h...ht], (iii) win or [h...ht].
- Turn 4: Reveal [R...RCRCRC] and turn all to heads. If not won, then [h...ht] stays the same and [h...hxx] becomes [h...ht] as well.
- Turn 5: Reveal [R...RCRCC]. If you see t, you win. Otherwise flip singleton. This creates [h...htt] or [h...htht].
- Turn 6:
- If n=4k, reveal . If you see "tt" you win. If you see "ht" or "th" look at both adjacent and you will either find "tht" or "tt". In either case you win looking at 2k+2=n/2+2 cups which is ≤n-3 provided n≥10. If you have not found a t, then you are in the [h...htt] case and you require at most k+1 further reveals to find the "tt" pair, i.e., 3k+3=3n/4+3 peeks which is ≤n-3 if n≥24.
- If n=4k+2, reveal . If you see "tt" you win. If you see "ht" or "th" look at both adjacent and you will either find "tht" or "tt". In either case you win looking at 2k+4=n/2+3 cups which is ≤n-3 provided n≥12. If you have not found a t, then you are in the [h...htt] case and you require at most k+1 further reveals to find the "tt" pair, i.e., 3k+5=3(n-2)/4+5 peeks which is ≤n-3 if n≥36.