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

Решение

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

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

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

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