2
$\begingroup$

Consider a chessboard ( an $8\times8$ board with 64 squares) and two opposite corner squares are removed.

Why can't you cover the rest of the board with domino tiles of 2 $\times$1?

What's the proof behind it?

I've read the solution on Gomory's theorem when the 2 opposite colors are removed from the chessboard. But I'm still curious behind the reason why this isn't possible.

$\endgroup$
6
  • 1
    $\begingroup$ Try covering a $4 \times 4$ board to find the reason. $\endgroup$
    – Math Lover
    Sep 26, 2017 at 16:15
  • 4
    $\begingroup$ Every tile covers one white square and one black square. Your board has 32 black squares and 30 white squares. $\endgroup$
    – Doug M
    Sep 26, 2017 at 16:15
  • $\begingroup$ But is that the only reason why it's not solvable. $\endgroup$
    – Anonymous196
    Sep 26, 2017 at 16:16
  • $\begingroup$ @AnonymousI I am sure there are other proofs that show it is not solvable ... but this one is super straightforward! $\endgroup$
    – Bram28
    Sep 26, 2017 at 16:18
  • 2
    $\begingroup$ @AnonymousI that is the proof. It's a proof by contradiction. We could make it a little more formal, but it's still the outline of the proof. $\endgroup$
    – Dando18
    Sep 26, 2017 at 16:21

1 Answer 1

Reset to default
3
$\begingroup$

Every time you place a domino, two tiles of different color are covered: one white and one black. If you remove two white squares, then you're left with 30 white squares and 32 black squares, which means one domino would have to cover 2 black squares. We know this is impossible!

$\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.