На всеукраинской олимпиаде 1989-го года предлагалась следующая задача (если я не ошибаюсь, фамилия автора задачи - Жук, что весьма символично
):
Цитата:
На каждой клетке доски размерами 9 × 9 сидит жук. По сигналу каждый жук переползает в одну из соседних по диагонали клеточек. При этом может оказаться, что в некоторых клетках будет по нескольку жуков, а некоторые клетки будут свободными. Найти наименьшее возможное число свободных клеток.
Несложно доказать, что менее 9 свободных клеток быть не может, ибо каждый из жуков переползает на горизонталь с номером иной чётности. На горизонталях с чётными номерами - 36 клеток, с нечётными - 45.
Несложно также привести пример, когда свободных клеток будет ровно 9:
Рассмотрим все диагонали "вправо-вниз". В 8 из них чётное число клеток, и жуки на каждой из этих диагоналей просто могут поменяться местами (первый со вторым, 3-й с 4-м и т. д.). В каждой из 9 других диагоналей нечётное (возможно 1) число клеток, крайнюю из них оставляем свободной (жук переползает из неё в соседнюю по этой диагонали клетку (если диагональ состоит из одной клетки, то жук переползает из неё в соседнюю клетку по диагонали "вправо-вверх")), а с чётным числом остальных поступаем аналогично четночисленным диагоналям (первый жук меняется со вторым, 3-й с 4-м и т. д.). По окончании всей этой процедуры ровно 9 клеток будут свободными.
А теперь новый вариант этой же задачи:
На каждой клетке доски размерами 9 × 9 сидит жук. По сигналу каждый жук переползает в одну из соседних по диагонали клеточек. При этом может оказаться, что в некоторых клетках будет по нескольку жуков, а некоторые клетки будут свободными.
Сколькими способами жуки могут переместиться так, чтобы как можно меньше клеток оказались свободными?
