Докажем это методом противоречия.

Предположим, что после переползания все клеточки остаются занятыми жуками. Тогда каждая клеточка имеет хотя бы одного соседнего жука (так как жуки переползают только в клетки с общей стороной). Обозначим через N_i количество соседних клеточек для жука в клетке i.

Так как каждый жук имеет не менее одного соседа, сумма N_i по всем клеткам не может быть меньше, чем количество жуков, т.е. сумма N_i >= общее количество клеток. Однако, так как каждая клетка имеет не более 8 соседних клеток, сумма N_i не может превышать 8 * количество клеток. Получаем противоречие.

Следовательно, после переползания какая-то из клеток останется пустой, т.е. без жука.