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 ?

  • $\begingroup$ Does this answer your question? One rectangle, indivisible $\endgroup$
    – StephenTG
    Sep 21 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$ Sep 21 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
    Sep 21 at 13:39

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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