Mongolian National Mathematical Olympiad

Let $X$ be the set of the painting of the $4 \times 4$ table with two colors, red and blue, so that no two rows are painted the same. Since we can color the $1 \times 4$ table with two colors in $2^4 = 16$ ways, $|X| = 16 \cdot 15 \cdot 14 \cdot 13$.

Now let $B_{ij} \subset X$ be the set of the painting of the $4 \times 4$ table with the two colors such that no two rows are painted the same and the $i$-th and the $j$-th columns are painted the same. We have to find $|X \setminus (B_{12} \cup B_{13} \cup B_{14} \cup B_{23} \cup B_{24} \cup B_{34})|$.

(1) Let us find $|B_{12}|$. Thus the first and the second columns are painted the same and no two rows are painted the same. There are three cases.

(i) Suppose that the first and the second columns are painted with only one color, red or blue. Then there are $4!$ ways to color the remaining $4 \times 2$ table with the two colors so that no two rows are painted the same. Considering the color of the first and second column, there are $2 \cdot 4!$ ways to color the $4 \times 4$ table in total.

(ii) Suppose that the first and the second columns are painted in such a way that three unit squares in the columns have the same color and the remaining one has the other color. Then the number of ways to color the remaining $4 \times 2$ table with the two colors is $4 \cdot 4 \cdot 3 \cdot 2$, since one row can be painted arbitrarily and the other three rows must be painted differently. We can color the first and the second column in $2 \cdot C_4^3$ ways. We have $8 \cdot 4! \cdot 4$ coloring in total.

(iii) Suppose that the first and the second columns are painted in such a way that two unit squares in age columns have the same color and the remaining two has the other color. Then the number of ways to color the remaining $4 \times 2$ table with the two colors is $(4 \cdot 3)^2$. We can color the first and the second column in $6$ ways. We have $6 \cdot (4 \cdot 3)^2$ coloring in total.

(2) Let $B_{ijk} \subset X$ be the set of the painting of the $4 \times 4$ table with the two colors such that no two rows are painted the same and the $i$-th, the $j$-th and the $k$-th columns are painted the same. Let us find $|B_{123}|$. Thus the first, the second and the third columns are painted the same and no two rows are painted the same.

(i) Suppose that the first three columns are painted in such a way that there exist three unit squares in the columns that have the same color. Then by the Dirichlet's box principle there exist two same rows, which is a contradiction. Therefore there is no such coloring.

(ii) Suppose that the first three columns are painted in such a way that two unit squares in the columns have the same color and the remaining two has the other color. Then the number of ways to color the remaining $4 \times 1$ table with the two color is $2 \cdot 2$. We can color the first three columns in $6$ ways. We have $6 \cdot 2 \cdot 2$ coloring in total.

(3) Let us find $|B_{12} \cap B_{34}|$. Thus the first two columns are painted the same, the 3rd and the 4th columns are painted the same, and no two rows are painted the same.

(i) Suppose that the first two columns are painted in such a way that there exist three unit squares in the columns that have the same color. Then by the Dirichlet's box principle there exist two same rows, which is a contradiction. Therefore there is no such coloring.

(ii) Suppose that the first three columns are painted in such a way that two unit squares in the columns have the same color and the remaining two has the other color. Then so is for the 3rd and the 4th columns. In this case we have $6 \cdot 2 \cdot 2$ coloring in total.

It is obvious that for mutually distinct $i, j, k, l$, we have $|B_{ij}| = |B_{12}|$, $|B_{ijk}| = |B_{123}|$ and $|B_{ij} \cap B_{kl}| = |B_{12} \cap B_{34}|$. Now we find that

$$\begin{align*} |X \setminus (B_{12} \cup B_{13} \cup B_{14} \cup B_{23} \cup B_{24} \cup B_{34})| &= |X| - 6 \cdot |B_{12}| + |B_{123}| + |B_{124}| \\ &\quad + |B_{123}| + |B_{124}| + |B_{12} \cap B_{34}| + |B_{134}| + |B_{123}| + |B_{13} \cap B_{24}| \\ &\quad + |B_{134}| + |B_{14} \cap B_{23}| + |B_{124}| + |B_{134}| + |B_{234}| + |B_{234}| + |B_{234}| \\ &\quad - |B_{123}| - |B_{124}| - |B_{134}| - |B_{234}| \\ &= 16 \cdot 15 \cdot 14 \cdot 13 - 6 \cdot 24 \cdot 70 + 11 \cdot 24 \\ &= 33864. \end{align*}$$