Таблица из $n\times n$ клеток заполнена числами от 1 до $n$ так, как показано на рисунке. При каком $n$ в ней можно выбрать $n$ клеток так, чтобы никакие две клетки не принадлежали одной строке или одному столбцу и чтобы все числа в выбранных клетках были разные?
Легко видеть, что если $n$ — нечётное, то условию задачи удовлетворяют клетки диагонали, идущей из левого верхнего угла в правый нижний угол таблицы (в этих клетках стоят сначала все нечётные, а затем все чётные числа).
Докажем, что в случае чётного$n$ выбрать $n$ клеток нужным образом нельзя. Занумеруем строки таблицы снизу вверх: 1, 2, $\ldots$, $n$, а столбцы — слева направо. Обозначим через $a_{ij}$ число, стоящее на пересечении $i$-го столбца и $j$-й строки. Легко показать, что $$
a_{ij}=
\begin{cases}
i-j,&\text{если}~i\gt j,\\
i-j+n,&\text{если}~i\le j.
\end{cases}
$$
Поэтому, если все $n$ чисел $a_{ij}$ взять из разных строк и разных столбцов, то сумма их обязана делиться на $n$ ($i$ и $j$ пробегают все значения от 1 до $n$).
С другой стороны, если все эти $n$ чисел — разные, то это числа 1, 2, $\ldots$, $n$. Сумма их равна $\dfrac{n(n+1)}2$
и при чётном $n$ на $n$ не делится. Значит, в этом случае выбрать клетки так, как требуется в задаче, нельзя.
[Многие читатели ошибочно считали, что если все $n$ чисел взяты из разных строк и разных столбцов, то это обязательно числа, стоящие по диагонали таблицы (идущие из левого верхнего в правый нижний угол), и доказывали невозможность требуемого выбора (при чётных $n$) только для этого случая.]
