INAMO 2021/8 wrote: On a $100 \times 100$ chessboard, the plan is to place several $1 \times 3$ boards and $3 \times 1$ board, so that Each tile of the initial chessboard is covered by at most one small board. The boards cover the entire chessboard tile, except for one tile. The sides of the board are placed parallel to the chessboard. Suppose that to carry out the instructions above, it takes $H$ number of $1 \times 3$ boards and $V$ number of $3 \times 1$ boards. Determine all possible pairs of $(H,V)$. Easily the most interesting problem in this year's INAMO. We claim that the answer is $(k,3333-k)$ where $33 \le k \le 3300$ and $k \equiv 0 \pmod{3}$. It is easy to find such a configuration, by generalizing the following board [asy][asy]size(4cm); path S = box( (-3,0), (4,7) ); path R = box( (3,6), (4,7)); fill(S, white); fill(shift(-3,0)*unitsquare,red); fill(shift(-1,1)*unitsquare, grey); fill(shift(-3,6)*unitsquare,red); fill(shift(-2,6)*unitsquare,red); fill(shift(-1,6)*unitsquare,red); fill(shift(0,6)*unitsquare,red); fill(shift(1,6)*unitsquare,red); fill(shift(2,6)*unitsquare,red); fill(shift(3,0)*unitsquare,blue); fill(shift(3,1)*unitsquare,blue); fill(shift(3,2)*unitsquare,blue); fill(shift(3,3)*unitsquare,blue); fill(shift(3,4)*unitsquare,blue); fill(shift(3,5)*unitsquare,blue); path W = box( (-3,0), (3,6)); fill(W,grey); path K = box( (-3,6), (3,6) ); fill(K, white); draw(K, black+1.4); path L = box( (3,0), (3,7)); fill(L, white); path M = box((0,0),(0,6)); fill(M,white); path N = box ((-3,3),(3,3)); fill(N,white); for (int i=-3; i<=3; ++i) { draw(shift(i,6)*unitsquare); } for (int i=-3; i<=3; ++i) { draw(shift(i,5)*unitsquare); } for (int i=-3; i<=3; ++i) { draw(shift(i,4)*unitsquare); } for (int i=-3; i<=3; ++i) { draw(shift(i,3)*unitsquare); } for (int i=-3; i<=3; ++i) { draw(shift(i,2)*unitsquare); } for (int i=-3; i<=3; ++i) { draw(shift(i,1)*unitsquare); } for (int i=-3; i<=3; ++i) { draw(shift(i,0)*unitsquare); } draw(L, black+1.4); draw(N,black+1.2); draw(M,black+1.2); draw(S, black+1.4); draw(R,black+1.4); [/asy][/asy] where every $3 \times 3$ grey tile could be replaced with either $3$ horizontal boards or $3$ vertical boards as follow: [asy][asy]size(4cm); path S = box( (-3,0), (0,3) ); path K = box( (-3,0), (-2,3)); fill(K, blue); draw(K, black+1.2); path A = box((-2,0), (-1,3)); fill(A,blue); draw(A,black+1.2); path B = box((-1,0), (0,3)); fill(B,blue); draw(B,black+1.2); draw(S,black+1.4); path T = box( (1,0), (4,3) ); draw(T,black+1.4); path C = box((1,0), (4,1)); fill(C,red); draw(C,black+1.2); path D = box((1,1),(4,2)); fill(D,red); path E = box((1,2),(4,3)); fill(E,red); draw(D,black+1.2); draw(E,black+1.2); [/asy][/asy] Let us now focus on proving that there are no other possible pairs of $(H,V)$. Indeed, note that the number boards needed to tile the whole board is $H + V = \frac{100^2 - 1}{3} = 3333$. Therefore, it suffices to keep track of the number of vertical boards used. Suppose that there are $k$ vertical boards used. Claim 01. $33 \le k \le 3300$. Proof. We will prove that $k \ge 33$, and by using symmetry, $3333 - k \ge 33$ as well, as this counts the number of horizontal boards. To prove this, fix a row $i$, and let the number of horizontal boards be $h_i$ and the number of vertical boards be $v_i$. Note that \[ 3h_i + v_i \in \{ 99, 100 \} \]for all $1 \le i \le 100$, where it could only be $99$ for exactly one index $i$. This implies that $v_i \equiv 1 \pmod{3}$ for exactly $99$ index $i$. This gives $v_i \ge 1$ for at least $99$ index $i$, which forces $\sum_i v_i \ge 99$. However, every vertical board contribute to $v_i$ exactly three times, which means that \[ 3k = \sum_i v_i \ge 99 \implies k \ge 33 \] Claim 02. $k \equiv 0 \pmod{3}$. Proof. Let us color the board with three colors: red, blue and green such that every row has a common color, and the color alternates as shown in the figure below, where we always start with red as the color of the first row: [asy][asy]size(4cm); path S = box( (-3,3), (1,7) ); fill(S,green); fill(shift(-3,6)*unitsquare,red); fill(shift(-2,6)*unitsquare,red); fill(shift(-1,6)*unitsquare,red); fill(shift(0,6)*unitsquare,red); fill(shift(-3,3)*unitsquare,red); fill(shift(-2,3)*unitsquare,red); fill(shift(-1,3)*unitsquare,red); fill(shift(0,3)*unitsquare,red); fill(shift(-3,5)*unitsquare,blue); fill(shift(-2,5)*unitsquare,blue); fill(shift(-1,5)*unitsquare,blue); fill(shift(0,5)*unitsquare,blue); for (int i=-3; i<=0; ++i) { draw(shift(i,6)*unitsquare); } for (int i=-3; i<=0; ++i) { draw(shift(i,5)*unitsquare); } for (int i=-3; i<=0; ++i) { draw(shift(i,4)*unitsquare); } for (int i=-3; i<=0; ++i) { draw(shift(i,3)*unitsquare); } draw(S,black+1.4); [/asy][/asy] We first claim that the missing tile must be in the red-colored row. To prove this, color the board in the following way: [asy][asy]size(4cm); path S = box( (-3,3), (1,7) ); fill(S,grey); fill(shift(-3,6)*unitsquare,white); fill(shift(-2,6)*unitsquare,black); fill(shift(0,6)*unitsquare,white); fill(shift(-3,3)*unitsquare,white); fill(shift(-2,3)*unitsquare,black); fill(shift(0,3)*unitsquare,white); fill(shift(-2,5)*unitsquare,white); fill(shift(-1,5)*unitsquare,black); fill(shift(-3,4)*unitsquare, black); fill(shift(-1,4)*unitsquare,white); fill(shift(0,4)*unitsquare,black); for (int i=-3; i<=0; ++i) { draw(shift(i,6)*unitsquare); } for (int i=-3; i<=0; ++i) { draw(shift(i,5)*unitsquare); } for (int i=-3; i<=0; ++i) { draw(shift(i,4)*unitsquare); } for (int i=-3; i<=0; ++i) { draw(shift(i,3)*unitsquare); } draw(S,black+1.4); [/asy][/asy] where the top left most tile is in white. It is easy to notice that any horizontal board, and any vertical board must cover exactly $1$ tile of each color. Since there are $1$ more white tile than black and grey tile, then the removed tile must be of white color. Repeating the same argument, but mirroring the coloring, we observe that the removed tile must be of white color in either cases of coloring. These remaining possible tiles all lie on the red row on the initial coloring. Indeed, note that there are a total of $34 \times 100 = 3400$ red tiles. Let us now count the number of red tiles occupied by vertical and horizontal boards. Indeed, since the missing square is one of the red tiles, there are $3399$ tiles that are occupied. However, any vertical board contributes exactly one red tile, and any horizontal board contributes either $0$ or $3$ red tile. Therefore, we conclude that \[ k \equiv 0 \pmod{3} \]which is what we wanted. Remark. This is a nice problem that shows how powerful coloring arguments could be used to tackle problems involving grids.

A different approach from the proposer (me):

Another interesting approach to prove an inequality: