Homework #1 (See EWD996)

*             *
*

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.)