Each cell of the board with $2021$ rows and $2022$ columns contains exactly one of the three letters $T$, $M$, and $O$ in a way that satisfies each of the following conditions: In total, each letter appears exactly $2021\times 674$ of times on the board. There are no two squares that share a common side and contain the same letter. Any $2\times 2$ square contains all three letters $T$, $M$, and $O$. Prove that each letter $T$, $M$, and $O$ appears exactly $674$ times on every row.
Problem
Source: 2021 Thailand Online MO P10 (Mock TMO contest)
Tags: combinatorics, Thailand online MO, desi chudayi, o physicsknight muth mrnejrha
kankan
08.04.2021 00:32
We claim that it is possible to color the columns of the board so that in each row with three colors (say red, blue, and green), such that all the cells that contain a given letter in a row have the same color. We prove this by constructing the board, row by row. Assume that we are given a row of the board, and are constructing the row beneath it. We see that once we choose what the leftmost $2$ by $2$ square involving both rows is, the next square in the two rows only has one cell left, so it is determined. As constructing this square also leaves another square with just one cell left, the entire row is determined, by induction.
Let $a,b,c$ be $T,M,O$, in some permutation. Color every column that contains an $a$ in the given row red, every one that contained a $b$ blue, and every one that contains a $c$ yellow. Let at some point in the construction, there be a square with top row $ab$. We apply casework to the value of the bottom row and the value of the next letter in the top row.
Bottom row is $bc$
If the letter after $b$ in the top row is $a$, then the letter in the next row is $b$. If the letter after $b$ is instead $c$, the next letter in the lower row is $a$. Here, every $b$ in the lower row is blue, every $a$ in the lower row is yellow, and every $c$ in the lower row is blue.
Bottom row is $ca$
If the letter after $b$ in the top row is $a$, then the next letter in the lower row is $c$. If the next letter in the upper row is $c$, then the next letter in the bottom row would instead be $b$. Here, every $c$ in the lower row is blue, every $b$ in the lower row is yellow, and every $a$ in the lower row is blue.
Call the following pairs of colors adjacent: red and blue, blue and yellow, yellow and red. Then, it is seen that generating a new row "rotates" the letters on the colors, so that two letters that were on adjacent colors previously are still on adjacent colors. WLoG, let the columns occupied by $T$s in the first row be red, the ones occupied by $M$ blue, and the ones occupied by $O$ yellow. Now, let there be $x$ red columns, $y$ blue columns, and $z$ yellow columns. Then, let $T$ appear red $q$ times, let $M$ appear red $r$ times, and let $O$ appear red $s$ times. The amount of times $T$ appears is therefore $qx + sy + rz$. This expression is $rx + qy +sz$ for $M$, and $sx + ry + qz$ for $O$.
Each of these expressions equals $2021 \cdot 674$. The desired statement is equivalent to proving that each of $x, y, z$ is $\frac{2022}{3} = 674$.
I'm not entirely sure how to finish.
MarkBcc168
08.04.2021 05:05
You got more than half of the problem. One way to continue is to just solve the equation by eliminating the variables. You can also use matrix here.
CANBANKAN
08.04.2021 10:56
Slightly troll. Let f(T)=O, f(O)=M, f(M)=T. Let’s drop the condition each letter shows up on the board the same number of times for now. The motivation for this observation is that there are limited colorings for this grid, as the two rules on coloring are very strong conditions. The main observation is that if one row is colored such that $a_i$ denotes the $i$th letter on that row, and $b_i$ denote the $i$th letter on the next row then one of the two are true: $f(a_i)=b_i \forall i $ or $f(b_i)=a_i$. Notice there are two choices for the first entry, and if three cells of a $2\cdot 2$ squares are colored, we can easily determine the color of the last. Therefore, there are exactly two colorings of the next row. It remains to show both coloring work. Note $f$ is a bijection, so clearly no two squares sharing a side contain the same letter. Also, easy casework reveals that any 2 by 2 square contains all colors. Let $t_i$ be the number of $t$’s on row $i$ and define $m_i, o_i$ similarly. By the third condition, $\sum\limits_{i=1}^{2021} (t_i+m_i\omega_3+o_i\omega_3^2)=0$. On the other hand, we know $t_i+m_i\omega_3+o_i\omega_3^2=\omega_3^{k_i} (t_1+m_1\omega_3+o_1\omega_3^2)$ for some $0\le k_i <3$ Let $a_i$ be the number of solutions to $k_j=i $. Then, our sum is equal to $(t_1+m_1\omega_3+o_1\omega_3^2)(a_0+a_1\omega_3+a_2\omega_3^2)=0$ note $k_0, k_1, k_2\in\mathbb{Z}, a_0+a_1+a_2=2021$, so $a_0+a_1\omega_3+a_2\omega_3^2\ne 0, $ so $t_1=m_1=o_1,$ as desired.
Physicsknight
12.04.2021 19:20
Replace $T,M,O$ with $X,Y,Z$. Consider any subsquare $2\times 2$. Observe that, it has to be in two diagonal form. $X-(\star),b -X(\bullet), -XX-$ with $X$. $-$ denotes the arbitrary letter in $\{X,Y,Z\}$. Call $\cal A$ is the first row. Consider the second row, combine with the first row to form a well-formed array of the validate squares of $2\times 2$.There will be $B,C$ is dependent what we consider with the first row, a diagonal $2\times 2$ square $(\star),\, \text{and},\,\,(\bullet)$ $\textbf{Wlog},$ assume that row is $B$. Continue with the third row. There are $2$ choices first row, or row $C$. We have all rows, which has to be of type $A,B,C$. Denote their numbers with $p,q,r$. In three rows $\{\mathcal{A},B,C\}$ the total number of $|X|=\text{number of }\,\,|Y|$ . I will write down rest prove bit later, sorry.