Задача 98564

Темы:    [ Числовые таблицы и их свойства ] [ Шахматные доски и шахматные фигуры ] [ Правило произведения ]

Сложность: 4- Классы: 9,10,11

Условие

Автор: Шаповалов А.В.

Сколькими способами можно расставить числа от 1 до 100 в прямоугольнике 2×50 так, чтобы каждые два числа, различающиеся на 1, всегда попадали бы в клетки с общей стороной?

Решение

  Заметим, что существует взаимно-однозначное соответствие между способами расстановки чисел и обходами ладьей "доски" 2×50: если дан способ, то обходим клетки по порядку номеров; если дан обход, то нумеруем клетки в порядке обхода. Это соответствие даёт нам возможность рассуждать как на "языке способов расстановки", так и на языке "обходов ладьёй". Клетки с числами 1 и 100 назовём концами обхода.
  Обход может содержать зигзаг – цепочку ходов, где строго чередуются ходы по вертикали и горизонтали и при этом хотя бы один вертикальный ход сделан в некрайнем столбце (см. рис.; для удобства мы закрасили доску в шахматном порядке).

  Посмотрим, как ведёт себя обход на краях зигзага. Во-первых, зигзаг может дойти до конца обхода. Это может быть только край доски (как на левом краю рисунка), иначе зигзаг "отрежет" необойдённые клетки. Во-вторых, из зигзага можно выйти двумя горизонтальными ходами. Но тогда в другой горизонтали остаётся клетка с единственным "выходом", и там может быть только конец обхода. Итак, зигзаг всегда зажат между двумя (несоседними) столбцами с концами обхода, и поэтому других зигзагов в этом обходе нет. Кроме того, видно, что по зигзагу концы обхода однозначно восстанавливаются.
  С другой стороны, путь между краем доски и ближайшим столбцом с концом обхода восстанавливается однозначно (начните от края). Поэтому любой зигзаг (при заданном направлении) однозначно дополняется до полного обхода (см. рис.).

  Обход без зигзагов может состоять только из звеньев ломаной (как на следующем рисунке).

  Однако у этой ломаной 100 звеньев, а обход состоит из 99 звеньев. Поэтому все такие обходы получаются выкидыванием одного звена и соответствуют расположениям концов в соседних клетках по горизонтали или на крайней вертикали. Поскольку любой обход состоит из нечётного числа ходов, числа 1 и 100 лежат в клетках разного цвета. Кроме того, из вышесказанного видно, что в один столбец они попадают только если он крайний. Размещение пары 1 и 100, удовлетворяющее этим двум ограничениям, назовём допустимым. Мы уже показали, что по каждому допустимому размещению однозначно восстанавливается зигзаг (или его отсутствие), а следовательно, и весь обход.
  Подсчитаем количество допустимых размещений (это и будет искомое число способов). Забудем пока про второе ограничение. Тогда число 1 можно поставить куда угодно (100 возможностей), а после этого число 100 – в любую клетку другого цвета (50 возможностей), итого  100·50 = 5000  таких размещений. Чтобы учесть второе ограничение, надо выбросить размещения в некрайних столбцах. Всего есть 48 таких столбцов, в каждом можно разместить пару  {1, 100}  двумя способами. Значит, всего допустимых разбиений  5000 – 2·48 = 4904.

Ответ

4904 способами.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	2001/2002
Номер	23
вариант
Вариант	весенний тур, тренировочный вариант, 10-11 класс
Задача
Номер	4