M2103

Дана таблица 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 должно быт ьнечетным.

1 n n-1 \cdots 2
2 1 n \cdots 3
3 2 1 \cdots 4
\vdots \vdots \vdots \ddots \vdots
n-1 n-2 n-3 \cdots n
n n-1 n-2 \cdots 1

Приведем пример расстановки при нечетном 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} хороших клеток.

M2103: 2 комментария

    1. Вы это самостоятельно должны решить. Я давал задание подготовить математические задачи. Пообещал выставить оценки за разметку, формулы и рисунки. Конечно, можно было и другим способом продемонстрировать свои знания и навыки (что Вы и сделали), но я выбрал такой.

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

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