3
$\begingroup$

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 ?

Improve this question
$\endgroup$
3
  • $\begingroup$ Does this answer your question? One rectangle, indivisible $\endgroup$
    – StephenTG
    Commented Sep 21, 2021 at 12:08
  • $\begingroup$ @StephenTG not quite. The proposed duplicate asks for “the smallest area that cannot be split along a line into two smaller rectangles”. The proposed duplicate isn’t a duplicate, but it is related. $\endgroup$
    – Taco
    Commented Sep 21, 2021 at 13:37
  • $\begingroup$ Fair. The answers to the question I've linked only cover the cases up to 5x6, so this can be seen as more of an extension than a duplicate. $\endgroup$
    – StephenTG
    Commented Sep 21, 2021 at 13:39

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you elaborate more on why would parity dictate that there has to be two bridging dominoes for every pair of adjacent rows/columns? $\endgroup$
    – Rishabh Jain
    Commented Aug 24, 2022 at 15:20
  • $\begingroup$ 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. $\endgroup$
    – Ed Murphy
    Commented Aug 25, 2022 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.