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