На мен ми се струва, че намирането на оптимално решение на задачата и доказването на оптималността (т.е., че математическото очакване на даден алгоритъм за времето до освобождаването с пълна сигурност е не по-голямо от това на всеки друг алгоритъм) си е направо безнадеждна работа.

Аз се опитах да поумувам какво ще стане, ако затворниците са не 100, а по-малко: 2, 3, 4, 5 и т.н.

За двама решението е тривиално, защото лампата става излишна. Средното време за освобождаване е 3 дни.

За трима съществува оптимален алгоритъм от средно 5.5 дни. Той е оптимален, защото гарантира, че последният влязъл за пръв път при лампата затворник веднага да разбере това.

За четирима обаче не съществува такъв алгоритъм, при който математическото очакване за времето на процедурата да съвпада с математическото очакване за времето на извъртане на всички затворници през стаята (което е 8 1/3 дни). Струва ми се, че това би могло да се докаже, но не съм го доказвал. Имам алгоритъм за 12 1/3 дни средно, но даже не зная, дали е оптимален.

За петима става много сложно.