Олимпиадная задача о хорошем клетке в таблице: теория чисел и комбинаторика для 8-10 классов
Дана таблица n×n, столбцы которой пронумерованы числами от 1 до n. В клетки таблицы расставляются числа 1, ..., n так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку хорошей, если число в ней больше номера столбца, в котором она находится. При каких 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хороших клеток.
Обсуждение
0Комментариев пока нет.