3

Saw this question in the book, "A Moscow Math circle" by Dorichenko.

Eighteen 2x1 dominoes cover a 6x6 board without overlapping each other or the sides of the board.

Prove that, for any such arrangement, it is possible to cut the board into two pieces along a vertical or horizontal line without cutting a single domino.

First and more important question : Can you please help me complete my answer to the above question ? This is my approach:

Let us label the rows as a,b,c,d,e,f and columns as 1,2,3,4,5,6.

Consider an arrangement where there is no domino occupying any 2 adjacent horizonal squares. For instance, let us say that there is no domino that occupies both 3 and 4. Then, in this arrangement, we can simply draw a vertical line between 3 and 4 without cutting any domino.

Similarly, consider an arrangement where there is no domino which is occupying two adjacent vertical squares, say 'a' and 'b'. Then we can simply draw a horizontal line between 'a' and 'b' without cutting any domino.

Therefore, the only way to not be able to cut the board without cutting a domino/ dominos is when there is at least one domino between every two adjacent horizontal boxes of the board i.e there is at least one domino each on 1-2, 2-3, 3-4, 4-5 and on 5-6. And also, there is at least one domino between every two adjacent vertical squares i.e there is at least one domino between a-b , b-c , c-d, d-e and e-f

Now, how do we prove that such an arrangement is not possible ?

Question 2: How would you have solved the question ?

Hemant Agarwal
  • 2,912
  • 14
  • 31

1 Answers1

6

Completion of proof:

Observe that because of parity there actually have to be two bridging dominoes for every pair of adjacent rows/columns. Now count them: 5x2 horizontal + 5x2 vertical: That's more than we have at our disposal.

loopy walt
  • 21,184
  • 33
  • 95
  • Can you elaborate more on why would parity dictate that there has to be two bridging dominoes for every pair of adjacent rows/columns? – Rishabh Jain Aug 24 '22 at 15:20
  • As Jaap noted on a recent duplicate: If there was only one bridging domino crossing the border between such a pair, then that domino plus the rest of that border would split the rest of the board into areas of (6a+5) and (6b+5) squares (for some integers a and b), neither of which can be tiled by dominoes. – Ed Murphy Aug 25 '22 at 05:31