Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search