8. In each of the $k$ cells of an $n \times n$ square table, a one is written, and in the remaining cells - a zero. Find the maximum value of $k$, such that regardless of the initial placement of the ones, by swapping rows with each other and columns with each other, it is possible to achieve that all ones are above the secondary diagonal or on it? (The secondary diagonal is the one that runs from the bottom left corner to the top right corner. An example is provided in the figure: the contents of the cells lying above the secondary diagonal or on it are marked in bold.)
Solution: We will denote a table of size $n \times n$ as $\mathbf{T}_{n}$. It is obvious that for the table $\mathbf{T}_{2}$, the maximum $k$ is 3. Experimenting with the table $\mathbf{T}_{3}$, we can notice that $k=4$ (we will prove this rigorously below). These observations allow us to hypothesize that for any $n>1$, the maximum value of $k$ is $n+1$. We will prove this. First, we will show that the table cannot contain $n+2$ ones. For this, we will provide a counterexample, but first, let's recall the definition of a transversal.

| $\mathbf{0}$ | $\mathbf{1}$ | $\mathbf{0}$ | $\mathbf{0}$ |
| :--- | :--- | :--- | :--- |
| $\mathbf{0}$ | $\mathbf{0}$ | $\mathbf{0}$ | 0 |
| $\mathbf{1}$ | $\mathbf{1}$ | 0 | 0 |
| $\mathbf{0}$ | 0 | 0 | 0 |

A transversal of the table $\mathbf{T}_{n}$ is a set of $n$ cells containing 1, any two of which are in different rows and different columns. It is clear that if some cells form a transversal, then after permuting rows or columns, they will again form a transversal. The figure shows a table $n \times n$ with $n+2$ ones located on the main diagonal, as well as in the $2 \times 2$ table in the upper left corner. This table contains two transversals. At the same time, a table where all 1s lie on or above the secondary diagonal contains no more than one transversal. Therefore, the table in the figure cannot be brought to the required form. Hence, $k \leq n+1$.

$\left(\begin{array}{cccc}1 & 1 & & 0 \\ 1 & 1 & & 0 \\ & 0 & \ddots & \\ & 0 & & 1\end{array}\right)$

$n+2$ ones and two transversals

We will show that $n+1$ ones can always be moved to the secondary diagonal or above. So, we are given a table $\mathbf{T}_{n}$ containing $01$ and $k=1$ when $n=1$.


[^0]:    Answer: It will not be able to.