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