Лабиринт имеет размеры 8 на 8 клеток. Вы находитесь в левом нижнем углу. Выход расположен в правом верхнем углу. За один ход можно переместиться в направлении стрелки в соседнюю клетку. После того, как вы ушли из клетки, направление в ней меняется на 90 градусов по часовой стрелке. Если границы лабиринта мешают двигаться дальше, то вы остаётесь в клетке, а направление в ней поворачивается на 90 градусов по часовой стрелке и следующий ход можно сделать в новом направлении. Докажите, что из этого лабиринта можно выбраться при любом начальном положении стрелок в клетках.
update
Первый - Andrew Antonets.Ответ
Предположим, что вы останетесь в лабиринте навсегда. Так как число клеток конечно, то по крайней мере одну из них вы посетите бесконечное число раз. А так как направление в этой клетке меняется после каждого посещения, то все смежные клетки вы также посетите бесконечное число раз. И так далее. Таким образом правую верхнюю клетку вы также посетите бесконечное количество раз. Но в какой-то момент она будет указывать на выход. Следовательно, остаться в лабиринте навсегда нельзя.
Если границы лабиринта мешают двигаться дальше, то вы остаётесь в клетке, а направление в ней поворачивается на 90 градусов по часовой стрелке и следующий ход можно сделать в новом направлении.
ОтветитьУдалитьПо-моему, этим всё сказано. Как только тупик, можно сидеть в клетке и ждать удобного направления.
Если тупик, я остаюсь, направление стрелки меняется, но это всё равно тупик, то уже нельзя делать очередной простой и это проигрыш? Или можно?
>Как только тупик, можно сидеть в клетке и ждать удобного
Удалить>направления.
Не совсем так. Получается, что ждать можно не удобного направления, а первого возможного.
>Если тупик, я остаюсь, направление стрелки меняется, но это
>всё равно тупик, то уже нельзя делать очередной простой и это
>проигрыш? Или можно?
Если в новом направлении двигаться тоже нельзя, то стрелка поворачивается ещё раз и продолжаете двигаться дальше. Проигрыша здесь быть не может
Спасибо. Я это и имел в виду. Первое возможное назвал "удобным".
УдалитьПолучается, какой бы тупик не был, выйти можно, потому что я буду ждать первого возможного направления, а одно из четырёх в любом случае будет первым возможным.
По-моему, нужно добавить в условие то, что в клетке можно оставаться не на один раз, а на несколько. Хотя тогда решать ничего не останется. А в таком виде воспринимается, будто в каждой клетке есть право только на один пропуск хода.
Хотя если после первой смены направления остаётся тупик, то мы как бы возвращаемся по условию в то положение, когда опять можно остаться.
Тупики тупиками, но у тебя нет доказательства того, что ты не будешь ходить "кругами" и обязательно доберёшься до клетки выхода в нужном направлении.
Удалитьу меня такие мысли - если есть способ обойти клетку выхода - значит существует контур, который возвращает нас в исходную клетку. Но возвращаться в клетку мы будем каждый раз через другую ячейку, которая будет отворачиваться, в конце концов при любых комбинациях стрелок около стрелки старта получим такую, что вернуться назад не сможем. Значит контура замкнутого не существует, а это значит что волей не волей человек обойдет все клетки и по несколько раз в конце концов выйдя из нужной.
ОтветитьУдалить> если есть способ обойти клетку выхода - значит существует
Удалить> контур, который возвращает нас в исходную клетку.
Вот это не очень понятно. Почему не может быть контура, по которому мы будет постоянно обходить исходную клетку.
Еще попытка!
ОтветитьУдалитьПредположим, что существует клетка, на которую лабиринт не приведет никогда! Тогда клетки вокруг него должны быть все развернуты от него. А клетки вокруг развернутых клеток могут быть пройдены не более трех раз. Про клетки третьего уровня нужно делать тоже предположение, что их не должны посетить не более 6 раз - при этом условии можно исключить вероятность поворота стрелки вокруг нашей непосещаемой клетки внутрь.
Рассуждая таким образом приходим к выводу, что найти клетку, которая не будет посещена не разу, при любом расположении стрелок можно, только если количество ходов конечно.
Из рассуждения получается, что каждую клетку мы посетим хотя бы один раз. Но это же не значит, что мы выйдем из лабиринта.
Удалитьа нельзя аналогично методом от противного предположить, что есть клетка, которую посещают не более три раза, тогда окружающие клетки должны быть заняты не более 9 раз, клетки третьего уровня не более 81 раза и т.д. и если количество ходов бесконечно, то существование такой клетки невозможно. Это означает что на клетке вверху справа мы побываем более 3 раз.
УдалитьТо есть если работает принцип - можно посетить любую клетку, сколько угодно раз, так как окружающие ее клетки рано или поздно разворачиваются на целевую клетку и для этого нужно большое(но конечное) посещение соседних клеток, то дальнейшее доказательство выглядит очевидным.
У меня было похожее доказательство.
УдалитьПопробуем рассуждать от противного. Пусть при определенном начальном расположении стрелок выйти из лабиринта не получится. Так как принцип передвижения между клетками не подразумевает тупиков, и из любой клетки через один или два хода ожидания можно выйти, то отсутствие выхода из лабиринта означает, что существует некий маршрут, по которому мы будем ходить бесконечно. Рассмотрим клетки этого маршрута, найдем среди этих клеток находящиеся правее всех, а из них выберем самую верхнюю. В эту клетку мы будем попадать бесконечное число раз. Когда из нее мы уйдем вниз, стрелка в ней повернется влево. После ухода влева стрелка повернется вверх. При следующем заходе по маршруту вверх мы не уходим (клетка самая верхняя в своем ряду из клеток маршрута), выходит, что там стена и мы ждем поворота стрелки вправо. Но и вправо мы по маршруту не уходим (т.к. клетка одна из самых правых по маршруту), т.е. и справа стена. Получается, что выбранная клетка - правый верхний угол лабиринта. А значит мы можем выйти из него, когда при одном из заходов стрелка будет направлена вверх.
ОтветитьУдалитьВроде бы всё сходится.
Удалить