100 узников

[VAL]

Продолжение темы.

...Но особо, ярче теоретических изюмин, запомнились две задачки.

Одна шокировала меня давно (более 30 лет тому назад). Ее здесь уже упоминали, про произведение возрастов, равное 36.

Другая же - относительно недавно. Здесь потрясение было двойным. Собственно задачкой. И тем, что я еще не утратил способности быть чем-то потрясенным
Результатом потрясения стала наша (совместная с И.Акуличем) статья в "Кванте".

Вот эта задачка:

Цитата:

В комнате стоят 100 одинаковых коробок, выстроенных в ряд. В каждой из
них находится (уникальное) имя одного из 100 узников - причём имя каждого
из них находится в одной из этих коробок. Узников по очереди запускают в
комнату. Каждый из них имеет право открыть одну за другой 50 коробок из ста.
Если хотя бы один из них не найдёт своего имени, все они будут казнены;
если же каждому удастся найти своё имя - всех выпустят на свободу.
Узники не имеют права - и возможности - общаться друг с другом после
выхода из комнаты; никаких пометок в комнате делать нельзя;
перекладывать имена в коробках нельзя (впрочем, надзиратели этого
делать тоже не будут). Короче говоря, каждый узник находит комнату в
точно том же состоянии, что и предыдущий. Единственная возможность
пообщаться - ДО испытания.

Как им следует действовать, чтобы вероятность выжить для них оказалась
выше 30%?

Не привожу решения, дабы не лишать огромного удовольствия от решения тех, кто с ней не знаком (и способен решить ).

[Руст]

Только что изменится, если переставляются неразличимые коробки (внутренние номера при этом не переставляются).

[VAL]

Руст в сообщении #429671 писал(а):

Только что изменится, если переставляются неразличимые коробки (внутренние номера при этом не переставляются).

Не знаю. Полагаю, что-то изменится.
Но это не важно. Поскольку по условию коробки не переставляются.

[Null]

Хм если узников 127 и каждый открывает по 64 то почти $\frac{1}{e}$ вероятность. Теперь это надо в нужное подогнать.

[VAL]

Null в сообщении #429728 писал(а):

Хм если узников 127 и каждый открывает по 64 то почти $\frac{1}{e}$ вероятность.

Почему?

[Crutoy Pazan]

вероятность сто процентов-каждый узник открывает первые пятьдесят коробок-пятьдесят из них точно отыщут свои имена

[Null]

Тогда вероятность 0 50 узников не найдут своих имен.

[venco]

Я, как бы, решение знаю. Можно поучаствовать подсказками, или даже - намёками?

[sup]

Хм, действительно симпатичная задача. И на удивление простая формула для вероятности.

(Приближенное выражение для вероятности)

$p \approx 1-\ln 2$

[VAL]

venco в сообщении #429783 писал(а):

Я, как бы, решение знаю. Можно поучаствовать подсказками, или даже - намёками?

Сегодня можно.
Но исключительно дезориентирующими

[Руст]

Конечно вместо упорядочивания можно использовать и другие действия типа поворотов ящиков на месте на соответствующий угол. Правда для квадратных ящиков углы поворотов по 0.9 градусов почти не отличимы. Однако, 30 процентный результат можно получить даже с гораздо меньшей информацией. Например, если в открытом ящике номер выше 50 (узники пронумеруем от 1 до 100) поворачиваем ящик на бок направо, иначе налево. Уже такая не полная информация обеспечивает вероятность порядка $\prod_k (1-\frac{1}{2^k})>0.3$.

[Null]

А как же то что пометки оставлять нельзя?

Я неправильно решил.

[TOTAL]

Цитата:

Узники не имеют права - и возможности - общаться друг с другом после выхода из комнаты; никаких пометок в комнате делать нельзя; перекладывать имена в коробках нельзя (впрочем, надзиратели этого делать тоже не будут). Короче говоря, каждый узник находит комнату в точно том же состоянии, что и предыдущий. Единственная возможность пообщаться - ДО испытания.

С интервалом 10 минут (с равным интервалом) узников вносят в комнату с ящиками, затем выносят в другое (изолированное от ещё стоящих в очереди на просмотр своих 50 ящиков) помещение. Так?

[VAL]

TOTAL в сообщении #429814 писал(а):

Цитата:

Узники не имеют права - и возможности - общаться друг с другом после выхода из комнаты; никаких пометок в комнате делать нельзя; перекладывать имена в коробках нельзя (впрочем, надзиратели этого делать тоже не будут). Короче говоря, каждый узник находит комнату в точно том же состоянии, что и предыдущий. Единственная возможность пообщаться - ДО испытания.

С интервалом 10 минут (с равным интервалом) узников вносят в комнату с ящиками, затем выносят в другое (изолированное от ещё стоящих в очереди на просмотр своих 50 ящиков) помещение. Так?

Ну пусть так. Хотя равные интервалы не не гарантированы. Гарантировано отсутствие возможности передачи информации.

[arseniiv]

VAL, а вы не разрешите venco одну недезориентирующую подсказку? Никакие два узника не должны выбирать одинаковые множества коробок, или должны?