Mathematics for Computer Science

(Frankie) #1

6.4. Strong Induction vs. Induction vs. Well Ordering 143


with at least one previously-placed square and no squares overlapped. Eventually,
he arrived at the shape in Figure 6.9 (c). He realized that the length of the periphery
of this shape was 36, which is again an even number.
Our plucky porcine pal is perplexed by this peculiar pattern. Use induction on
the number of squares to prove that the length of the periphery is always even, no
matter how many squares Theory Hippotamus places or how he arranges them.


(a) (b) (c)

Figure 6.9 Some shapes that Theory Hippotamus created.

Problems for Section 6.2


Practice Problems


Problem 6.9.
Which states of the Die Hard 3 machine below have transitions to exactly two
states?


Die Hard Transitions


  1. Fill the little jug:.b;l/!.b;3/forl < 3.

  2. Fill the big jug:.b;l/!.5;l/forb < 5.

  3. Empty the little jug:.b;l/!.b;0/forl > 0.

  4. Empty the big jug:.b;l/!.0;l/forb > 0.

Free download pdf