Решение задачи 401

Условие:

На каждой клетке таблицы 8х8 сидит по два таракана. По команде все они переползают в соседнюю по ребру клетку так, что два таракана, сидящие в одной клетке, не могут снова оказаться в одной. Какое наибольшее число клеток после этого могут быть свободными?

Решение:

Оценка:

Выделим на доске 40 черных клеток следующим образом:

Эта раскраска хороша тем, что никакие два таракана, сидящие на черных клетках не могут переползти в одну клетку. Действительно, если два таракана сидят в одной черной клетке, то это им не позволяет сделать условие задачи. Если они сидят в соседних черных клетках, то они могут либо поменяться черными клетками, либо переползти в разные белые. Если же тараканы изначально находятся в черных клетках из разных пар, то раскраска устроена так, что никакая белая клетка не прилегает по ребру к двум черным, значит и тараканы в одну белую клетку не попадут.

Таким образом, все эти 40 тараканов, сидящие в черных клетках, переползут в разные клетки. Следовательно, хотя бы 40 клеток после команды будут заняты. Значит свободно будет не больше 24.

Пример:

Давайте заставим тараканов, сидящих изначально в красных клетках переползать в разные стороны, чтобы полностью заполнить периметры красных квадратов. А тараканов, сидящих в зелёных квадратах, заставим переползти на красные квадраты. Тогда все зелёные клетку станут свободными. Их всего 24.

Ответ: 24 клетки.