Any cell of a $5\times 5$ table is colored black or white. Find the greatest possible value of the ways to place a $T$-tetramino on the table so that it covers exactly two white and two black cells (for various colorings of the table).
Problem
Source: 2017 Belarus Team Selection Test 6.2
Tags: combinatorics, Tables
Pathological
01.04.2019 06:47
The answer is $37.$
To see that $37$ is attainable, consider the following table, where $W$ means white and $B$ means black.
\[
\begin{bmatrix}
W & W & B & B & W \\
B & B & W & W & B \\
W & W & B & B & B \\
B & B & W & W & B \\
W & W & B & B & W
\end{bmatrix}
\]
Now, we will show that $37$ is optimal. For a $T-$tetromino, we will define its $\mathbf{core}$ as the cell which is in its center (the one neighboring the other three). Notice that any point is the core of at most $3$ $T-$tetrominoes, with equality iff it is surrounded by $3$ cells of its opposite color and $1$ of the same color. Furthermore, any point on the boundary is the core of at most $1$ $T-$tetromino and the corners cannot be the cores of any $T-$tetrominoes. Therefore, this gives an upper bound of $3 * 3 * 3 + 12 * 1 = 27 + 12 = 39.$
Assuming that $39$ was possible, we can WLOG assume that the center is white and then uniquely determine the other cells (up to rotation) one by one, and easily find that $39$ is not possible.
Hence, we've shown that the answer is at most $38.$ Now, notice that in the case for $38,$ there is only one of the squares which is "bad," in the sense that it's the core of one too few $T-$tetrominoes. Then, caseworking on whether this bad square is on the edge or in the middle $3 \times 3$, and then splitting into subcases on where it is will finish (it's pretty straightforward, since using the non-bad squares turns out to always be enough to uniquely determine the grid).
Note that an interior cell is bad iff it has $2$ neighbors of each color.