Exercise 2. We place the integers from 1 to 9 in each of the cells of a $3 \times 3$ grid. For $i=1$, 2 and 3, we denote $\ell_{i}$ as the largest integer present in the $i$-th row and $c_{i}$ as the smallest integer present in the $i^{\text{th}}$ column.

How many grids exist such that $\min \left\{\ell_{1}, \ell_{2}, \ell_{3}\right\}=\max \left\{\mathbf{c}_{1}, \mathrm{c}_{2}, \mathrm{c}_{3}\right\}=4$?
Solution to Exercise 2 Let G be any grid, and let $i$ and $j$ be the integers such that the integer 4 is located on the $i^{\text{th}}$ row and the $j^{\text{th}}$ column. We say that the grid $\mathrm{G}$ is good if $\ell_{i}=\mathrm{c}_{j}=4$.

First, if $\min \left\{\ell_{1}, \ell_{2}, \ell_{3}\right\}=\max \left\{c_{1}, c_{2}, c_{3}\right\}=4$, then $4=\ell_{i}=c_{j}$, so $G$ is a good grid. Conversely, if $G$ is a good grid, then for any integer $j^{\prime}$, the column $j^{\prime}$ contains one of the integers from the row $i$. This integer is therefore at most 4, which shows that $c_{j^{\prime}} \leqslant 4$. Similarly, for any integer $i^{\prime}$, we have $\ell_{i^{\prime}} \geqslant 4$. Therefore, we indeed have $\min \left\{\ell_{1}, \ell_{2}, \ell_{3}\right\}=\max \left\{c_{1}, c_{2}, c_{3}\right\}=4$.

Consequently, we are actually trying to count how many good grids there are. To construct a good grid, it suffices to choose successively:

$\triangleright$ the integers $i$ and $j$, i.e., the position of the 4: there are 9 possible choices;

$\triangleright$ each of the two other integers that are on the row $i$. Since $l_{i}=4$, these two integers must be smaller than 4, so they must be chosen from $\{1,2,3\}$. There are 3 ways to choose the first (say the leftmost), and 2 ways to choose the second;

$\triangleright$ each of the two other integers that are on the column $j$. Since $c_{j}=4$, the two other integers must be greater than 4, so they must be chosen from $\{5,6,7,8,9\}$. There are 5 ways to choose the first, and 4 ways to choose the second;

$\triangleright$ each of the four remaining integers to be placed: there are 4! ways to proceed. Therefore, there are $9 \times 3 \times 2 \times 5 \times 4 \times 4!=25920$ grids such that $\min \left\{\ell_{1}, \ell_{2}, \ell_{3}\right\}=\max \left\{\mathrm{c}_{1}, \mathrm{c}_{2}, \mathrm{c}_{3}\right\}=4$.

Remark: In general, regardless of the size of the grid, the smallest of the integers $\ell_{i}$ is necessarily equal to the largest of the integers $\mathrm{c}_{\mathrm{i}}$. This is known as the Minimax Theorem. More information on this is available at:

$$
\text{en.wikipedia.org/wiki/Minimax_theorem}
$$