Tiling with Dominoes

Date: 08/06/2001 at 12:09:42
From: Ethan Street
Subject: Math Contest Question

I looked at this question and my initial reaction was that it didn't 
seem very hard. But when I tried to do it, I had no idea where to 
begin! Here's the problem:

A 6 square by 6 square board is tiled completely with 18 2x1 dominos. 
Prove that at least one horizontal or vertical line can be drawn along 
the edges of the dominos that divides the board into 2 regions, 
without cutting any dominos in half.

This is paraphrased, but it is the same basic principle. How do you 
do it? I've tried devising a way to map out the positions of dominos 
by assigning coordinate values to the missing edge between the 2 
squares of the dominos. With this I tried coming up with rules that 
govern the density of vertical and horizontal dominos. This, not 
surprisingly, didn't work. Help!

Date: 08/07/2001 at 11:52:25
From: Doctor Jubal
Subject: Re: Math Contest Question

Hi Ethan,

Thank you for writing Dr. Math.

You did have the right idea to try to figure out how many horizontal 
and how many vertical dominoes you would need to make such a tiling.  
The description you gave of your work isn't specific enough for me to 
figure out whether what you were trying could have led to a proof, but 
let me try to set you on a path that does lead to a proof.

There are five vertical lines and five horizontal lines that the 6x6 
tiling might be divided along. The vertical lines are the lines 
between the first and second columns, between the second and third 
columns, etc., and the horizontal lines are the lines between the 
first and second rows, between the second and third rows, etc.

If the tiling can't be divided along any of these lines, then there 
must be at least one horizontal domino blocking each of the vertical 
lines, and one vertical domino blocking each of the horizontal lines.  
Therefore, the tiling must contain at least five vertical and five 
horizontal dominoes.

Also, each row contains an even number of squares (6). Each horizontal 
domino occupies two squares in the same row, so the number of squares 
in each row occupied by horizontal dominoes is even. The difference 
between any two even numbers is also even, so the number of squares in 
each row occupied by vertical dominoes is even. Since each vertical 
domino only takes up one square in a single row, that means each row 
must contain an even number of vertical dominoes.

In the same way, each column must contain an even number of horizontal 
dominoes.

Can you combine the two theorems we've proven so far:

1) Any tiling that can't be divided along a vertical or horizontal 
line must have at least one horizontal domino blocking each of the 
five vertical lines between the columns, and at least one vertical 
domino blocking each of the five horizontal lines between the rows.

2) Each row must contain an even number of vertical dominoes, and each 
column must contain an even number of horizontal dominoes.

to show that if there was a tiling that couldn't be divided along any 
of the horizontal or vertical lines, that tiling would have to contain 
more than 18 dominoes? This contradicts the fact that a 6x6 domino 
tiling contains only 18 dominoes, and so no such tiling exists.

Does this help? Write back if have trouble filling in the one hole I 
left in the proof for you, or if you have any other questions.

- Doctor Jubal, The Math Forum
  http://mathforum.org/dr.math/