Alice and Bob take turns to play a game with four coins on the corners of a square table covered by four identical tumblers. At her turn, Alice rotates the table in the blink of an eye by a random amount and presents it to Bob. Then Bob gets to choose any two tumblers to reveal the coins underneath; for each of the revealed coins, he may choose its configuration: heads up or tails up; he then covers both the coins that he just inspected with tumblers. At any moment, if all four coins become either four heads or four tails, Bob wins! Does Bob have a deterministic winning strategy? If not, why?

Followup: What if we have 6 tumblers on a hexagonal table and Bob gets to pick any 4 tumblers in each turn? Does Bob have a deterministic winning strategy? [Generalize the solution to n = 2k tumblers at the corners of an n-gon.]

A video on FaceBook.

n = 4: Bob wins in 5 turns:

Turn 1: Choosing two diagonally opposite coins. Make them heads.

Turn 2: Choose two adjacent coins. Make them heads.

Turn 3: Choose two diagonal coins. These two coins can't be both tails. If both are heads, turn any one of them to tails. Otherwise, turn the tail into head.

Turn 4: Choose two adjacent coins. Flip them.

Turn 5: Choose two diagonal coins. Flip them.

n = 4 (alternate solution): Let N denote 'choose (N)eighboring tumblers' and let O denote 'choose (O)pposite tumblers'.

1. With NO or ON as the first two turns, and "flip both coins to heads" at each turn, B wins or we reach a configuration with three heads and one tail.
2. With N or O in the third turn, and "flip any one", we either win or we reach a configuration with two heads and two tails.
3. With a NO or ONO in subsequent turns and "flip both" policy, Bob is guaranteed to win.

n = 6: Solution in brief: After any 2 non-identical 4-point selections and "flip to H", we reach HHHHHT. Then pick two opposite sides. If we uncovered T, flip it to reach HHHHHH and win. Otherwise, make one side HH and the other side TT to reach HHHTTT. Next pick three adjacent sides. If we overlapped with HHH or TTT, then flip these segments to win! Otherwise, we're looking at ?HHTT? where the ?'s are known (guaranteed to be H on the left and T on the right). So we can transform this into HTHTHT and we win in the next turn by picking any 3 points not connected by a side.

n is even: The above solution can be generalized to even n-gons.

1. By picking any 2 non-identical (n-2) point selections in the first two turns, and turning all selected coins to heads, we either win or get n-1 heads and 1 tail.
2. In the next turn, choose all points except any two diametrically opposite points. If any of these is tail, flip that tail to head to win. Otherwise, the 2 non-selected points are head and tail, respectively. Turn one streak of adjacent (n-2) / 2 selected points into heads; turn the other streak into tails. At this point, exactly half the coins are heads and they are adjacent to each other.
3. Next, pick n-2 adjacent points. If any of these is tail, flip it to heads and win. Otherwise, the selected coins are composed of two strings of (n-2) / 2 heads and (n-2) / 2 tails. We are gauranteed that the two unselected coins are of opposite polarity. Plus we are guaranteed that the unselected coin next to the string of tails is a tail, and the unselected con next to the string of heads is a head. Using this information, we can convert all n coins into an alternating sequence of heads and tails.
4. Finally, pick only n/2 coins in alternating positions and flip all of them to win!

n is odd: How may we prove that a solution for odd n does not exist?