__Jan van de Snepscheut's tiling problem__

When a 6×6 square is covered by 18 2×1 dominoes, each domino is "cut" into 2 unit squares by one of the (5 + 5 =) 10 grid lines. Show that there is a grid line that cuts no domino.

__Proof__ Define for each grid line its "`cut frequency`" as the number of dominoes it cuts. For an arbitrary grid line we observe

(i) it divides the 6×6 square into two rectangles, each of an *even* number of unit squares.

(ii) each domino it cuts covers in both rectangles 1, i.e. an *odd* number of unit squares.

(iii) each domino it does not cut covers in both rectangles an *even* number of unit squares

From (i), (ii), (iii) we conclude

(iv) `cut frequencies` are even.

Because 10 grid lines cut 18 dominoes, the average `cut frequency` equals 1.8. Hence —on account of the generalized pigeon-hole principle—

(v) the minimum `cut frequency` is ≤ 1.

From (iv) and (v) we conclude that the minimum `cut frequency` equals 0, which proves the theorem. (End of proof.)