Today I am going to post the stunningly simple answer to the unanswered question from my last post. I couldn't solve it myself. So, I just saw the solution.
The Question was,
If you are given an 8x8 chessboard and infinite supply of (1 x 3) and (3 x 1) tiles, is it always possible to tile the chessboard using some of these tiles, if the position of the single uncovered cell is specified?
The Beautiful Answer:
Let's number the (8 x 8) board like the figure above. Here, we have 21 cells numbered 2, 21 numbered 3 and 22 numbered 1. A single tile covers three different numbers. So, the board cannot be covered if the uncovered cell is specified to be a cell with a 2 or 3 on it.
This beautiful technique of proof is known as Coloring Proof (here, 1, 2 and 3 represents three different 'colors')
The answer doesn't imply that, we are always safe with an uncovered-cell with an 1 on it. So, here is another question:
Which of these cells-containing-an-1 are safe to be kept uncovered ? (here, 'safe' means, it is still tillable).
Let's try to answer to the opposite question, "Which of these cells-containing-an-1 are not safe to be kept uncovered?"
Note that, the top-left cell contains an 1 but it is still an unsafe cell because, it is equivalent to the top-right cell containing a 2 ( the mirror reflection of this board has a 2 on the top-left cell ).
So, we might claim that, those cells that contain 1, both before and after the reflection of the board along the x-axis or y-axis, are safe to be kept uncovered.
There are four such cells. If we number rows and columns with numbers 1 to 8 then those safe cells are (3,3), (3,6), (6,3) and (6,6). Because of the symmetry of the board, proving the safety for one of these cells would prove for all four. And, we have already proved it for cell (3,6) in the previous post ( the solution image ).
The Question was,
If you are given an 8x8 chessboard and infinite supply of (1 x 3) and (3 x 1) tiles, is it always possible to tile the chessboard using some of these tiles, if the position of the single uncovered cell is specified?
The Beautiful Answer:
Let's number the (8 x 8) board like the figure above. Here, we have 21 cells numbered 2, 21 numbered 3 and 22 numbered 1. A single tile covers three different numbers. So, the board cannot be covered if the uncovered cell is specified to be a cell with a 2 or 3 on it.
This beautiful technique of proof is known as Coloring Proof (here, 1, 2 and 3 represents three different 'colors')
The answer doesn't imply that, we are always safe with an uncovered-cell with an 1 on it. So, here is another question:
Which of these cells-containing-an-1 are safe to be kept uncovered ? (here, 'safe' means, it is still tillable).
Let's try to answer to the opposite question, "Which of these cells-containing-an-1 are not safe to be kept uncovered?"
Note that, the top-left cell contains an 1 but it is still an unsafe cell because, it is equivalent to the top-right cell containing a 2 ( the mirror reflection of this board has a 2 on the top-left cell ).
So, we might claim that, those cells that contain 1, both before and after the reflection of the board along the x-axis or y-axis, are safe to be kept uncovered.
There are four such cells. If we number rows and columns with numbers 1 to 8 then those safe cells are (3,3), (3,6), (6,3) and (6,6). Because of the symmetry of the board, proving the safety for one of these cells would prove for all four. And, we have already proved it for cell (3,6) in the previous post ( the solution image ).
