Flipping Exactly k Coins at Once

In this section, we characterize when the magician can equalize n coins by flipping exactly k coins in each
move. Naturally, we must have 0 < k < n, because both 0-flip and n-flip moves cannot equalize a notalready- equal configuration. Also, as observed in the previous section, we cannot have both n and k even, because then we could never change an odd-parity configuration into the needed even parity of an all-equal configuration. We show that these basic conditions suffice for the magician: Theorem 8 The magic trick with k-flip moves can be performed if and only if 0 < k < n and either n or k is odd. The optimal solution sequence uses exactly 2n−1 − 1 moves in the worst case. A lower bound of 2n−1 − 1 follows in the same way as Section 2. Again we can view the trick on the n-dimensional hypercube, where 0 represents a bit unchanged from its initial configuration and 1 represents a changed bit. The difference is that now moves (edges) connect two configurations that differ in exactly k bits. The lower bound of 2n−1 − 1 follows because we need to visit every bit string or its complement among 2n possibilities. Our construction of a (2n−1 −1)-move solution is by induction on n. If k is even, we can consider only odd values of n. The base cases are thus when n = k + 1 for both even and odd k. The n = k + 1 case has k = n − 1, so it is effectively equivalent to k = 1 from Section 2. We will, however, need to prove some additional properties about this solution. It seems difficult to work with general solutions for smaller values of n, so we strengthen our induction hypothesis. Given a solution to a trick, we call a configuration destined for heads if the solution transforms that configuration into the all-heads configuration (and never all-tails), and destined for tails if it transforms into all-tails (and never all-heads). (Because our solutions are always optimal length, they only ever reach one all-heads configuration or one all-tails configuration, never both, even if run in entirety.) We call a transformation destiny-preserving if every configuration on n coins has the same destiny before and after applying the transformation. A transformation is destiny-inverting if every configuration on n coins has the opposite destiny before and after applying the transformation. Now the stronger inductive statement is the following: 1. for nk even, flipping the first j coins for even j < k preserves destiny, while flipping the first j coins for odd j < k inverts destiny; and 2. for nk odd, flipping the first j coins for even j < k inverts destiny, while flipping the first j coins for odd j < k preserves destiny, and flipping coins 2, 3, . . . , k preserves destiny. To get this stronger induction hypothesis started, we begin with the base case: Lemma 9 For any k > 0, the k-flip trick with n = k + 1 coins has a solution sequence of length 2k − 1
such that flipping the first j coins for even j < k preserves destiny, while flipping the first j coins for odd j < k inverts destiny. Proof: The construction follows the Gray code of Section 2. That flip sequence, ignoring the first coin, can be described recursively by Gk = Gk−1, “flip the (n − k + 1)st coin”, Gk−1. To flip n − 1 coins in each move, we invert this sequence into ¯G k = ¯Gk−1, “flip all but the (n − k + 1)st coin”, ¯Gk−1. In the base case, G0 = ¯G0 = ;. Validity of the solution follows as in Section 2; indeed, for any starting configuration, the number of moves performed before the configuration becomes all-heads or all-tails is the same in sequences Gk and ¯Gk. Every move flips the first coin, so the destiny of a configuration is determined by its parity and the parity of n: if n and the number of coins equal to the first coin (say heads) have the same parity, then the configuration is destined is that value (heads); and if n and the (heads) count have opposite parity, then the destiny is the opposite value (tails). To see why this is true, consider the hypercube viewpoint where 0s represent coins matching the initial configuration and 1s represent flipped coins in an execution of Gk (not ¯Gk). Then, at all times, the number of 1 bits in the configuration has the same parity as the number of steps made so far. At the same time, every move in ¯Gk flips the first coin, so the first coin in the current configuration matches its original value precisely when there have been an even number of steps so far. Thus, when we reach a target configuration of all-heads or all-tails, it will match the original first coin precisely if there have been an even number of steps so far, which is equivalent to there being an even number of 1 bits in the Gk view, which means that the initial and target configurations differ in an even number of bits. In this case, the initial and target configurations have the same parity of coins equal to their respective first coins; but, in the target configuration, all coins match the first coin, so in particular n has the same parity as the number of coins equal to the first coin. We have thus shown this property to be equivalent to the target configuration matching the initial first coin. It remains to verify the flipping claims. Flipping the first j coins for even j < k preserves the parity of the number of heads as well as the number of tails, but inverts the first coin, so inverts the destiny. Flipping the first j coins for odd j < k changes the parity of the number of heads as well as the number of tails, and inverts the first coin, which together preserve the destiny. 2 With this base case in hand, we complete the induction to conclude Theorem 8. In the nonbase case, n > k + 2. There are three cases to consider:
Case 1: Both n and k are odd. By induction, we obtain a solution sequence _0 of length 2n−2 − 1 for
n0 = n − 1 satisfying the destiny claims. We view _0 as acting on only the last n − 1 of our n coins. Then
we construct a solution _ for n as follows:
_ = _0, “flip the first k coins”, _0.
This solution has length |_| = 2 |_0| + 1 = 2n−1 − 1.
Next we prove that sequence _ solves the trick. Consider any configuration on n coins, and assume by
symmetry that the last n − 1 of its coins are destined for heads in _0. If the first coin is also heads, then the
magician arrives at the all-heads configuration within the first _0 prefix of _. If the first coin is tails, then
the _0 prefix will not complete the trick, at which point the magician flips the first k coins. This move has
the effect of flipping the first coin to heads as well as flipping the first k − 1 of the _0 subproblem, which is
destiny-preserving because k−1 is even and (n−1)k is even. Therefore, during the second _0, the magician
will arrive at the all-heads configuration.
Now we verify the destiny claims. Note that the destiny of a configuration in _ equals the destiny of
the last n − 1 coins in _0, so we can apply induction almost directly. Flipping the first j coins for even
j < k flips the first j − 1 of the last n − 1 coins, which inverts destiny by induction because j − 1 is even
and (n − 1)k is even. Similarly, flipping the first j coins for odd j < k preserves destiny by induction.
Finally, flipping coins 2, 3, . . . , k flips the first k − 1 coins of the last n − 1 coins, which preserves destiny
by induction because k − 1 is even.
Case 2: For n even and k odd, by induction we again obtain a solution sequence _0 of length 2n−2 − 1
for n0 = n − 1, viewed as acting on only the last n − 1 coins. We construct a solution _ for n as follows:
_ = _0, “flip coins 1, 3, 4, . . . , k + 1”, _0.
Again _ has length 2n−1−1. Flipping coins 1, 3, 4, . . . , k+1 has the effect of flipping the first 2, 3, . . . , k of
the last n − 1 coins, which by induction is destiny-preserving because (n − 1)k is odd. Thus, if the destiny
of _0 does not match the first coin, then it will match the newly flipped first coin during the second _0. As
before, destiny in _ matches destiny in _0 on the last n − 1 coins. Flipping the first j coins for even j < k
flips the first j − 1 of the last n − 1 coins, which preserves destiny by induction because j − 1 is odd and
(n − 1)k is odd. Similarly, flipping the first j coins for odd j < k inverts destiny by induction.
Case 3: For n odd and k even, by induction we obtain a solution sequence _0 of length 2n−3 − 1 for
n0 = n − 2, which we view as acting on only the last n − 2 coins. Then we construct a solution _ for n as
follows:
_ = _0, “flip the first k coins”, _0, “flip coins 1, 3, 4, . . . , k + 1”, _0, “flip the first k coins”, _0.
This solution has length |_| = 4 |_0|+3 = 2n−1 −1. Restricting attention to the first two coins, _ first flips
both coins, then flips the first coin only, then flips both coins again. Together these enumerate all possibilities
for the first two coins. Restricting to the last n − 2 coins, these moves correspond to flipping the first k − 1
coins, coins 2, 3, . . . , k, and again the first k − 1 coins. By induction, all three of these operations preserve
destiny because k − 1 and (n − 2)k are odd. Therefore all three executions of _0 produce the same target
configuration (all-heads or all-tails) which will eventually match one of the combinations of the first two
coins. Flipping the first j coins for even j < k flips the first j − 2 of the last n − 2 coins, which preserves
destiny by induction because j − 2 is even and (n − 1)k is odd. Similarly, flipping the first j coins for odd
j < k inverts destiny by induction.
This concludes the inductive proof of Theorem 8 .