A chessboard of size is tiled with tiles of size . You do not know the tiling but wish to uncover it. In order to do so, you can choose some cells on the board, following which you will learn what the positions of the tiles that cover those cells are. What is the least such that you can make your choice so as to always be able to reconstruct the complete tiling?
Solution
We will show that is the desired least number for any board tiled with tiles, , thus the answer to our problem is . From now on consider a board tiled with tiles (), with fixed.
For a lower bound of , divide the board into squares of size and notice that if one of them, say , does not contain some one of the chosen cells, then there exist two tilings which differ on but agree on the rest of the board, and the given tiling would never be uncovered. Thus we must have .
For an upper bound of , consider the in number lower-left cells in each one of the squares of size considered above, and learn the position of the tiles that cover these cells. We shall show by induction on that this procedure allows you to figure out the complete tiling. Thus . This, together with prove above would imply , and we'll have finished.
For the induction argue as follows:
For , suppose that there are two tilings and that agree on all lower-left cells of the squares considered above, but differ on some other cell of the given board. We'll arrive at a contradiction, which will mean any tiling can be uncovered by choosing to learn the positions of these lower-left cells, as wanted. Indeed:
Let be the domino which covers in . Colour in red the upper-right cell in each square; without loss of generality, is a red cell (otherwise, replace by the other cell covered by ). Let be the domino which covers in , be the second cell covered by , be the domino which covers in , be the second cell covered by , et cetera. Then is red for all .
Let be the least positive integer such that there exists a such that ; clearly, we must have . Consider the polyomino enclosed by the sequence of cells , .
Let be the centre of . It is straightforward to verify that (where denotes area). Since is a polyomino in the grid formed by the centres of all red cells, its area is a multiple of four and the number of its sides is even. It follows from this that is odd whereas it must be possible to tile with dominoes; the desired contradiction.
For the inductive step, let . Number all columns as through from left to right and all rows as through from bottom to top, and delete all rows and columns whose number is congruent to modulo . This operation produces a chessboard tiled with tiles. By the induction hypothesis, we can reconstruct this tiling completely by choosing to uncover the lower-left cells of the squares in which we divide this chessboard. These cells are exactly the lower-left cells of the squares in which we divide the original chessboard. Restore all deleted rows and columns, and you have the positions of all tiles in the original tiling that were not contained within a deleted row or column. Repeat the operation for all rows and columns whose numbers are congruent to modulo , and you have the positions of those tiles as well, using the same lower-left cells of the squares in which we divide the original chessboard. So choosing to learn the positions of the tiles covering these cells you uncover the whole tiling of the original chessboard, as wanted to prove.