Question 80
In a one-player game, the player begins with $4m$ fair coins. On each of $m$ turns, the player takes 4 unused coins, flips 3 of them randomly to heads or tails, and then selects whether the 4th one is heads or tails (these four coins are then considered used). After $m$ turns, when the sides of all $4m$ coins have been determined, if half the coins are heads and half are tails, the player wins; otherwise, the player loses.
Prove that whenever the player must choose the side of a coin, the optimal strategy is to choose heads if more coins have been determined tails than heads and to choose tails if more coins have been determined heads than tails.
Prove that whenever the player must choose the side of a coin, the optimal strategy is to choose heads if more coins have been determined tails than heads and to choose tails if more coins have been determined heads than tails.