Question 178
Spring is finally here in Cambridge, and it's time to mow our lawn. For the purpose of these problems, our lawn consists of little clumps of grass arranged in an $m \times n$ rectangular grid, that is, with $m$ rows running east-west and $n$ columns running north-south. To be even more explicit, we might say our clumps are at the lattice points
$$
\left\{(x, y) \in \mathbb{Z}^2 \mid 0 \leq x \lt n \text{ and } 0 \leq y \lt m \right\}.
$$
Our machinery consists of a fleet of identical mowbots (or "mobots" for short). A mobot is a lawn-mowing machine. To mow our lawn, we begin by choosing a formation: we place as many mobots as we want at various clumps of grass and orient each mobot's head in a certain direction, either north or east (not south or west). At the blow of a whistle, each mobot starts moving in the direction we've chosen, mowing every clump of grass in its path (including the clump it starts on) until it goes off the lawn.
Because the spring is so young, our lawn is rather delicate. Consequently, we want to make sure that every clump of grass is mowed once and only once. We will not consider formations that do not meet this criterion.
One more thing: two formations are considered "different" if there exists a clump of grass for which either (1) for exactly one of the formations does a mobot starts on that clump, or (2) there are mobots starting on this clump for both the formations, but they're oriented in different directions.
Prove that the maximum number of mobots you need to mow your lawn is $m+n-1$.
$$
\left\{(x, y) \in \mathbb{Z}^2 \mid 0 \leq x \lt n \text{ and } 0 \leq y \lt m \right\}.
$$
Our machinery consists of a fleet of identical mowbots (or "mobots" for short). A mobot is a lawn-mowing machine. To mow our lawn, we begin by choosing a formation: we place as many mobots as we want at various clumps of grass and orient each mobot's head in a certain direction, either north or east (not south or west). At the blow of a whistle, each mobot starts moving in the direction we've chosen, mowing every clump of grass in its path (including the clump it starts on) until it goes off the lawn.
Because the spring is so young, our lawn is rather delicate. Consequently, we want to make sure that every clump of grass is mowed once and only once. We will not consider formations that do not meet this criterion.
One more thing: two formations are considered "different" if there exists a clump of grass for which either (1) for exactly one of the formations does a mobot starts on that clump, or (2) there are mobots starting on this clump for both the formations, but they're oriented in different directions.
Prove that the maximum number of mobots you need to mow your lawn is $m+n-1$.