A T-tetromino is formed by adjoining three unit squares to form a $1 \times 3$ rectangle, and adjoining on top of the middle square a fourth unit square. Determine the least number of unit squares that must be removed from a $202 \times 202$ grid so that it can be tiled using T-tetrominoes.
Problem
Source: Philippine Mathematical Olympiad 2020/1
Tags: PMO, combinatorics
20.02.2020 08:56
Claim: 202×2002 Can't be filled by T- tetrominoes. Proof:Colour the big $202*202$ board in ordinary chessboard pattern with alternatively black and white squres.A $T$-tetromino will $3$ black,$1$ white or $3$ white,$1$ black square.To cover the board we need equally many tetrominoes of each kind.But$202*202/4=10201$ is odd. Now total number of cells covered by the tetrominoes must be divisible by 4.As $2002*2002$ is divisible by 4, at least 4 cells should be deleted. Now we claim that deleting 4 cells we can cover the board. Number the columns and rows $0,1,2,...201$ from left to right and to bottom to top.$(i,j)$ denote the cell in $i$ th column $j$ th row. Now delete the $(200,0),(0,200),(201,200),(201,201)$ cells.Now the board consists of a left bottom $200*200$ board and upper most and right most 2 strips with some cells deleted. Note that 4×4 board can be covered by T-tetromino.So the 200*200 board can be covered Now define $L_k$ the following structure :Deleting the upper rightmost cell and bottom left most cell from a $4k+1*2$ board. So now we can cover the rightmost part of our board by a $L_{50}$ and the upper most by a $L_{50}$.Easy to see that $L_k$ s can be covered by T- trominoes.