Homework #1 (See EWD996)
Show that, for any finite set of grid points in the plane, we can colour each of the points either red or blue such that on each grid line the number of red points differs by at most 1 from the number of blue points.
Homework #1 (See EWD996)
Show that, for any finite set of grid points in the plane, we can colour each of the points either red or blue such that on each grid line the number of red points differs by at most 1 from the number of blue points.
* *
*
A snake is a non-empty sequence or cycle of distinct grid points to be coloured such that
(i) adjacent points in the snake can be connected by a grid line such that along the snake horizontal and vertical connections alternate, and
(ii) a sequential snake is maximal in the sense that neither endpoint can be further connected.
We observe that, if there are points to be coloured, a snake can be formed: start with a point and extend in both directions the snake as long as possible; when no new points can be added to the snake, it is made into a cycle, if that is possible.
Through each endpoint of a sequential snake passes a grid line containing an odd number of “snake points”; on account of (ii), these lines contain no further points to be coloured. All other grid lines contain their snake points partitioned into pairs of “snake neighbours”.
Since on account of (i) each cycle contains an even number of points, we can colour the points along a snake alternately red and blue, and we do so, thereby only creating differences of 1 on grid lines with no uncoloured points left.
The algorithm that produces a colouring with the required properties consists of repeatedly —i.e., as long as not all points of the given set have been coloured— creating a snake and then colouring it. The invariants of this algorithm are
(iii) on a grid line that contains an uncoloured point the number of red points equals the number of blue ones
(iv) on no grid line the number of red points differs by more than 1 from the number of blue ones.
Note The above argument has a bit more structure than the one in EWD996, which did not contain the concept of a snake. EWD996, however, was free from rabbits. (End of note.)
Austin, 9 October 1996
(Written manu sinistra with a
Parker roller ball, Fine.)
prof. dr. Edsger W. Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188
USA