5
$\begingroup$

Problem Is it possible to tile a $13 \times 13$ board with $4 \times 1$ dominoes such that the center square is left untiled?

I was not able to find a tiling so I am trying to prove that it is no possible.

I tried the usual way of coloring the board with $4$ colors using a chessboard style alternating coloring. Lets say the colors are $1, 2, 3, 4$ then I find that we have $43$ $1$’s, $42$ $2$‘s, $42$ $3$‘s, $42$ $4$’s and the center ($7^{\text{th}}$ row and $7^{\text{th}}$ column) cell has color $1$. But then this meets the demands of the $4 \times 1$ dominoes, so there is no contradiction.

Any hint will be helpful. Do I need to do a different kind fo coloring?

$\endgroup$
4
  • $\begingroup$ I would like to understand your coloring convention, but I don't (it's even worse when I read the answer given!) Could you make it more explicit ? $\endgroup$ – Jean Marie Sep 9 '20 at 7:30
  • $\begingroup$ My first row is 1, 2, 3, 4, 1, 2, 4..... $\endgroup$ – Subham Jaiswal Sep 9 '20 at 9:21
  • $\begingroup$ @Jean my second row is a cyclic left shift of row 1, tht is 2, 3, 4, 1, 2, 3.. n so on for 3rd row n so on $\endgroup$ – Subham Jaiswal Sep 9 '20 at 9:23
  • $\begingroup$ @JeanMarie I have drawn out the one in the answer. $\endgroup$ – tkf Sep 9 '20 at 12:51
9
$\begingroup$

Any $4\times 4$ Latin square gives a colouring by repeating across the board, starting from the top left corner. You just need a Latin square where the $(1,1)$ entry is different to the $(3,3)$ entry.

For example $$ \begin{array}{c} 1234\\2143\\3421\\4312 \end{array} $$

which gives: $$\small\begin{array}{|c|c|c|c|} \hline 1234&1234&1234&1 \\ 2143&2143&2143&2 \\ 3421&3421&3421&3 \\ 4312&4312&4312&4 \\ \hline 1234&1234&1234&1 \\ 2143&2143&2143&2 \\ 3421&34{\tiny\fbox{2}}1&3421&3 \\ 4312&4312&4312&4 \\ \hline 1234&1234&1234&1 \\ 2143&2143&2143&2 \\ 3421&3421&3421&3 \\ 4312&4312&4312&4 \\ \hline 1234&1234&1234&1\\ \hline \end{array} $$

Any $4\times 1$ (or $1\times 4)$ tetromino will cover one square of each colour, so a collection of tetrominos will cover the same number of squares of each colour. Thus they cannot cover all but the center square (boxed), as you have an extra $1$ (e.g. bottom right square of board) and one less $2$ (center square).

$\endgroup$
4
  • 1
    $\begingroup$ A $1 \times 4$ tile is a tetromino, not a domino. Otherwise, a good solution. $\endgroup$ – Ross Millikan Sep 9 '20 at 15:12
  • $\begingroup$ The "4x1 domino" is in the question title as well ;) $\endgroup$ – ypercubeᵀᴹ Sep 9 '20 at 15:50
  • 1
    $\begingroup$ [+1] Now very clear. $\endgroup$ – Jean Marie Sep 9 '20 at 17:46
  • 2
    $\begingroup$ See page 4 of this interesting document for a different coloring argument. $\endgroup$ – Jean Marie Sep 9 '20 at 17:56

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.