Japan Mathematical Olympiad

$\left(\genfrac{}{}{0ex}{}{198}{100}\right)\cdot 3\cdot 2^{100}$

STEP 1 In this step, we give $\left(\genfrac{}{}{0ex}{}{198}{100}\right)\cdot 3\cdot 2^{100}$ possible ways of filling satisfying the two conditions. Let ${\ell }_1,\dots ,{\ell }_{99}$ be the horizontal grid lines of the table, and let ${\ell }_1^{\prime },\dots ,{\ell }_{99}^{\prime }$ be the vertical grid lines of the table. We have exactly $\left(\genfrac{}{}{0ex}{}{198}{100}\right)$ ways to choose 100 lines from 198 lines ${\ell }_1,\dots ,{\ell }_{99},{\ell }_1^{\prime },\dots ,{\ell }_{99}^{\prime }$. Furthermore, there are $3\cdot 2^{100}$ sequences $a_1,\dots ,a_{101}$ of letters J, M, and O such that adjacent letters are different. We fix one way of choosing 100 grid lines and one sequence $a_1,\dots ,a_{101}$. For these choices, we give a way of filling the $100\times 100$ table as follows: Let $s$ be the number of the horizontal grid lines among the chosen 100 grid lines. Then, there are $100-s$ vertical grid lines among the chosen 100 lines, and the $100\times 100$ table is divided into $(s+1)(101-s)$ many rectangular-shaped blocks. For $1\le i\le s+1$ and $1\le j\le 101-s$, let $[i,j]$ denote the block located at the $i$-th row from the top and the $j$-th column from the left. Then, for each $i$ and $j$, we fill the squares in the block $[i,j]$ with the letter $a_{i+j-1}$.

By this way of filling, the squares within the same block have the same letter. On the other hand, two squares in adjacent blocks have different letters since adjacent letters in the sequence $a_1,\dots ,a_{101}$ are different.

Lemma 1. This way of filling satisfies the first condition of the problem.

Proof of Lemma 1. We fix a $2\times 2$ square in the $100\times 100$ table. Let $N$ be the number of chosen grid lines passing through the interior of the $2\times 2$ square. The possibility of $N$ is either $N=0,1,2$. When $N=0$, the $2\times 2$ square is contained in one block, and the four squares have exactly one type of letter. When $N=1$, the $2\times 2$ square crosses over two blocks. In this case, the four squares in the $2\times 2$ square have exactly two types of letters, and each letter appears twice. When $N=2$, the $2\times 2$ square crosses over four blocks. Let $[i,j]$ be the block containing the upper-right square of the $2\times 2$ square. Then, the block $[i+1,j-1]$ contains the lower-left square of the $2\times 2$ square. By the way of filling, those two squares have the same letter. In any case, it has been shown that the $2\times 2$ square is a good block, which completes the proof of Lemma 1. ■

Lemma 2. This way of filling satisfies the second condition of the problem.

Proof of Lemma 2. By the way of filling, for a pair of two adjacent squares of the table, the following two conditions are equivalent: The two squares have different letters. The two squares are separated by one of the chosen 100 grid lines. Therefore, we conclude that there are exactly $100\cdot 100=10000$ pairs whose two squares have different letters, which completes the proof of Lemma 2. ■

Thus, we have established a way of filling from a choice of 100 grid lines and a choice of a sequence. Since different choices give different fillings, we have proved that there are at least $\left(\genfrac{}{}{0ex}{}{198}{100}\right)\cdot 3\cdot 2^{100}$ possible ways of filling satisfying the two conditions.

STEP 2 We suppose that the squares of the $100\times 100$ table are filled to satisfy the two conditions. In this step, we will prove that such way of filling is one of the ways given in STEP 1.

Let $(i,j)$ denote the square in the $i$-th row from the top and $j$-th column from the left. Furthermore, $f(i,j)$ denotes the letter written in the square $(i,j)$.

First, we will prove the following two lemmas.

Lemma 3. Let $a$ and $b$ be integers satisfying $1\le a,b\le 99$. Then, the two conditions $f(a,b)=f(a,b+1)$ and $f(a+1,b)=f(a+1,b+1)$ are equivalent. Furthermore, the two conditions $f(a,b)=f(a+1,b)$ and $f(a,b+1)=f(a+1,b+1)$ are equivalent.

Proof of Lemma 3. We will show that $f(a,b)=f(a,b+1)$ implies $f(a+1,b)=f(a+1,b+1)$. Let $N$ denote the number of types of letters written in the four squares $(a,b),(a,b+1),(a+1,b),(a+1,b+1)$. Here, we have $N\le 3$ by the definition of a good block. If $N=1$, then we have $f(a+1,b)=f(a+1,b+1)$ and it shows the assertion. If $N=2$, then each letter appears exactly twice by the definition of a good block, and hence, we conclude that $f(a,b)=f(a,b+1)$ implies $f(a+1,b)=f(a+1,b+1)$. If $N=3$, then we have $f(a+1,b)=f(a,b+1)$ by the definition of a good block. Since $N=3$, we have $f(a,b)\ne f(a,b+1)$ and it shows the assertion. We have proved that $f(a,b)=f(a,b+1)$ implies $f(a+1,b)=f(a+1,b+1)$. The other implications can be proved similarly. ■

Lemma 4. Let $a$ and $b$ be integers satisfying $1\le a,b\le 99$. If $$f(a,b)\ne f(a,b+1)\ne f(a+1,b+1)\ne f(a+1,b)\ne f(a,b),$$ then we have $f(a+1,b)=f(a,b+1)$.

Proof of Lemma 4. Let $N$ denote the number of types of letters written in the four squares $(a,b)$, $(a,b+1)$, $(a+1,b)$, and $(a+1,b+1)$. Here, we have $N\le 3$ by the definition of a good block, and $N\ge 2$ by the assumption $f(a,b)\ne f(a,b+1)$. When $N=2$, the assertion $f(a+1,b)=f(a,b+1)$ follows from the assumption $f(a,b)\ne f(a,b+1)\ne f(a+1,b+1)$. When $N=3$, the assertion $f(a+1,b)=f(a,b+1)$ follows from the definition of a good block. ■

When two squares sharing an edge have different letters, we call such shared edge a boundary edge. From Lemma 3, for each integer $a$ with $1\le a\le 99$, we conclude that either all edges shared by a square on the $a$-th row and a square on the $(a+1)$-th row are boundary edges, or none of them are boundary edges. The same assertion holds for columns as well. Therefore, the union of the boundary edges forms a collection of some of the grid lines ${\ell }_1,\dots ,{\ell }_{99},{\ell }_1^{\prime },\dots ,{\ell }_{99}^{\prime }$. Let $s$ denote the number of horizontal grid lines obtained by the horizontal boundary edges, and let $t$ denote the number of vertical grid lines obtained by the vertical boundary edges. Then, by the boundary edges, the $100\times 100$ table is divided into $(s+1)(t+1)$ many rectangular-shaped blocks. By the definition of a boundary edge, the squares within the same block have the same letter, and two squares in adjacent blocks have different letters. Therefore, the number of pairs of adjacent squares sharing a boundary edge is exactly $100(s+t)$. Hence, by the second condition of the problem, we conclude that $t=100-s$.

For $1\le i\le s+1$ and $1\le j\le t+1=101-s$, let $[i,j]$ denote the block located at the $i$-th row from the top and the $j$-th column from the left. Note that the squares in the block $[i,j]$ have the same letter, and we denote the letter by $g(i,j)$. We define a sequence $a_1,\dots ,a_{101}$ of letters J, M, and O by $$\begin{gathered} a_1=g(1,1),a_2=g(2,1),\dots ,a_{s+1}=g(s+1,1), \\ {a}_{s+2}=g(s+1,2),\dots ,a_{101}=g(s+1,t+1). \end{gathered}$$ Then, adjacent letters of the sequence are different.

By Lemma 4, we have $$g(i,j)=\{\begin{array}{ll}g(i+j-1,1)& \text{if }i+j-1\le s+1\\ g(s+1,i+j-s-1)& \text{otherwise}\end{array}=a_{i+j-1}$$ for any $1\le i\le s+1$ and $1\le j\le t+1=101-s$. Therefore, this way of filling coincides with the way given in STEP 1 corresponding to the choice of the 100 grid lines and the sequence $a_1,\dots ,a_{101}$.

By STEP 1 and STEP 2, we conclude that there are exactly $\left(\genfrac{}{}{0ex}{}{198}{100}\right)\cdot 3\cdot 2^{100}$ ways of filling satisfying the two conditions.