9.4. All cells of a $100 \times 100$ square table are numbered in some order with numbers from 1 to 10000. Petya colors the cells according to the following rules. Initially, he colors $k$ cells at his discretion. Then, on each move, Petya can color one more uncolored cell with number $a$ if at least one of the two conditions is met: either there is an already colored cell with a number less than $a$ in the same row; or there is an already colored cell with a number greater than $a$ in the same column. What is the smallest $k$ such that, regardless of the initial numbering, Petya can color all the cells of the table in several moves?

(S. Berlov)
Answer. $k=1$.

Solution. First, let's prove the following statement.

Lemma. For any two cells $A$ and $B$, there exists a cell $C$ such that by coloring it, one can then color both $A$ and $B$ (possibly $C$ coincides with $A$ or $B$).

Proof. We can assume that the number $a$ of cell $A$ is less than the number $b$ of cell $B$. Let $D$ be the cell in the same column as $A$ and in the same row as $B$, and let $d$ be its number (possibly $D=A$ or $D=B$). Then, if $d < a$, after coloring $A$, one can sequentially color $D$ and $B$. If $d > b$, after coloring $B$, one can sequentially color $D$ and $A$. Therefore, in any case, one can choose $C$ as one of the cells $A$, $B$, or $D$. The lemma is proved.

Now, let's proceed to the solution of the problem. It is clear that $k \geqslant 1$; hence, it is sufficient to prove that when $k=1$, the coloring is always possible.

Fix an arbitrary numbering of the cells. Consider all ways of coloring the cells according to the condition (for $k=1$) and choose the one in which the number of colored cells is maximal. Let $A$ be the first colored cell in this way. Suppose that in this way, some cell $B$ remains uncolored. Then, by choosing the corresponding cell $C$ according to the Lemma and starting the coloring from it, we can then color $B$, $A$, and, consequently, all the cells that were colored in the chosen way. Thus, we will color at least one more cell. The contradiction with the choice of the way shows that in fact, all cells will be colored in our way. This means that $k=1$ works.

## 10th grade