Дана таблица $n\times n$, столбцы которой пронумерованы числами от $1$ до $n$. В клетки таблицы расставляются числа $1,2,\cdots,n$ так, что в каждой строке и в каждом столбце все числа различны. Назовем клетку хорошей, если читсло в ней больше номера столбца, в котором она находится. При каких $n$ существует расстановка, в которй во всех строках одинаковое количество хороших клеток?

Решение

Найдем общее количество хороших клеток. В первом столбце их $n-1$ (все, кроме клетки с числом 1), во вторм их $n-2$ (все, кроме клетки с числом 1 и 2) и т.д., в последнем столбце таких клкеток нет. Значит, всего их $(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$

Поэтому в каждой строке их должно быть по $\frac{n-1}{2}$, следовательно, $n$ должно быт ьнечетным.

Приведем пример расстановки при нечетном $n$. Пусть в первой строке записаны числа в порядке $1,n,n-1,n-2,\cdots,2$

а каждая следующая строка является циклическим сдвигом предыдущей строки на 1 клетку (см.рис.). Очевидно, в любой строке и в любом столбце каждое из чисел $1,2,\cdots,n$ встречается по одному разу. Рассмотрим $m$-ю строку ( $m\in \left \{ 1,2,\cdots,n \right \}$). В ее первых $m$ клетках стоят числа $1,2,\cdots,m$ в обратном порядке, поэтому среди этих клеток ровно $\left [\frac{m}{2} \right]$ хороших. В ее последних $n-m$ клетках(т.е. в столбцах с номерами $m+1,m+2,\cdots,n$) стоят числа $m+1,m+2,\cdots,n$ в обратном порядке, поэтому среди этих клеток ровно $\left [\frac{n-m}{2} \right]$ хороших. Так как числа $m$ и $n-m$ разной четности, то в $m$-й строке ровно $\left [\frac{m}{2} \right]+\left [\frac{n-m}{2} \right]=\frac{m}{2}+\frac{n-m}{2}-\frac{1}{2}=\frac{n-1}{2}$ хороших клеток.