# Heuristics problem of a $6 \times 6$ chessboard

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.

• 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? Sep 27, 2017 at 15:00
• @ThomasGrubb It's the line taken to be the edges adjacent to the dominoes. Sep 27, 2017 at 15:02
• @Bram28 So my first case described above is the first case of the induction proof? Sep 27, 2017 at 15:03
• (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. Sep 27, 2017 at 15:19
• @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. Sep 27, 2017 at 15:35

Note that an $8 \times 8$ board can be covered with dominoes in such a way that every line is blocked:
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).