Поиск собственного номера в коробке

StackOverflow https://stackoverflow.com/questions/34345

  •  09-06-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

Примечания:

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

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

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

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

Это было полезно?

Решение

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

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

Другие советы

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

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

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

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

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

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

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

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

Все остальные могут легко открыть коробки, содержащие их числа.

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

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

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

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

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

Перед тем, как второй применчик входит в комнату, факторизируйте X. Вы заранее знаете основные числа, которые были использованы, поэтому факторизация тривиальна. Это вы получаете M, N, P и т. Д., Так что второй привкус знает каждую комбинацию Box/Number, используемый предыдущий привкус.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мой взгляд:

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

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

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

Аонтер возьми:

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top