Найти свой номер в коробке

Question

100 (или некоторые четные числа 2N :-)) заключенные находятся в комнате А. Они пронумерованы от 1 до 100.

Один за другим (по порядку от заключенного № 1 до заключенного № 100) их пускают в комнату В, в которой их ожидают 100 ящиков (пронумерованных от 1 до 100). Внутри (закрытых) ящиков находятся числа от 1 до 100 (числа внутри ящиков случайным образом переставлены!).

Оказавшись в комнате B, каждый заключенный открывает 50 коробок (он выбирает, какую из них он открывает). Если он находит номер, который ему был присвоен в одной из этих 50 коробок, заключенный попадает в комнату C, и все коробки снова закрываются, прежде чем следующий войдет в комнату B из комнаты A. В противном случае все заключенные (в комнаты А, В и С) погибают.

Перед входом в комнату B заключенные могут согласовать стратегию (алгоритм). Между комнатами нет возможности общаться (и в комнате B нельзя оставлять сообщения!).

Существует ли алгоритм, который максимизирует вероятность того, что все заключенные выживут? Какую вероятность достигает этот алгоритм?

Примечания:

• Случайные действия (то, что вы называете «без стратегии») действительно дают вероятность 1/2 для каждого заключенного, но тогда вероятность того, что все они выживут, равна 1/2 ^ 100 (что довольно мало ). Можно сделать намного лучше!

• Заключенным не разрешается менять порядок ящиков!

• Все заключенные погибают в первый раз, когда заключенный не может найти его номер. И связь невозможна.

• Подсказка : можно спасти более 30 заключенных * в среднем 1031 * , что намного больше (50/100) * (50/99) * [.. .] * 1

Answer 1

Эта загадка объяснена на http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml, и этот человек гораздо лучше объясняет проблему.

Заявление "все заключенные убиты" неверно. «Вы можете сэкономить 30+ в среднем» также неправильно, в статье говорится, что в 30% случаев вы можете сэкономить 100% заключенных.

Answer 2

Я считаю, что решение этой проблемы всегда является наилучшим решением.

Сначала мы сделаем некоторые предположения о ситуации

• Заключенные не все программисты или математики
• Они не хотят умирать
• Охранники хорошо вооружены

Таким образом, с вероятностью 0,005%, которую они увидят завтра, существует очень простое и низкотехнологичное решение этой проблемы. Бунт

все дело в потерях против потенциальной выгоды, есть вероятность того, что заключенные намного превосходят охранников и используют друг друга в качестве живого щита, так как все они в любом случае мертвы, если они этого не делают, они могут увеличить вероятность над силой охранника, когда у него есть оружие, шанс возрастает, помогая им усилить охрану, чтобы получить больше огневой мощи для дальнейшего увеличения выживаемости. как только охранники поймут, что происходит, они, вероятно, побегут к холмам и закроют тюрьму, это поставит СМИ в тупик, а затем станет проблемой прав человека.

Answer 3

Я не знаю, разрешено ли это, но лучшее приближение, которое я могу найти:

РЕДАКТИРОВАТЬ: Хорошо, я думаю, что это делает. Конечно, я отношусь к этому как к вычислительной проблеме, я не думаю, что кто-либо из заключенных сможет это сделать, хотя довольно просто, если вы этого не сделаете.

Найдите первые 50 простых чисел, давайте предположим, что мы храним их в массиве, называемом простыми числами.

• Первый заключенный входит в комнату B, открывает первую коробку и находит число m.
• Подождите, простые числа [1] ^ m (это будет 3 ^ m)
• Откройте поле 2 и прочитайте число -> n
• Подождите (простые числа [2] ^ n - 1) * простые числа [1] ^ m, это будет (5 ^ n - 1) * 3 ^ m, и общее время, которое он ждал, будет 3 ^ n * 5 ^ п

Повторите. После первого заключенного общее время для него будет: 3 ^ m * 5 ^ n * 7 ^ p ... = X

До того, как второй наблюдатель входит в комнату, разложить на множители X. Вы заранее знаете, какие простые числа были использованы, поэтому разложение на множители тривиально. При этом вы получите m, n, p и т. Д., Чтобы второй наблюдатель знал каждую комбинацию коробки / номера, использованную предыдущим наблюдателем.

Вероятность того, что первый убьет всех, равна 1/2, у второго будет 50 / (100 - n) (при n числах попыток первого), у третьего - 50 / ( 100 - n - m) (если n + m = 100, то все позиции известны) и т. Д.

Очевидно, следующий обвиняемый должен пропустить уже известные ящики (за исключением последнего выбора, если ящик, который содержит его номер, уже известен)

Я не знаю, какова точная возможность, поскольку это зависит от того, сколько вариантов они должны сделать, но я бы сказал, что это довольно высокий показатель.

РЕДАКТИРОВАТЬ: Повторное чтение, если заключенный не должен останавливаться, когда он получает свое число, то вероятность для всей группы значительно улучшается, ровно на 50%.

EDIT2: @OysterD посмотри на это так. Если первый наблюдатель может открыть 50 коробок, то второй знает, есть ли его номер в любом из этих коробок. Если это так, то он может открыть остальные 49 (и, изучив таким образом, комбинацию из 100 блоков), и, наконец, открыть свою. Так что, если первый заключенный преуспевает, тогда все преуспевают. Помните, что каждый заключенный дает возможность другому точно знать комбинацию ящиков / чисел для каждого открываемого им ящика.

Answer 4

Реализация алгоритма сортировки и сортировка блоков по номерам внутри них.

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

После 2-го пленника все ящики будут в отсортированном порядке !!!

Тогда все остальные могут легко открыть коробки с их номерами.

Answer 5

В этом вопросе нет временных ограничений, поэтому я предлагаю, чтобы заключенные решили взять 1 час на ящик и открыть их в указанном порядке. Если второму заключенному разрешают войти в комнату через 2 часа, он знает, что первый заключенный нашел свой номер в ячейке 2. Поэтому он знает, что пропускает рамку 2 в своей последовательности и открывает ячейки 1, 3, 4 ... 51 Вероятность потери первого заключенного составляет 50/100 Предположим, что первый заключенный выжил, а у второго - 50/99. Таким образом, ответ, кажется, ((50 ^ 51) * 49!) / 100! который по гуглу составляет 2.89 * 10 ^ -9 что в значительной степени ноль Так что, даже если бы заключенные знали коробки, в которых ранее находились счастливчики, у них не было бы надежды

Answer 6

Если все заключенные погибают, когда кто-то не может найти их номер, тогда вы либо сохраняете 100, либо 0. Спасти 30 человек невозможно.

Answer 7

Та же концепция.

Другой дубль:

1. Запишите список первых 100 двоичных чисел, который имеет пятьдесят 1 и пятьдесят 0.
2. Сортируйте их по возрастанию.
3. Заключенный № 1 получает первый номер, заключенный № 2 получает второй, заключенный № 3 получает третий и так далее ...
4. Каждый заключенный запоминает свой двоичный номер.
5. Когда любого заключенного переводят в комнату B, он / она затем сопоставляет двоичные цифры числа, которое он запомнил, с каждым из ящиков, старший бит сопоставляется с самым левым ящиком, следующий старший бит сопоставляется со вторым крайний левый блок ... младший бит совпадает с крайним правым блоком.
6. Он / она открывает все поля, соответствующие 1, и оставляет закрытые поля, соответствующие 0.

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

Хотя я не продумал точные цифры и обоснование, но это одно быстрое решение, о котором я могу подумать в данный момент.

Answer 8

Я думаю, что поскольку общение невозможно, лучшая стратегия будет включать

Распределение вероятности каждого заключенного как можно более равномерно

Я на правильном пути или нет?

Информация, доступная для каждого заключенного:

• Количество выживших заключенных, поэтому, если у вас есть эффективная система отбора ящиков, которая использует порядок, в котором любой заключенный входит в комнату B, тогда стратегия определенно возможна
• Какие ящики забрали ранние заключенные. Конечно, никакая связь невозможна во время пробега, и невозможно было бы вспомнить какую-либо перестановку выбора коробки 100 с. Но вы могли бы использовать эту информацию для вычисления в системе до запуска.

Мой дубль:

1. Нарисуйте таблицу чисел с 2 столбцами, первый столбец содержит номер поля (от блока № 1 до блока № 100). Затем каждый заключенный должен выбрать 50 ящиков, и независимо от того, какую коробку он выберет, он должен поставить 1 отметку в соответствующем ряду во втором столбце.
2. Однако все заключенные никогда не должны выбирать ни одну коробку дважды. И ни одна коробка не может быть помечена более 50. У некоторых заключенных может быть меньше вариантов, чем у других, так как одна коробка может быть заполнена вначале до 50 марок.
3. Когда заключенного переводят в комнату B, он / она открывает все коробки, на которых он отмечен.

Answer 9

Заключенные могут согласиться с тем, что заключенный 1 открывает коробки 1-50.

Если они все еще живы, они соглашаются, что следующий заключенный открывает коробки 2-51. (2 - произвольно, но просто запомнить это правило). Его шансы на выживание , учитывая, что P1 выжил , теперь равны 50/99. Вы хотите исключить открытие коробки, когда узнаете, что предыдущий парень нашел его.

Я не знаю, оптимально ли это, но это намного лучше, чем случайное.

Вероятность выживания, которая выглядит как

50/100 * 50/99 * 50/98 *. , .50 / 51 * 1

Answer 10

Может быть, я не правильно это понимаю, но вопрос, похоже, неправильно составлен или отсутствует информация.

Если он найдет номер, который был назначен ему в одном из этих 50 ящики, в которые попадает заключенный комната С и все коробки закрыты снова, прежде чем следующий входит в комната B из комнаты A. В противном случае все заключенные (в комнатах A, B и C) получают убит.

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

Если коммуникация невозможна, и всякий раз, когда заключенный входит в комнату B, он всегда находится в идентичном состоянии, тогда нет никакой возможности для стратегии.

Заключенные могли бы сказать, прежде чем покинуть комнату А, какую коробку с цифрами они собираются открыть. Но без того, чтобы последующие заключенные не знали, были ли они успешными или нет (при условии, что неудача для одного не является неудачей для всех), когда следующий заключенный входит в комнату B, у них все еще есть те же шансы выбора их числа, что и у предыдущего заключенного (всегда 1: 100) .

Если неудача для одного является неудачей для всех, то, зная, какую коробку открыли предыдущие заключенные, и в силу того факта, что они не все были убиты, каждый последующий заключенный может уменьшить вероятность выбора неправильной коробки: одна коробка то есть 1: 100 для первого заключенного, 1:99 для второго, до 1: 1 для последнего.