В каждой клеточки клетчатый доски семь на одиннадцать сидит жук в какой то момент времени все жуки переползает в одну из соседних клеточек которая имеет с ними общую сторону докажите что после этого какая то из клеток будет пустой то есть без жука

Предыдущий
вопрос Следующий
вопрос

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

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

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

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