Задача
В клетчатом квадрате между каждыми двумя соседними по стороне клетками есть закрытая дверь. Жук начинает с какой-то клетки и ходит по клеткам, проходя через двери. Закрытую дверь он открывает в ту сторону, в которую идёт, и оставляет дверь открытой. Через открытую дверь жук может пройти только в ту сторону, в которую дверь была открыта. Докажите, что если жук в какой-либо момент захочет вернуться в исходную клетку, то он сможет это сделать.
Решение
Если до какой-то закрытой двери можно добраться, направим жука к ней и откроем. Продолжим этот процесс. Общее количество закрытых дверей уменьшается, значит, в некоторый прекрасный момент не останется закрытых дверей, до которых можно дойти.
Предположим, что в этот момент осталось непустое множество $N$ недостижимых клеток. Оставшиеся клетки образуют множество $D$ достижимых клеток. Заметим, что все двери между $N$ и $D$ открыты в сторону $D$. Ясно, что таких дверей хотя бы две. Это значит, что жук когда-то открыл одну из них, попал в $D$, а потом смог вернуться в $N$, чтобы открыть вторую дверь. Но нет двери, через которую он мог попасть в $N$. Противоречие.
Следовательно, в прекрасный момент все клетки достижимы и жук может вернуться в исходную клетку.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь