Maths Olympiad Prep

Library / /7 of 17

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Balkan Mathematical Olympiad

A chessboard of size 1000×10001000 \times 1000 is tiled with tiles of size 1×101 \times 10. You do not know the tiling but wish to uncover it. In order to do so, you can choose some NN cells on the board, following which you will learn what the positions of the tiles that cover those cells are. What is the least NN such that you can make your choice so as to always be able to reconstruct the complete tiling?

Solution

We will show that N=k2N = k^2 is the desired least number for any kn×knkn \times kn board tiled with 1×n1 \times n tiles, n2n \ge 2, thus the answer to our problem is N=1002=10000N = 100^2 = 10000. From now on consider a kn×knkn \times kn board tiled with 1×n1 \times n tiles (n2n \ge 2), with k>1k > 1 fixed.

For a lower bound of NN, divide the board into k2k^2 squares of size n×nn \times n and notice that if one of them, say PP, does not contain some one of the NN chosen cells, then there exist two tilings which differ on PP but agree on the rest of the board, and the given tiling would never be uncovered. Thus we must have k2Nk^2 \le N.

For an upper bound of NN, consider the k2k^2 in number lower-left cells in each one of the squares of size n×nn \times n considered above, and learn the position of the tiles that cover these cells. We shall show by induction on nn that this procedure allows you to figure out the complete tiling. Thus Nk2N \le k^2. This, together with k2Nk^2 \le N prove above would imply N=k2N = k^2, and we'll have finished.

For the induction argue as follows:
For n=2n = 2, suppose that there are two tilings AA and BB that agree on all lower-left cells of the n×n=2×2n \times n = 2 \times 2 squares considered above, but differ on some other cell a1a_1 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 d1d_1 be the 1×n=1×21 \times n = 1 \times 2 domino which covers a1a_1 in AA. Colour in red the upper-right cell in each 2×22 \times 2 square; without loss of generality, a1a_1 is a red cell (otherwise, replace a1a_1 by the other cell covered by d1d_1). Let d2d_2 be the 1×n=1×21 \times n = 1 \times 2 domino which covers a1a_1 in BB, b1b_1 be the second cell covered by d2d_2, d3d_3 be the domino which covers b1b_1 in AA, a2a_2 be the second cell covered by d3d_3, et cetera. Then aia_i is red for all ii.
Let ss be the least positive integer such that there exists a t<st < s such that as=ata_s = a_t; clearly, we must have t=1t = 1. Consider the polyomino PP enclosed by the sequence of cells a1,b1,a2,b2,,bs1a_1, b_1, a_2, b_2, \dots, b_{s-1}, as=a1a_s = a_1.
Let OiO_i be the centre of aia_i. It is straightforward to verify that S(P)=S(O1O2Os1)s+2S(P) = S(O_1O_2\dots O_{s-1}) - s + 2 (where S()S(\cdot) denotes area). Since O1O2Os1O_1O_2\dots O_{s-1} is a polyomino in the grid formed by the centres of all red cells, its area S(O1O2Os1)S(O_1O_2\dots O_{s-1}) is a multiple of four and the number s1s-1 of its sides is even. It follows from this that S(P)S(P) is odd whereas it must be possible to tile PP with dominoes; the desired contradiction.

For the inductive step, let n3n \ge 3. Number all columns as 11 through knkn from left to right and all rows as 11 through knkn from bottom to top, and delete all rows and columns whose number is congruent to 22 modulo nn. This operation produces a k(n1)×k(n1)k(n-1) \times k(n-1) chessboard tiled with 1×(n1)1 \times (n-1) tiles. By the induction hypothesis, we can reconstruct this tiling completely by choosing to uncover the lower-left cells of the (n1)×(n1)(n-1) \times (n-1) squares in which we divide this k(n1)×k(n1)k(n-1) \times k(n-1) chessboard. These cells are exactly the lower-left cells of the n×nn \times n squares in which we divide the original kn×knkn \times kn 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 33 modulo nn, and you have the positions of those tiles as well, using the same lower-left cells of the n×nn \times n squares in which we divide the original kn×knkn \times kn chessboard. So choosing to learn the positions of the tiles covering these cells you uncover the whole tiling of the original kn×knkn \times kn chessboard, as wanted to prove. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.