|
|
 |
Условие
Дана таблица n×n, столбцы которой пронумерованы числами от 1 до n. В клетки таблицы расставляются числа 1, ..., n так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку хорошей, если число в ней больше номера столбца, в котором она находится. При каких n существует расстановка, в которой во всех строках одинаковое количество хороших клеток?
Решение
Найдём общее количество хороших клеток. В первом столбце их n – 1 (все, кроме клетки с числом 1), во втором – n – 2 (все, кроме клеток с числами 1 и 2) и т. д., в последнем столбце таких клеток нет. Значит, всего их (n – 1) + (n – 2) + ... + 1 = ½ n(n – 1). Поэтому в каждой строке их должно быть по n–1/2. Следовательно, n нечётно.
Приведём пример расстановки для n = 2k + 1.
В каждой строке стоит циклическая перестановка ряда 2k + 1, 2k, ..., 1. При этом, как нетрудно видеть, в 2i-й строке хорошими будут первая i – 1 клетка и клетки с 2i-й по (k+i)-ю, а в (2i–1)-й строке – первая i – 1 клетка и клетки с (2i–1)-й по (k+i–1)-ю. Таким образом, в каждой строке ровно k хороших клеток.
Ответ
При нечётных n.
