9
$\begingroup$

Say I have an eleven by eleven chessboard, so there's 121 squares total. I remove the centermost piece so there's 120 pieces. I want to tile the chessboard with 1x4 or 4x1 pieces in a way that none of the pieces I place hang off of the board or overlap with one another. I also want the entire chessboard to be covered. Can it be done? I heard this problem from a friend and looked up a lot of domino tiling theory but can't figure it out still.

Any answers? Even incomplete answers or thoughts would be useful.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ As a general note, this kind of problem just screamed 'coloring proof' at me when I read it. There a different ways to color your board and in general for these kind of problems, either it is relatively straight forward to find a tiling or there is a coloring proof why it is impossible. $\endgroup$
    – quarague
    Dec 2, 2022 at 9:12

3 Answers 3

Reset to default
13
$\begingroup$

The answer is

no

because

grid with 2×1 vertical dominoes alternating
Each 1×4 covers exactly two red cells, but there are 61 red cells total.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Corollary: by applying the same coloring in four ways, we can conclude that there are exactly 4 cells ((4,4) and rotations) that admit such a tiling after removal. $\endgroup$
    – Bubbler
    Dec 2, 2022 at 4:09
  • 1
    $\begingroup$ @Bubbler it only shows that we can't say "no" with this technique, right? Unless, of course, you have an example tiling showing it done with (4,4) removed. $\endgroup$
    – justhalf
    Dec 2, 2022 at 4:15
  • 5
    $\begingroup$ @justhalf Yes, you're right. Constructing such a tiling is left as an exercise to the reader. :P $\endgroup$
    – Bubbler
    Dec 2, 2022 at 4:24
4
$\begingroup$

A non-coloring solution:

No, it's impossible (every $v_n$ variable is the number of the vertical blocks starting on row $n$):

enter image description here

11 can be written as $4k+3$ and 10 as $4k+2$, with each horizontal block taking up 4 squares on a row. The rest are vertical blocks.

Row 1: $v_1 ≡ 3$ $(mod$ $4)$
Row 2: $v_1 + v_2 ≡ 3$ $(mod$ $4)$
Row 3: $v_1 + v_2 + v_3 ≡ 3$ $(mod$ $4)$
Row 4: $v_1 + v_2 + v_3 + v_4 ≡ 3$ $(mod$ $4)$
Row 5: $v_2 + v_3 + v_4 + v_5 ≡ 3$ $(mod$ $4)$
Row 6: $v_3 + v_4 + v_5 + v_6 ≡ 2$ $(mod$ $4)$
Row 7: $v_4 + v_5 + v_6 + v_7 ≡ 3$ $(mod$ $4)$
Row 8: $v_5 + v_6 + v_7 + v_8 ≡ 3$ $(mod$ $4)$
Row 9: $v_6 + v_7 + v_8 ≡ 3$ $(mod$ $4)$
Row 10: $v_7 + v_8 ≡ 3$ $(mod$ $4)$
Row 11: $v_8 ≡ 3$ $(mod$ $4)$

This leads to the contradiction where $v_3+v_4+v_5+v_6$ should have been 2 modulo 4 based on the middle row, but is actually divisible by 4.

Taking away a square:

Let the single square be below the middle row. Then $v_1$ and $v_5$ can be written in the $4k+3$ form. $v_2, v_3, v_4$ and $v_6$ can be written in the $4k$ form. Rows 8 and 9 (from top to bottom) give different results, so it's on Row 8 because its mod 4 sum is 1 lower. Same goes for the column. Row 8, column 8, rotations are welcome.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Probably correct but not the clearest explanation! $\endgroup$
    – Florian F
    Dec 6, 2022 at 22:31
  • $\begingroup$ Sorry, is it clearer now? $\endgroup$
    – Nautilus
    Dec 7, 2022 at 6:16
2
$\begingroup$

A tiling with a different square removed, using @Bubbler's comment:

enter image description here
The empty square can be moved into any of the three other admissible positions by sliding tiles, as well.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.