Mathematics for Computer Science

Chapter 6 Induction124

0 1 2 3

0

1

2

x

y

Figure 6.6 The Diagonally Moving Robot.

6.2.2 Invariant for a Diagonally-Moving Robot

Suppose we have a robot that moves on an infinite 2-dimensional integer grid. The
stateof the robot at any time can be specified by the integer coordinates.x;y/of
the robot’s current position. Thestart stateis.0;0/since it is given that the robot
starts at that position. At each step, the robot may move to a diagonally adjacent
grid point, as illustrated in Figure 6.6.
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/. We ask 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 means, of course, that
it can’t reach.1;0/. This all follows because evenness of the sum of coordinates is
preserved by transitions.
This once, let’s go through this preserved-property argument again carefully
highlighting where induction comes in. Namely, define the even-sum property of