Назад

Олимпиадная задача по комбинаторной геометрии о тараканах на шахматной доске

Задача 211267 • Сложность: 3 • 8-11 класс
Задача

В каждой клетке шахматной доски сидят по два таракана. В некоторый момент времени каждый таракан переползает на соседнюю (по стороне) клетку, причём тараканы, сидевшие в одной клетке, переползают в разные клетки. Какое наибольшее количество клеток доски может после этого остаться свободным?

Решение

  Оценка. Закрасим 20 клеток доски так, как показано на рисунке слева. Каждая закрашенная клетка обладает следующим свойством: в какие бы две соседние клетки не переползли из неё тараканы, в эти клетки не смогут попасть тараканы ни из какой другой закрашенной клетки. Поэтому после переползания всех тараканов по крайней мере 40 клеток доски будет занято.

             
 Пример. Пусть все тараканы переползут в клетки, закрашенные так, как на рисунке справа. Поскольку каждая незакрашенная клетка граничит ровно с двумя закрашенными, то это возможно. При эхтом останутся свободными 24 клетки.

Ответ

24 клетки.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Войти Зарегистрироваться
Комментариев нет