Browse · MathNet
Print2016 European Girls' Mathematical Olympiad
Romania 2016 counting and probability
Problem
Let and be integers such that and . Place rectangular tiles, each of size or , on an chessboard so that each tile covers exactly cells, and no two tiles overlap. Do this until no further tile can be placed in this way. For each such and , determine the minimum number of tiles that such an arrangement may contain.
Solution
The required minimum is if , and it is if .
The case being clear, assume henceforth . Begin by describing maximal arrangements on the board , having the above mentioned cardinalities.
If , then . To obtain a maximal arrangement of this cardinality, place four tiles, , , and in the square , stack horizontal tiles in the rectangle , and erect vertical tiles in the rectangle .
If , then . A maximal arrangement of tiles is obtained by stacking horizontal tiles in the rectangle , another horizontal tiles in the rectangle , and adding the horizontal tile .
The above examples show that the required minimum does not exceed the mentioned values.
To prove the reverse inequality, consider a maximal arrangement and let , respectively , be the number of rows, respectively columns, not containing a tile.
If or , the arrangement clearly contains at least tiles.
If and are both positive, we show that the arrangement contains at least tiles. To this end, we will prove that the rows, respectively columns, not containing a tile are consecutive. Assume this for the moment, to notice that these rows and columns cross to form an rectangular array containing no tile at all, so and by maximality. Consequently, there are rows containing at least one horizontal tile each, and columns containing at least one vertical tile each, whence a total of at least tiles.
We now show that the rows not containing a tile are consecutive; columns are dealt with similarly. Consider a horizontal tile . Since , the nearest horizontal side of the board is at most rows away from the row containing . These rows, if any, cross the columns crosses to form a rectangular array no vertical tile fits in. Maximality forces each of these rows to contain a horizontal tile and the claim follows.
Consequently, the cardinality of every maximal arrangement is at least , and the conclusion follows.
The case being clear, assume henceforth . Begin by describing maximal arrangements on the board , having the above mentioned cardinalities.
If , then . To obtain a maximal arrangement of this cardinality, place four tiles, , , and in the square , stack horizontal tiles in the rectangle , and erect vertical tiles in the rectangle .
If , then . A maximal arrangement of tiles is obtained by stacking horizontal tiles in the rectangle , another horizontal tiles in the rectangle , and adding the horizontal tile .
The above examples show that the required minimum does not exceed the mentioned values.
To prove the reverse inequality, consider a maximal arrangement and let , respectively , be the number of rows, respectively columns, not containing a tile.
If or , the arrangement clearly contains at least tiles.
If and are both positive, we show that the arrangement contains at least tiles. To this end, we will prove that the rows, respectively columns, not containing a tile are consecutive. Assume this for the moment, to notice that these rows and columns cross to form an rectangular array containing no tile at all, so and by maximality. Consequently, there are rows containing at least one horizontal tile each, and columns containing at least one vertical tile each, whence a total of at least tiles.
We now show that the rows not containing a tile are consecutive; columns are dealt with similarly. Consider a horizontal tile . Since , the nearest horizontal side of the board is at most rows away from the row containing . These rows, if any, cross the columns crosses to form a rectangular array no vertical tile fits in. Maximality forces each of these rows to contain a horizontal tile and the claim follows.
Consequently, the cardinality of every maximal arrangement is at least , and the conclusion follows.
Final answer
Minimum number of tiles = n if n = k; and min(n, 2n − 2k + 2) if k < n < 2k.
Techniques
Coloring schemes, extremal arguments