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