Remove the square in the top-left corner of a $2015 \times2015$ chessboard. Can the remaining mutilated chessboard be tiled with $1\times4$ and $4\times1$ rectangles?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Is this a question from a contest? $\endgroup$– JRNCommented Mar 22, 2016 at 11:01
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
I believe this works as a short proof.
Color the second, fourth, sixth, etc. rows orange. Every rectangle covers an even number of orange squares ... but there are an odd number of orange squares ($1007 \cdot 2015$ to be precise). Thus it is impossible.
answered Mar 21, 2016 at 15:18
-
3$\begingroup$ +1, this also proves that it's still not possible if we add 2x2 rectangles. $\endgroup$ Commented Mar 21, 2016 at 15:35
$\begingroup$
$\endgroup$
First assume that this is possible.
Look at the first row. It has 2014 available spaces. This means that there are at least 2014 % 4 = 2 pieces that are 1x4.
The second row now has 2015 - 2 = 2013 spaces available. This means that there are at least 2013 % 4 = 1 piece that is 1x4 (with the top of that piece starting on that row).
The third row now has 2015 - 3 = 2012 spaces available. This means that there are at least 2012 % 4 = 0 pieces that are 1x4.
The fourth row now has 2015 - 3 = 2012 spaces available. This means that there are at least 2012 % 4 = 0 pieces that are 1x4.
The fifth row now has 2015 - 1 = 2014 spaces available. This means that there are at least 2014 % 4 = 2 pieces that are 1x4.
The sixth is just as the second.
the seventh is just as the third.
...
the $n$th row is just as the ($n \% 4$)th
the 2013th row is just like the second row and therefore should at least have 2 pieces that are 4x1, but this is impossible because there are less than 4 spaces from the 2013th row down.
Therefore
the tiling is not possible.
Note that I say "at least" at each row. You might wonder, but what if there are more? This wouldn't matter because if there were more they would always be more in multiples of 4 to be able to fill the row. And because they are in multiples of 4 it has no consequence on the "at least" number of 1x4 pieces on the next row.
$\begingroup$
$\endgroup$
Take the original 2015 x 2015 board, and color the SW to NE diagonals with four colors in the repeating pattern red, blue, green, purple as shown below: $$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline \color{red}{\times} & \color{blue}{\times}& \color{green}{\times}& \color{purple}{\times}&\color{red}{\times} &\cdots\\ \hline \color{blue}{\times}& \color{green}{\times}& \color{purple}{\times}&\color{red}{\times} &\ddots\\ \hline \color{green}{\times}& \color{purple}{\times}&\color{red}{\times} &\ddots\\ \hline \color{purple}{\times}&\color{red}{\times} &\ddots\\ \hline \color{red}{\times} &\ddots\\ \hline \vdots\\ \hline \end{array} $$ Then, remove one of the red corners. Every tile will cover exactly one red square. The number of red squares is equal to 5 + 9 + ... + 2013 + 2013 + ... + 5 + 1 = 1,015,055, which is one fewer than the number of tiles needed to color the whole board.
answered Mar 21, 2016 at 18:08
$\begingroup$
$\endgroup$
1
It's interesting to notice that if you square an odd integer with an absolute value greater than or equal to 3, then subtract 1 from it, the result will always be a number divisible by 4. You can prove this to yourself using the representation of an odd number (2n+1), squaring it, subtracting 1 from it, and the proof should become apparent after that. Not all squares of odd numbers will result in a layout that can be divided into 4x1 rectangles. 3x3 obviously doesn't. 5x5 does, 7x7 doesn't, 9x9 does. One can begin to detect a pattern. Basically if a side can be represented as (4n+1), where n is an integer, then the rectangles will fit.
-
1$\begingroup$ Although this is an interesting observation, it doesn't show why the 4n+1 pattern holds. $\endgroup$– f''Commented Mar 21, 2016 at 23:31