6.4. Strong Induction vs. Induction vs. Well Ordering 147
The above scenario can be nicely modelled as a state machine in which each state
is a pair consisting of the “ant’s memory” and “everything else”—for example,
information about where things are on the grid. Work out the details of such a
model state machine; design the ant-memory part of the state machine so the ant
will eat all the crumbs onanyfinite path at which it starts and then signal when it
is done. Be sure to clearly describe the possible states, transitions, and inputs and
outputs (if any) in your model. Briefly explain why your ant will eat all the crumbs.
Note that the last transition is a self-loop; the ant signals done for eternity. One
could also add another end state so that the ant signals done only once.
Problem 6.14.
Suppose that you have a regular deck of cards arranged as follows, from top to
bottom:
A~ 2 ~:::K~A 2 :::KA| 2 |:::K|A} 2 }:::K}Only two operations on the deck are allowed:inshufflingandoutshuffling. In
both, you begin by cutting the deck exactly in half, taking the top half into your
right hand and the bottom into your left. Then you shuffle the two halves together
so that the cards are perfectly interlaced; that is, the shuffled deck consists of one
card from the left, one from the right, one from the left, one from the right, etc. The
top card in the shuffled deck comes from the right hand in an outshuffle and from
the left hand in an inshuffle.
(a)Model this problem as a state machine.(b)Use the Invariant Principle to prove that you can not make the entire first half
of the deck black through a sequence of inshuffles and outshuffles.
Note: Discovering a suitable invariant can be difficult! The standard approach is
to identify a bunch of reachable states and then look for a pattern, some feature that
they all share.^6
Problem 6.15.
Let’s extend the jug filling scenario of Section 8.1.3 to three jugs and a receptacle.
Suppose the jugs can holda,b, andcgallons of water, respectively.
The receptacle can be used to store an unlimited amount of water, but has no
measurement markings. Excess water can be dumped into the drain. Among the
possible moves are:
(^6) If this does not work, consider twitching and drooling until someone takes the problem away.