Tiling with DominoesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/