5.4. State Machines 163
(b)Use the Invariant Principle to prove that you cannot make the entire first half
of the deck black through a sequence of inshuffles and outshuffles.
Note: Discovering a suitable invariant can be difficult! This is the part of a
correctness proof that generally requires some insight, and there is no simple recipe
for finding invariants. A standard initial approach is to identify a bunch of reachable
states and then look for a pattern—some feature that they all share.
Problem 5.36.
Prove that the fast exponentiation state machine of Section 5.4.5 will halt after
dlog 2 neC 1 (5.23)transitions starting from any state where the value ofzisn 2 ZC.
Hint:Strong induction.
Problem 5.37.
Nim is a two-person game that starts with some piles of stones. A player’s move
consists of removing one or more stones from a single pile. Players alternate moves,
and the loser is the one who is left with no stones to remove.
It turns out there is a winning strategy for one of the players that is easy to carry
out but is not so obvious.
To explain the winning strategy, we need to think of a number in two ways: as
a nonnegative integer and as the bit string equal to the binary representation of the
number—possibly with leading zeroes.
For example, theXORofnumbersr;s;:::is defined in terms of their binary repre-
sentations: combine the corresponding bits of the binary representations ofr;s;:::
usingXOR, and then interpret the resulting bit-string as a number. For example,
2 XOR 7 XOR 9 D 12because, takingXOR’s down the columns, we have
0 0 1 0 (binary rep of 2)
0 1 1 1 (binary rep of 7)
1 0 0 1 (binary rep of 9)
1 1 0 0 (binary rep of 12)This is the same as doing binary addition of the numbers, but throwing away the
carries (see Problem 3.5).