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

На доске 5х5 клеток всего 25 клеток, и в каждой из них изначально сидит один жук. Таким образом, всего жуков на доске — 25.

Когда жуки переползают на соседние клетки, каждый жук может пересесть либо вверх, вниз, влево или вправо, но не может покинуть пределы доски.

Причина, по которой не может произойти ситуация, когда все клетки заняты жуками (и ни одной клетки не будет пустой), заключается в том, что при каждом перемещении жука обязательно меняется состояние клеток: если жук уходит из одной клетки в другую, он оставляет первую клетку пустой (или "освобождает" её). Таким образом, по правилам (каждый жук может перемещаться только на смежные клетки), невозможно, чтобы при одном движении каждый жук занял новую клетку и при этом осталась бы занятая клетка — всегда будет хотя бы одна клетка, которую жук покинет, и она станет пустой.

Это можно продемонстрировать на любом примере: если все жуки сдвинутся, то один жук должен будет оставить свою клетку, и таким образом, в любом случае останется хотя бы одна пустая клетка.

Таким образом, обязательно будет хотя бы одна пустая клетка после переползания всех жуков.