Flipping More Coins At Once

Returning to the magic trick of flipping n coins to become all the same, another generalization is to allow
the magician the additional flexibility of flipping more than one coin at once. The number of coins flipped
per move might be a constant value (as considered in the next section), or might change from move to move
. In either case, we let k denote the number of coins flipped in a move.
In this section, we consider what happens when the spectator gets to choose how many coins the magician
must flip in each move. Obviously, if n is even, then the spectator must choose odd values for k, or
else the magician could never get out of the odd parity class. But even then the magician is in trouble. We
provide a complete answer to when the magician can still succeed:
Lemma 6 If n _ 5, the magician is doomed.
Proof: The spectator uses the following strategy: if the distance between the current configuration and the
all-heads or all-tails configuration is 1, then the spectator tells the magician to flip three coins. Otherwise,
the spectator tells the magician to flip one coin. Because n _ 5, being at distance 1 from one target
configuration means being at distance at least 4 from the other target configuration, and 4 > 3, so the
magician can never hit either target configuration. The spectator always says odd numbers, so this strategy
satisfies the constraint when n is even. 2
Lemma 7 If n = 3 or n = 4, the magician can succeed.
Proof: As mentioned above, flipping k or n − k coins are dual to each other. For n = 3 or n = 4, the
spectator can only ask to flip 1 or n − 1 coins. Thus the magician effectively has the same control as when
flipping one coin at a time. More precisely, if the spectator says to flip 1 coin, the magician flips the next
coin in the k = 1 strategy. If the spectator says to flip n−1 coins, the magician flips all coins except the next
coin in the k = 1 strategy. This transformation has effectively the same behavior because the two targets are
bitwise negations of each other. 2
Despite this relatively negative news, it would be interesting to characterize the sequences of k values for
which the magician can win. Such a characterization would provide the magician with additional flexibility
and variability for the equalizing trick. In the next section, we make partial progress toward this goal by
showing that the magician can succeed for most fixed values of k.