Добрые инопланетяне

[Barbedo]

Добрые инопланетяне, прибывшие к нам на орбиту с дружественным визитом, для установления контакта любезно умыкнули Вас тепленьким к себе на корабль, буквально из постели от жены, убедились, что с галактическими языками у Вас не очень, согласно инструкции миссии просканировали Ваш мозг нейроспайдером, ну и из чистой любознательности загадали загадку. Отгадаешь, мол, - отпустим: "Наш корабль - он в виде тора, отсеки - сектора тора. Дверь вперед, дверь назад - все соединены. В отсеках включен свет, не во всех, а в случайном порядке. Можешь ходить по отсекам взад-вперед в любом направлении, можешь включать и выключать свет в любом отсеке сколько угодно раз. Требуется определить, сколько всего отсеков на корабле! Метить двери, отсеки мелом, пинком, разбитием лампочки или еще как нельзя."
И вот, стоите вы голый и ошарашенный босиком на холодном металлическом полу и озираетесь. Ни иллюминаторов, ни заметной кривизны стен или потолка, никаких косвенных признаков величины или направления кривизны тора не наблюдаете. Начинаете лихорадочно соображать, а можно ли, действительно, разгадать загадку, только включая и выключая свет в отсеках?
Домой-то хочется.

[Nadir Zaitov]

Сообщение от Barbedo

Домой-то хочется.

1. Нужно оговорить, что свет включенный сам не выключается и наоборот.
2. Нужно оговорить, что число комнат конечно, а то в 4-хмерном пространстве мы будем «заходить в разную воду». Межпланетный корабль может существовать в 4-х мерном пространстве (иначе тяжело двигаться между звездами с досветовой скоростью), стало быть тор может оказаться бутылкой Клёйна .
3. Комнаты линейно соединены по секторам тора Это ж инопланетяне. У них всякое бывает.
4. Считать нам не запретишь.

Теперь об идеальном варианте. Решение есть,

1. Выключим за спиной свет и назовем эту комнату нулевой.
2. В первой комнате включим свет. Проверим, что за спиной свет не погас (комната не одна)
3. Установим N=1;
4. Включаем свет в 2^N комнатах. (включен в них или выключен свет был - не важно если включен, то считаем, что включили мы и только что)
5. Возвращаемся обратно до нулевой комнаты (отсчитывая 2^N комнат назад).
7. Если свет в нулевой комнате выключен, то увеличиваем N на единицу, и идем к пункту 3 выше.
6. Если свет в нулевой комнате включен, то выключаем его и начинаем считать комнаты начиная с первой по первую комнату с выключенным светом. Конец (ответ число комнат).

Так как число комнат конечно и зациклено линейным циклом, 2^N сремится к бесконечности с ростом N, то рано или поздно ответ мы найдем.

[Timofeus]

Если не ош., количество отсеков можно определить лишь с той или иной степенью вероятности.

[Fedorov Stanislav]

А что мешает сначала включить все а потом наматывая круги выключать отсеки друг за другом, засекая количество кругов.

[Akmal Bafoev]

Сообщение от Fedorov Stanislav

А что мешает сначала включить все а потом наматывая круги выключать отсеки друг за другом, засекая количество кругов.

неизвестно общее количество, то есть их может быть сколь угодно большое конечное число.

[Nadir Zaitov]

Сообщение от Akmal Bafoev

А что мешает сначала включить все

Так вопрос же в том, что для того, чтобы "включить все" вы должны знать, что вы их все прошли. Комнаты условно абсолютно неотличимы. Так? Сначала нужно объять необъятное. Как только выяснится, что прошли все и веде включили свет, то дело конечно же простое: пометить начало и пересчитать. Это мы и сделали в самом конце.

[Fedorov Stanislav]

А естественные нужды организма в процессе подсчета не будут являться маркерами отсека?

[Nadir Zaitov]

Сообщение от Fedorov Stanislav

А естественные нужды организма в процессе подсчета не будут являться маркерами отсека?

А вообще, это оффтоп в теме. Задачка поставлено достаточно ясно.

Оффтоп:

А где гарантия, что маркеры не зеркализируюутся в других комнатах или не будут убраны автоматикой инопланетян? Нет. Т.е. и надежды на них нет.

[Ferrum]

Случайный порядок предполагает, что возможны циклические повторения сочетаний тёмных и светлых отсеков, от 2 до бесконечности. При таком раскладе невозможно будет ответить наверняка сколько отсеков.

[Vitaliy Fioktistov]

По-моему, единственная проблема, как определить, что ты в данном отсеке уже был.
Например, включаем свет в той комнате, в которой находимся, далее идем вперед и в каждой из следующих комнат свет гасим. До тех пор, пока не дойдем до протяженного темного участка (например, 1000 комнат), который прерывается одной освещенной, после которой снова идет 1000 неосвещенных комнат и за ними снова одна освещенная.
При этом огромная вероятность, что мы уже ходим по кругу, но есть определенная вероятность, что мы нарвались на естественный участок и еще не дошли до нашей первой комнаты.