Maths Olympiad Prep

Library /

Combinatorics Difficulty 6.2 National Olympiad Prove it Philippines

Problem:
A T-tetromino is formed by adjoining three unit squares to form a 1×31 \times 3 rectangle, and adjoining on top of the middle square a fourth unit square. Determine the minimum number of unit squares that must be removed from a 202×202202 \times 202 grid so that it can be tiled with T-tetrominoes.

Solutions — 2

Solution 1

Solution:
We provide the following construction, which shows that the answer is at most four. Clearly, four T-tetrominoes tile a 4×44 \times 4 grid, as follows:

Figure 1

These can be used to tile the upper-left 200×200200 \times 200 grid. It can be verified that the following pattern fills the remaining space, leaving four grid squares uncovered:

Figure 2

As the answer must be a multiple of four, it remains to prove that the answer is not zero, that is, it is impossible to tile a 202×202202 \times 202 grid with T-tetrominoes.

Number the rows of the grid, from left to right, with 0,1,,2010,1, \ldots, 201. Similarly, number the columns of the grid, from top to bottom, with 0,1,,2010,1, \ldots, 201.
Assign the square numbered (x,y)(x, y) with the weight 4x+4y+14x+4y+1. It can be verified that a T-tetromino, no matter how it is placed, covers a sum of weights divisible by 88. However, the sum of all the weights is not divisible by 88, as desired.

Solution 2

Solution:
An alternative way to prove that the 202×202202 \times 202 grid cannot be tiled with T-tetrominoes is with a checkerboard coloring.

For the sake of contradiction, assume that the board can be tiled with T-tetrominoes. Clearly, a T-tetromino covers only either three or one black square. Let xx be the number of T-tetrominoes each covering three black squares and yy be the number of T-tetrominoes each covering only one black square. Counting the number of black and white squares yields
3x+y=21012,x+3y=21012x=y=10122 3x + y = 2 \cdot 101^{2}, \quad x + 3y = 2 \cdot 101^{2} \quad \Longrightarrow \quad x = y = \frac{101^{2}}{2}
which contradicts the fact that xx and yy are integers.

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.