M2103. Таблица с разными числами в строке и столбце

Условие

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

Решение

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

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

[latex]1[/latex] [latex]n[/latex] [latex]n-1[/latex] [latex]\cdots[/latex] [latex]2[/latex]
[latex]2[/latex] [latex]1[/latex] [latex]n[/latex] [latex]\cdots[/latex] [latex]3[/latex]
[latex]3[/latex] [latex]2[/latex] [latex]1[/latex] [latex]\cdots[/latex] [latex]4[/latex]
[latex]\vdots[/latex] [latex]\vdots[/latex] [latex]\vdots[/latex] [latex]\ddots[/latex] [latex]\vdots[/latex]
[latex]n-1[/latex] [latex]n-2[/latex] [latex]n-3[/latex] [latex]\cdots[/latex] [latex]n[/latex]
[latex]n[/latex] [latex]n-1[/latex] [latex]n-2[/latex] [latex]\cdots[/latex] [latex]1[/latex]

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

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

К.Чувилин

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *