4
$\begingroup$

Given a $6\times 6$ chessboard. The chessboard is filled with $18$ dominos (each domino covers $2$ adjacent squares). Prove that one can find a line from the one side of the board to the other side of the board that isn't intersected by one domino.

In the trivial case you have exactly $3$ dominoes lined up in each column or row of the square. Then you'll get $5$ lines verticaly and $2$ lines horizontaly and you're done.

Please give me only a hint on how to proceed proving this generally.

$\endgroup$
7
  • $\begingroup$ I don't understand the question; do you mean that the line is essentially taken to be the edges of adjacent dominoes? Or that it doesn't intersect one domino in particular? $\endgroup$
    – TomGrubb
    Sep 27, 2017 at 15:00
  • $\begingroup$ @ThomasGrubb It's the line taken to be the edges adjacent to the dominoes. $\endgroup$ Sep 27, 2017 at 15:02
  • $\begingroup$ @Bram28 So my first case described above is the first case of the induction proof? $\endgroup$ Sep 27, 2017 at 15:03
  • 2
    $\begingroup$ (1) Prove it Is impossible for a line to be intersected by exactly one domino. (2) With 5+5=10 possible lines, you would need at least 20 dominoes to block them all, but you have only 18. $\endgroup$ Sep 27, 2017 at 15:19
  • $\begingroup$ @JaapScherphuis I don't really understand how you can prove the 1st statement. Intuitively it's seems reasonable but formally I don't really know on how to begin. I thought maybe about using the fact that the dominoes are of even numbers and so is the total amount of squares of the board. $\endgroup$ Sep 27, 2017 at 15:35

1 Answer 1

3
$\begingroup$

This isn't an answer, but an observation too long for a comment.

Note that an $8 \times 8$ board can be covered with dominoes in such a way that every line is blocked:

enter image description here

The fact that this is possible means that an induction argument isn't the right way to go; with induction, the point is typically that you can continue a pattern ad infinitum. In this case, you need to make an argument specific to the $6 \times 6$ board (as Jaap Scherphuis pointed out in the comments).

$\endgroup$
1
  • 1
    $\begingroup$ +1 Although it's an answer to my request and a very good clarification on what to do. Thanks for that. $\endgroup$ Sep 27, 2017 at 15:55

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.