[задача] про заключённых и лампочку

Во-первых не оговорено, включена лампа перед началом допроса или нет. Пусть будет выключена.

пусть 0-й выключает, их трое.

Порядок
0 - выключил.
1 - пришёл, включил (больше не трогает).
2 - пришёл, ничего не делает.
=== все побывали на допросе
далее вызывают 0-го до бесконечности. Он никогда не скажет "Да", значит их никогда не освободят.

Следовательно данное описание не позволяет им гарантированно освободиться.

Я так решил, что "в случайном порядке" в условии задачи означает "с равной вероятностью", поэтому, по законам статистики, при достаточно большом по сравнению с N количеством допросов, каждого заключенного будут вызывать по несколько раз. Вопрос о состоянии лампы до допроса, конечно, остается, но его можно решить даговорившись, например, что каждый должен включить по 2 раза. Таким образом, максимальное число включений лампы может быть 1 + 2 * (N - 1). Но уже после того, как (N - 1) * 2 она окажется включеной, заключенный, который ее выключает, может сделать вывод, что это было или 1 включение до начала допросов + 2*(N - 2) + 1 /*кто-то включил ее 1 раз, остальные по 2*/, или (N - 1) * 2 /*все включили по 2*/.

Словом, при любом раскладе (N - 1) * 2 включений наберется тогда и только тогда, когда каждый из N - 1 заключенных включит лампу хотя бы раз, независимо от того, была ли лампа включена вначале.

Ну или другой вариант: если есть возможность, то договорится, что в первый день кого-бы ни вызывали, тот выключает лампу, а дальше со следующего дня действуют по первому алгоритму.

s/договорится/договориться/

> Следовательно данное описание не позволяет им гарантированно освободиться.

ИМХО, тут и не будет гарантированного варианта освобождения. Возьмём приведённый вами крайний случай - всех вызывают по очереди и только 1 раз, а последнего - бесконечное количество раз. Лампочка чрезчур "бинарна", чтобы каждый вызванный заключённый мог бы "в ней отметиться". Последний заключённый получит информации ровно в один бит, который может быть израсходован на сообщение "ты последний" (да/нет) :) Но это неорганизуемо :))

Я тоже сомневаюсь в наличии корректного решения при поставленных условиях. А так приведённое решение по-моему правильно.

> Вопрос о состоянии лампы до допроса, конечно, остается, но его можно решить даговорившись, например, что каждый должен включить по 2 раза

Такая избыточность ни к чему. Считающий-выключающий просто должен увидеть включенную лампу не N-1, а N раз.

>ИМХО, тут и не будет гарантированного варианта освобождения.

Да, гарантированого нет. Тюремщики могут быть нечестны и вызывать только одного:) а могут сами играться и включать-выключать лампочку;)

> Да, гарантированого нет. Тюремщики могут быть нечестны и вызывать только одного:) а могут сами играться и включать-выключать лампочку;)

Ну, скажем, при приведённым Легионером раскладом - ни один из предложенных вариантов не даст освобождения. Хотя всех зеков честно вызовут и лампочку не тронут.