Covering a square

Feb 2010
26
1
Is it possible to remove one square from a 5 × 5 board so
that the remaining 24 squares can be covered by eight 3 × 1
rectangles? If yes, find all such squares
(Hint: A domino is a 2 × 1 rectangle. As you may know,
if two diagonally opposite squares of an ordinary 8 × 8–
chessboard are removed, the remaining 62 squares cannot
be covered by 31 non-overlapping dominos. The reason
being, after removing the two corners 32 squares of one
colour and 30 of the other are left. No matter how you place
a domino it will cover one white and one black square.)


I found that if the central square is removed, the remaining squares can be covered. I don't think there are any other squares which apply.
How do you show that you cannot cover the board if you remove any other square?
 
Mar 2010
116
41
Bratislava
Is it possible to remove one square from a 5 × 5 board so
that the remaining 24 squares can be covered by eight 3 × 1
rectangles? If yes, find all such squares
(Hint: A domino is a 2 × 1 rectangle. As you may know,
if two diagonally opposite squares of an ordinary 8 × 8–
chessboard are removed, the remaining 62 squares cannot
be covered by 31 non-overlapping dominos. The reason
being, after removing the two corners 32 squares of one
colour and 30 of the other are left. No matter how you place
a domino it will cover one white and one black square.)


I found that if the central square is removed, the remaining squares can be covered. I don't think there are any other squares which apply.
How do you show that you cannot cover the board if you remove any other square?
You can color the board using 3 colors as follows:
ABCAB
BCABC
CABCA
ABCAB
BCABC

We have 8 A's, 9 B's and 8 C's.

If you notice that each trimino covers exactly one A, one B and one C, you can see immediately that you have to omit a square colored by color B.

Now, we can repeat the same reasoning with a different coloring (obtained using vertical symmetry):
BACBA
CBACB
ACBAC
BACBA
CBACB

There's only one square which has the color B in both colorings.

You can easily find more similar problems, if you're interested in them, if you google for keywords like invariant, domino, chessboard
Google
 
  • Like
Reactions: nahduma