Chapter 5 Induction144
Figure 5.10 Gehry’s new tile.Now it’s easy to check that if.x;y/ !.x^0 ;y^0 /is a legitimate robot move, then
v..x^0 ;y^0 // < v..x;y//. In particular,vis a strictly decreasing derived variable, so
Theorem 5.4.8 implies that the robot always get stuck—even though we can’t say
how many moves it will take until it does.
Problems for Section 5.1
Practice Problems
Problem 5.1.
Prove by induction that every nonempty finite set of real numbers has a minimum
element.
Problem 5.2.
Frank Gehry has changed his mind. Instead of the L-shaped tiles shown in fig-
ure 5.3, he wants to use an odd offset pattern of tiles (or its mirror-image reflection),
as shown in 5.10. To prove this is possible, he uses reasoning similar to the proof
in 5.1.5. However, unlike the proof in the text, this proof is flawed. Which part of
the proof below contains a logical error?
False Claim.The proof is by induction. LetP.n/be the proposition that for every
location of Bill in a 2 n 2 ncourtyard, there exists a tiling of the remainder with
the offset tile pattern.
False proof.Base case:P.0/is true because Bill fills the whole courtyard.