You have an infinite stack of T-shaped tetrominoes (composed of four squares of side length 1), and an n × n board. You are allowed to place some tetrominoes on the board, possibly rotated, as long as no two tetrominoes overlap and no tetrominoes extend off the board. For which values of n can you cover the entire board?
Problem
Source: 2022 cjmo P2
Tags: CJMO, combinatorics
12.03.2022 20:09
$4\mid n$ only. Clearly $n$ is even. If $4\nmid n$, then the number of T's is odd, and a checkerboard coloring gives contradiction. For $4\mid n$ we have TTTS ATSS AABS ABBB
12.03.2022 20:32
CANBANKAN wrote: $4\mid n$ only. Clearly $n$ is even. If $4\nmid n$, then the number of T's is odd, and a checkerboard coloring gives contradiction. For $4\mid n$ we have TTTS ATSS AABS ABBB I got the same answer
12.03.2022 20:54
ye that is what I got
04.05.2022 18:49
I spent so long trying to get this config in tetris For $4 \mid n,$ note the attached config, if you don't see it then oh well. Each tetromino covers $4$ squares, so odd $n$ clearly does not work. For $2 \mid n$ but $4\not{\mid}n,$ simply apply a checkerboard coloring argument to show that the tetrominoes cover an odd amount of white squares but there are an even number of white squares in the entire checkerboard.
Attachments:

21.01.2024 07:19
The answer is $\boxed{n \text{ divisible by } 4}$. The construction is obvious by copypasting the $4 \times 4$ construction across the board. Claim $4 \mid n$. Proof. It is easy to see, from say area, that $2 \mid n$. To show that we require $4 \mid n$ consider a checkerboard coloring. Each tetrominoe covers exactly $3$ squares of one of the colors, and $1$ of the other. Thus we require an even number of tetronimoes. This implies that $8 \mid n^2$. However it is easy to see then that we must have $4 \mid n$ as claimed. $\square$
21.01.2024 07:21
We claim that the answer is $n \equiv 0 \pmod{4}$ only. First, note that odd $n$ fails since we then have a total number of squares - $n^2$ which is odd and thus, clearly not divisible by 4 (which it would have to be if it was completely tileable by T-tetrominoes which have 4 squares each). Now, for $n\equiv 2 \pmod{4}$, we have $n=2m$ for some odd integer $m$. Then, the total number of squares is $n^2=(2m)^2=4m^2$. Then, if it is completely tileable using T-tetrominoes, we have to use exactly $m^2$ tetrominoes which is an odd number. Now, color the board chessboard style. It is easy to see that each T-tetromino covers exactly 1 or 3 black squares. Thus, the total number of black squares covered is odd (since we have an odd number of tetrominoes and each covers and odd number of squares). But, in total we have $\frac{n^2}{2}=\frac{4m^2}{2}=2m^2$ black squares which is clearly even. But this is a clear contradiction and it is impossible to cover an $n\times n$ grid using T-tetrominoes when $n\equiv 2 \pmod{4}$. For $n\equiv 0 \pmod{4}$. Simply break the $n\times n$ grid into multiple $4\times 4$ grid sections. Then, cover each section using T-tetrominoes as follows.
Attachments:
