Given is an table with distinct unit squares marked with a ring (). Juku wishes to connect these rings into pairs using (possibly curved) lines in a way that meets the following conditions:
(1) Each line begins from some ring and ends in some other ring;
(2) Every two unit squares visited by the same line one after another have a common side;
(3) No two lines (including their endpoints) visit a common unit square;
(4) No line visits the same unit square more than once.
Prove that the sum of the numbers of unit squares visited by the lines is either always even or always odd, no matter of how Juku draws the lines.
Solutions — 2
Solution 1
Color the unit squares black and white in such a way that unit squares with a common side are of different color. Each line goes from a black square to a white square and vice versa; thus whenever the endpoints of a line are in squares of equal color, the line visits an odd number of squares, and otherwise, the line visits an even number of squares. Let squares out of the ones marked with ring be black. Among the lines drawn by Juku, let lines have both endpoints in black squares, lines have both endpoints in white squares, and lines have endpoints in squares of different color. Then and , implying . Hence the numbers and have equal parity.
Let the numbers of squares visited by the lines sum up to . Then can be expressed as the sum of odd numbers and even numbers, whence and have equal parity. Consequently, and have equal parity. Since does not depend on the way Juku draws the lines, must be always even or always odd.
Solution 2
Every line can be considered as a sequence of unit movements, each having one of four possible directions (right, left, up, down). Thus the number of unit squares visited by a line is where is the number of unit movements. Let be the numbers of unit movements of the line in different directions (right, left, up and down, respectively); then the end of the line is located units to the right and units upwards from the beginning of the line. Since and have equal parity, as do and , the numbers and have equal parity.
Let the line start in column and row and end in column and row . Then and , whence the number of unit squares visited by the line has the same parity as the number . But the latter has the same parity as . Summing up these numbers for all lines, we obtain that the total number of unit squares visited by the lines has the same parity as the number where and are the sum of all column numbers and all row numbers, respectively, of the squares containing a ring. But this sum does not depend on the way how Juku connects the rings, which proves the desired claim.