7
$\begingroup$

If we remove the square in the upper right corner of a $8\times 8$ chessboard. The question is: Is it possible to cover the entire remaining area, with $1\times 3$ chocolate bars? (they can be laid on the chessboard vertically and horizontally aswell)

For the answer: We know that there will be $63$ squares left on the chessboard, of which $32$ are white and $31$ are black, since the one in the upper right corner was black. $63$ is divisible by $3$, so it could be possible to cover the area, but that doesn't prove that an arrangement exists to do it. I'm not sure how to continue and am seeking help. Thanks.

$\endgroup$
  • 2
    $\begingroup$ You also need an integer partition $32 = 2k + l, 31 = k + 2l$ because each bar covers exactly $2$ squares of one colour and one of the other. This has a unique solution (by linear algebra) so you know that $k$ bars must start and end on a white square and $l$ bars start and end on a black square. ($k=11, l=10$) $\endgroup$ – AlexR Sep 24 '14 at 20:08
  • $\begingroup$ Deleted my answer, I just grabbed the numbers from the OP. But I must've made a mistake. $\endgroup$ – amcalde Sep 24 '14 at 20:19
15
$\begingroup$

[Copied from When chessboards meet dominoes .]

This problem appears in Solomon Golomb's book Polyominoes. The solution involves coloring the chessboard in three colors in alternating diagonal stripes:

colored chessboard

This colors the $64$ squares of the chessboard with $21$ green squares, $21$ yellow squares, and $22$ blue squares. Each $1\times $3 rectangle must cover exactly one square of each color. The deleted square therefore cannot be any of the green or yellow ones, nor any of the squares equivalent to one of these under a rotation or reflection of the chessboard:

Solutions must look like this

(This is four copies of the first diagram, superimposed, with suitable rotations.)

This eliminates all but $4$ squares from consideration, namely the four bright blue ones in the previous diagram. So the only solutions involve deleting one of these four blue squares. In particular, the corner square won't do.

Showing that the chessboard can be tiled if one of the four special squares is deleted is then an easy exercise.

$\endgroup$

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.