Dominoes puzzle in high school state-wide math competition

LifeIn

Well-known member
A six by six grid contains 36 squares. This grid can be completely covered by 18 dominoes in many ways. Prove that no matter how the grid is covered by dominoes, there will always be a vertical or horizontal grid line that divides the grid into two pieces without cutting through any dominoes. (The grid lines are the 5 vertical and 5 horizontal lines that make up the interior of the grid. Prove that at least one of these lines will not be blocked by a domino.)
 
It may be helpful to try to construct a counter example. Try to place 18 dominoes on a 6x6 grid so that every vertical and every horizontal grid line is blocked by a dominoe. Then again, maybe it won't.
 
OK, here is a hint that really will help. How many dominoes does it take to block one grid line? Ideally only one. But is it possible on a 6x6 grid to block a grid line with just one domino? Try it. Then think of evens and odds, and the fact that a domino takes up exactly two squares.
 
A six by six grid contains 36 squares. This grid can be completely covered by 18 dominoes in many ways. Prove that no matter how the grid is covered by dominoes, there will always be a vertical or horizontal grid line that divides the grid into two pieces without cutting through any dominoes. (The grid lines are the 5 vertical and 5 horizontal lines that make up the interior of the grid. Prove that at least one of these lines will not be blocked by a domino.)

Treating this scenario similar to a standard "fencepost - span counting problem" is helpful.

The array of dominoes where each domino covers two squares each - transforms a square matrix of the original 6 x 6 array into a 3 x 6 array or a 6 x 3 array of dominoes. [ using the standard row, column definition ]

The vertical grid in the 3 x 6 array:

- Counting the spans between the domino columns instead of the domino columns themselves leaves 6 - 1 = 5 spans.

- Because there are an odd number of spans between the domino columns, the third span (counting from the right or the left side) must bisect the matrix through the center of the array.

___
 
Hmmm, I'm not sure about that. I couldn't get the solution either, until I looked it up. It from the 1999 Michigan Math Prize Competition.

Since the grid is 6x6, any vertical or horizontal grid line divides the grid into two pieces that have an even number of squares. (6x1, 6x2, 6x3, 6x4, 6x5, 1x6. 2x6, 3x6, 4x6, 5x6 are all even numbers.) Any domino that is cut by one of these lines takes up exactly one square from each of the two pieces that grid line produces. That leaves an odd number of squares in each of the remaining pieces. Since it is impossible to cover an odd number of squares with dominoes (which also cover squares two at a time), any complete covering of the 6x6 grid must have a second domino blocking that grid line so that the two resulting pieces of the grid again have an even number of remaining squares. Therefore of one domino blocks a grid line, then there must be at least two dominoes blocking that grid line. Since there are 10 grid lines (5 vertical and 5 horizontal), that requires 20 dominoes to block them all. But there are only 18 dominoes covering a 6x6 grid. Therefore it is impossible to block all 10 grid lines with a complete covering of a 6x6 grid with dominoes.

Note that the same argument does not work for a 8x8 grid because there are 7 vertical and 7 horizontal grid lines, which require 14 x 2 dominoes (28). An 8x8 grid covered by dominoes uses 32 dominoes. And in fact it is possible to block all 14 grid lines with dominoes in an 8x8 grid.
 
Hmmm, I'm not sure about that. I couldn't get the solution either, until I looked it up. It from the 1999 Michigan Math Prize Competition.

Since the grid is 6x6, any vertical or horizontal grid line divides the grid into two pieces that have an even number of squares. (6x1, 6x2, 6x3, 6x4, 6x5, 1x6. 2x6, 3x6, 4x6, 5x6 are all even numbers.) Any domino that is cut by one of these lines takes up exactly one square from each of the two pieces that grid line produces. That leaves an odd number of squares in each of the remaining pieces. Since it is impossible to cover an odd number of squares with dominoes (which also cover squares two at a time), any complete covering of the 6x6 grid must have a second domino blocking that grid line so that the two resulting pieces of the grid again have an even number of remaining squares. Therefore of one domino blocks a grid line, then there must be at least two dominoes blocking that grid line. Since there are 10 grid lines (5 vertical and 5 horizontal), that requires 20 dominoes to block them all. But there are only 18 dominoes covering a 6x6 grid. Therefore it is impossible to block all 10 grid lines with a complete covering of a 6x6 grid with dominoes.

Note that the same argument does not work for a 8x8 grid because there are 7 vertical and 7 horizontal grid lines, which require 14 x 2 dominoes (28). An 8x8 grid covered by dominoes uses 32 dominoes. And in fact it is possible to block all 14 grid lines with dominoes in an 8x8 grid.

Thanks - :cool:

Their answer:

"3. There are five horizontal lines and five vertical lines that can cut the board. Since the area on either side of such a line is even, each of these ten lines must cut an even number of dominoes. No domino is cut by more than one line. For each line to cut a domino (and hence cut at least one other domino), we would need at least 20 dominoes.

Since there are only 18, some line must cut the board but not cut any of the dominoes."

Yes, since there are 3*6 = 18 dominoes (or 6*3 = 18 dominoes) there is at least one span between the array that "cuts" the array.

___
 
Back
Top