Задача 111267

Темы:    [ Вспомогательная раскраска (прочее) ] [ Принцип Дирихле (конечное число точек, прямых и т. д.) ] [ Таблицы и турниры (прочее) ] [ Геометрия на клетчатой бумаге ]

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

Условие

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

Решение

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

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

Ответ

24 клетки.

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

олимпиада
Название	Окружная олимпиада (Москва)
год
Дата	2008
класс
Класс	11
задача
Номер	2293576