Jump to content
BrainDen.com - Brain Teasers
  • 0

Covering chessboards with dominoes


bonanova
 Share

Question

Thirty-two dominoes can always cover a standard 8x8 chessboard.

But can 31 dominoes always cover a chessboard if we remove two of its squares?

Evey problem solver knows it can never happen if the removed squares have the same color.

1. But what if the removed squares have opposite colors?

 

If you try to cover a 7x7 chessboard with dominoes, one square will be left over.

2. Which one?

 

post-1048-0-64943200-1415858289_thumb.gi

3.  Can this board be tiled with dominoes? Why or why not?

 

post-1048-0-38375200-1415859096_thumb.gi

4.  Can this board be tiled with quadominoes? Why or why not?

Link to comment
Share on other sites

8 answers to this question

Recommended Posts

  • 0

1. Yes.


One configuration is:
.AABBCC5
DDEEFF25
GGHHII26
JJKKLL36
MMNNOO37
PPQQRR47
SSTTUU48
.VVWWXX8


2. Each square may be left over, depending on the arrangement.

3. With an assumption that the squares surrounded by a blue outline are to be left domino-free, and a domino fits inside the border of any two adjacent squares, the answer is "Yes".

4. With an assumption that the squares surrounded by a blue outline are to be left quadomino-free, and a quadomino fits inside the border of a four-square area, the answer is "No".
Link to comment
Share on other sites

  • 0

The answer for 3 is "no". Placing a domino so the protruding single squares is covered reveals that an internal square will be unfilled.

The answer to 4 is "no". A 1x4 quadomino will not fill a 10x10 checkered-board. 10 is not evenly divisible by 4.

 

But 100 is divisible by 4.

 

Still open.

Link to comment
Share on other sites

  • 0

The answer is "no".

Consider a rook that can only move on black squares.
Let's call "reachable" the squares that can be reached by this rook
(in finite number of moves) from the bottom-left corner.
Only black squares in rows: 1 (bottom), 3, 5, 7 and 9 are reachable.
This accounts to 25 (5*5) reachable squares total.
Now observe that a quadomino, now matter how placed on the chessboard,
always covers an even (0 or 2) number of reachable squares.
But 25 is odd.

  • Upvote 1
Link to comment
Share on other sites

  • 0

Consider a lame King (chess piece) that cannot move diagonally.


It's easy to draw a closed path for him to inspect all his kingdom:
a closed path that visits each square exactly once (and returns to starting point).
Obviously such path can be covered by dominoes starting from any square,
as well as any continuous segment of this path of even length.
Removing two squares of different color we break the path into two such segments,
so the answer is "yes".
  • Upvote 1
Link to comment
Share on other sites

  • 0

Suppose the bottom-left corner is black (and so are the other corners).


There is one more black square than white,
therefore the remaining square should be black.
The question remains: could it be any black square?
The answer is "yes".
To see this you can draw a path for the lame King (the one that cannot move diagonally),
that visits each square exactly once (there is no requirement for path to be closed this time as in solution to #1).
Removing one black square breaks the path into two segments of even length (only one segment in case when terminal square of the path is removed),
and obviously we can easily cover each segment with dominoes.
Edited by witzar
  • Upvote 1
Link to comment
Share on other sites

  • 0

The answer is "no".


Consider those two squares in the center, that - when removed - disconnect the board into two pieces.
Those two squares can be covered either by one or by two dominoes.
In both cases this disconnects the board into two pieces, that cannot be covered by dominoes,
since they have different number of black and white squares.
To see this, first inspect the case with one domino (just count black squares and white squares of the upper piece).
The difference equals 2 in this case.
Now it is easy to realize that replacing the single domino with two dominoes can fix this difference only by 1 (not enough).
  • Upvote 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...