Mathematics for Computer Science

Chapter 5 Induction132

0 1 2 3

0

1

2

x

y

Figure 5.8 The Diagonally Moving Robot.

To be precise, the robot’s transitions are:

f.m;n/!.m ̇1;n ̇1/jm;n 2 Zg:

For example, after the first step, the robot could be in states.1;1/,.1;1/,.1;1/,
or.1;1/. After two steps, there are 9 possible states for the robot, includ-
ing.0;0/. The question is, can the robot ever reach position.1;0/?
If you play around with the robot a bit, you’ll probably notice that the robot can
only reach positions.m;n/for whichmCnis even, which of course means that it
can’t reach.1;0/. This follows because the evenness of the sum of the coordinates
is preserved by transitions.
This once, let’s go through this preserved-property argument, carefully highlight-
ing where induction comes in. Specifically, define the even-sum property of states
to be:
Even-sum..m;n//WWDŒmCnis evenç:

Lemma 5.4.1. For any transition,q ! r, of the diagonally-moving robot, if
Even-sum(q), then Even-sum(r).

This lemma follows immediately from the definition of the robot’s transitions:
.m;n/!.m ̇1;n ̇1/. After a transition, the sum of coordinates changes by