Затворникът започва с кутията със собствения му номер. Номерът вътре му указва коя кутия трябва да е следващата за проверка. И така докато не намери номера си или му свършат опитите.

Простичко... По-интересно е доказателството. При това обхождане задължително рано или късно се връщаш в кутията, от която си почнал. Демек независимо колко си разбърквал числата и независимо как индексираш кутиите (от ляво на дясно или дясно наляво) - винаги се получават един или повече кръгове.
Най-интересното е, че независимо колко кръга има общо, винаги уцелваш правилния кръг и винаги кутията която търсиш е последната в тоя кръг
Така всичко се свежда до дължината на най-големия кръг. Ако има кръг с повече от половината кутии, то всички от тоя кръг ще се издънят задължително. Очевидно може да има само един такъв кръг, но ако няма толкова дълъг кръг всички задължително си намират номерцата с толкова опита, колкото е дължината на кръга им.
Шансът при случайно подреждане да има кръг с повече от половината бройки е ln2. Демек шансът за успешно освобождаване на затворниците е 1-ln2, което е около 30%. Независимо дали са 100, 1000 или 1000 милиона.
За по-нагледно - последното видео на Veritasium

"извратена" форма на последователно приближение

една задачка за "green" ... с голямо самочувствие
може да затрудни и тези с опит, ако не се сетят

два бутона ======= две жици ======= две ламби

натискаш бутон А - пали ламба А
натискаш бутон Б - пали ламба Б
двата бутона - двете ламби

Търси се най-простото решение

Задачата е решена още в условието и...

обясни

Инсталацията променливотокова ли е?

Всеки бутон отива към лампа посредством жица. Какво има да се решава?

Грешка Трябват ти 3 жици.
С 2 жици (според мен) става само с диоди към ламБите и бутоните и променливо захранване. Ще се губи обаче половината мощност и ако лампите са с нажежаема жичка ще трепти (видимо).

А мцу-та допускат ли се?

Аха, не съм внимавал и съм пропуснал условието, че жиците са само две.
Това е непосилна задача. Има толкова много решения...
Диоди. Ако проектът трябва да зеленясва, шотки диоди. Ако трябва да е много зелен - активни изправители с фетове.
Става и с тиристори, триаци, вероятно и с още половин шепа чаркове...

В тубата имаше един юнак заиграващ се с идеята. Той свързваше всичко последователно. Беше го докарал до 4 или 6 це-ка ключа и толкова светодиода. И всеки ключ пали неговия си светодиод. Ако се нацъкат всички ключове свети всичко.

Зависи. Ако си в космоса - Тогава може би.
Но тук на Земята, винаги можеш да използваш ... Земята, като проводник.
Имаш 2 жици и една Земя - общо 3 проводника.

Допълнение: Ако се използват високи честоти и високо напрежение, постановката ще работи и на 10км над Земята (разбира се на по-ниска надморска височина ще работи по-добре). Тогава самия въздух ще се йонизира и ще играе ролята на трети проводник.

задачата трябва да бъде разказано достатъчно просто за да бъде подценена ( без да се дават съвети и напътствия )
и да се прецени как мисли "ученика"

уловката е, че е необходимо захранване за ламбите, а щом е необходимо и не е забранено значи всичко останало е позволено
в задачата няма качествени параметри ... да използваш земята е малко "ала-бала" ... да кажем е "непрактично" решение ( може да се забрани в условието - мой пропуск )
всъщност трета "жица" е забранена

практичното решение, може би най-простото е променливотоково захранване и 4 диода

1 000 000 fps
https://youtu.be/VgjyPmFKxCU?t=809

може и без диоди, но бутоните ще са с НО и НЗ контакти и захранването ще е от генератор на ток, а не на напрежение.
Лампите може да са и повече от две.
(не беше казано какви да са бутоните и какъв да е захранващият источник)

Е като нямаш натиснат бутон източника ти е на късо, или това което си сложил е генератор на ток, те така става глобалното затопляне