Andjans A.

In a table with $m$ rows and $n$ columns, a horizontal move is defined as a permutation of the elements in the table such that each element remains in the same row it was in before the permutation; similarly, a vertical move is defined ("row" in the previous definition is replaced with "column"). Determine such a $k$ that any permutation of the elements in the table can be achieved in $k$ moves (of any kind), but there exists a permutation that cannot be achieved in fewer moves.
The case $m=1$ or $n=1$ is trivial.

Let $m \neq 1$ and $n \neq 1$. We will show that two moves are insufficient. Suppose in the initial table, the top-left

![](https://cdn.mathpix.com/cropped/2024_05_06_caf98da37e6d9925b347g-03.jpg?height=120&width=2018&top_left_y=969&top_left_x=0)

square is \begin{tabular}{|l|l|}
\hline \& $b$ 
\cline { 1 - 3 } \& $c$

. In one move, $d$ cannot be converted to $a$, so $d$ must move on the first move, either to the position of $b$ or to the position of $c$. Due to symmetry, it makes no difference; suppose $d$ moves to the position of $c$. Then, by the same reasoning, $a$ moves to the position of $b$, so the top-left square becomes

$*$ \& $a$ 
\hline \& $*$ 
\cline { 1 - 3 }
\end{tabular} (where $*$ denotes any element). In this case, $c$ remains in the second row. The next, second move must be vertical to place $d$ and $a$ in their correct positions, but $c$ is not in the first column, so the required table cannot be achieved.

For further discussion, we need the

Marriage Theorem. Suppose there are $n$ young men, and for each $k \leq n$, the following condition is satisfied: for any group of $k$ young men, there are at least $k$ young women who are acquainted with these young men. Then each young man can be married to a young woman he knows.

Lemma. Suppose in an $m \times n$ table, the numbers from 1 to $m$ are arranged such that each number appears $n$ times. Then in each row, one can choose a number such that all chosen numbers are distinct.

Proof. We will consider that in the $j$-th row, the numbers represent the indices of the young women acquainted with the $j$-th young man (the fact that one number can appear multiple times is irrelevant). The condition of the Marriage Theorem is satisfied: in any $k$ rows, there are at least $k$ distinct numbers. Indeed, in $k$ rows, there are $k n$ positions, and $k-1$ distinct numbers in the table occupy $(k-1) n < k n$ positions.

We will now show that any permutation of the elements of the table in the problem can be achieved in three moves.

By the lemma, in each row, one can choose an element that, after the permutation, should end up in different rows. We will gather them in the first column with a horizontal move. Applying the lemma to the table without the first column, we will gather (with the same move) in the second column elements that should also end up in different rows, and so on.

The second move will rearrange the elements in each column so that all elements of the table end up in the rows where they should be after the permutation (in each column, the elements whose interests are distinct are gathered, so this is possible).

The third move will place the numbers in each row in their correct positions.

## Answer

If $m=1$ or $n=1$, then $k=1$; otherwise, $k=3$.

Send a comment