A室中有100名(或者什至2N :-)号囚犯。他们的编号从1到100。

将他们一一(从＃1囚犯到＃100囚犯)依次放到B室，其中有100箱(从1到100的数字)等待着他们。 (封闭的)框内的数字是1到100(框内的数字是随机排列的！)。

进入B室后，每个囚犯都可以打开50个盒子(他选择打开哪个盒子)。如果他在这50个箱子中找到一个分配给他的号码，则囚犯进入C房间，然后所有箱子都关闭，然后下一个箱子从A房间进入B房间。否则，所有囚犯(在A，B和C房间)被杀。

在进入B室之前，囚犯可以商定一种策略(算法)。房间之间无法进行通信(房间B中不能留下任何消息！)。

是否有一种算法可以最大化所有囚犯生存的可能性？该算法达到什么概率？

笔记：

• 随机做事(我们称之为"无策略")的确为每个囚犯提供了1/2的概率，但是所有这些人幸存下来的概率为1/2 ^ 100(这是非常低的)。一个人可以做得更好！
• 囚犯不允许重新订购箱子！
• 第一次找不到囚犯号码时，所有囚犯都会被杀。而且无法进行通讯。
• 提示：一个人平均可以拯救30多名囚犯，远远超过(50/100)(50/99)[...] * 1

解决方案

回答

实现排序算法，并根据其中的数字对框进行排序。

第一个囚犯将50个盒子分类，第二个囚犯将另外50个盒子分类并与第一个盒子合并。 (请注意，第二个囚犯可以猜测前50个框内的值)

在第二名囚犯之后，所有箱子都将按照有序排列！！！

然后其他所有人都可以轻松打开包含其编号的框。

回答

我发现针对此类问题的技术含量较低的解决方案始终是最好的解决方法。

首先，我们对情况做出一些假设

• 囚犯并非都是程序员或者数学家
• 他们不想死
• 卫队装备精良

因此，他们明天将有0.005％的机会看到该问题，因此有一个非常简单且技术含量低的解决方案。暴动

所有关于损失v潜在收益的可能性，就是囚犯远远超过警卫人数，并互相利用作为人类的盾牌，因为他们都是死人，如果他们不这样做的话，他们可以增加他们战胜权力的机会。守卫，一旦他们拥有他的武器，机会就会增加，从而帮助他们控制更多的守卫以获得更多的火力，从而进一步提高那里的生存率。一旦警卫们意识到发生了什么事，他们很可能会冲向山丘并封锁监狱，这将使媒体抬起头来，然后是人权问题。

回答

也许我没有正确阅读，但问题似乎是构造错误或者缺少信息。

If he finds the number that was
  assigned to him in one of these 50
  boxes, the prisoner gets to walk into
  a room C and all boxes are closed
  again before the next one walks into
  room B from room A. Otherwise, all
  prisoners (in rooms A, B and C) gets
  killed.

那里的最后一句话是否意味着所有囚犯在第一次找不到囚犯号码时就被杀死？如果没有，找不到号码的囚徒怎么办？

如果无法进行交流，并且每当囚犯进入房间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

回答

我不知道是否允许这样做，但我能找到的最佳近似值是：

编辑：好的，我认为这做到了。当然，我将其视为一个计算问题，我认为任何prisioner都将无法执行此操作，尽管如果没有的话，这很简单。

找到前50个素数，假设我们将它们保存在称为素数的数组中。

• 第一个盗贼进入房间B，打开第一个盒子，找到数字m。
• 等待素数[1] ^ m(将为3 ^ m)
• 打开方框2并读取数字-> n
• 等待(primes [2] ^ n-1)* primes [1] ^ m，即(5 ^ n-1)* 3 ^ m，而他一直在等待的总时间为3 ^ n * 5 ^ n

重复。在第一个罪犯之后，他的总时间将是：
3 ^ m * 5 ^ n * 7 ^ p ... = X

在第二个罪犯进入房间之前，请进行因式分解X。我们已预先知道已使用的素数，因此因式分解是微不足道的。这样做可以获得m，n，p等，因此第二个prisioner知道前一个prisioner使用的每个框/数字组合。

第一个被杀死的概率是1/2，第二个将被杀死的概率为50 /(100 n)(是第一个的尝试次数的n)，第三个将被杀死的概率为50 /(100 nm)(如果n + m = 100，则所有位置都是已知的)，依此类推。

显然，下一个犯人必须跳过已知的框(如果包含其编号的框是已知的，则最后一个选择除外)

我不知道确切的可能性是什么，因为它取决于他们必须做多少选择，但我会说这相当高。

编辑：重新阅读，如果犯罪者在获得自己的号码时不必停止，那么整个团队的可能性将大大提高，准确地是50％。

EDIT2：@OysterD这样看。如果第一个罪犯可以打开50个盒子，那么第二个就可以知道它的编号是否在那个盒子中。如果是这样，那么他可以打开其他49个盒子(并通过这样做来学习100个盒子的盒子/数字同位)，最后打开他的盒子。因此，如果第一个犯罪者成功了，那么每个人都会成功。请记住，每个prisioner提供了一种让对方准确知道他打开的每个盒子的盒子/数字组合的方法。

回答

我认为，由于无法沟通，因此最好的策略是

distributing the probability of each prisoners as evenly as possible

我在正确的道路上吗？

每个囚犯可用的信息：

The number of survivied prisoners, so if you have an efficient box picking system that  utilizes the order any prisoner enters room B, then a strategy is definitely possible
  Which boxes the earlier prisoners picked. Of course, no communication is possible during the run and it wouldn't be possible to remember any 100s box picking permutation. But you could use this information to compute in a system before the run starts.

我的看法：

Draw a table of numbers with 2 columns, the first column contains the box number (from box #1 to box#100). Each prisoner then gets to pick 50 boxes and whatever box they pick, they should put 1 mark on the corresponding row in the second column.  
  All prisoners are however required to never pick any box twice. And no box may be marked more than 50. Some prisoners may get less options than others since some box may get filled to 50 marks first.
  When a prisoner is moved to room B he/she opens whatever boxes he has marked on.

回答

相同的概念。

其他：

Write down a list of the first 100 binary numbers which has fifty 1s and fifty 0s.
  Sort them from lowest to highest.
  Prisoner #1 gets the first number, prisoner #2 gets the second, prisoner #3 gets the third and so on...
  Each prisoner remembers his/her binary number.
  When any prisoner is moved to room B, he/she then match the binary digits of the number he remembered with each of the box, the highest bit is matched with the leftmost box, the next highest bit is matched with the second leftmost box ... the lowest bit is matched with the rightmost box.
  He/she opens whatever boxes matched with 1 and leave closed boxes matched with 0.

这将使可能性最小化，因为早期的囚犯将获得与后来的囚犯不同的数字，而数字紧密接近的囚犯将使数字紧密接近。这不能保证生存能力，但是如果早期的囚犯确实能够生存，那么后期的囚犯也有更高的生存概率。

我还没有考虑确切的数字和原理，但这是我目前可以想到的一种快速解决方案。

回答

如果在某人找不到他们的号码时所有囚犯都被杀死，那么我们或者保存100，或者保存0。无法保存30人。

回答

在http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml上可以解释此难题，并且该人可以更好地解释该问题。

"所有囚犯都被杀"的说法是错误的。
"我们平均可以保存30多名囚犯"也是错误的，该文章说，我们有30％的时间可以保存100％的囚犯。

回答

这个问题没有任何时间限制，所以我建议囚犯应该决定每个盒子花1个小时，然后按提出的顺序打开它们。如果第二名囚犯在2小时后被允许进入房间，那么他知道第一名囚犯在方框2中找到了自己的号码。因此，他知道将按顺序跳过方框2，并打开方框1、3、4 ... 51.
第一犯的赔率是50/100
假设第一个囚犯得以幸存，然后第二个囚犯获胜的机会是50/99
因此答案似乎是((50 ^ 51)* 49！)/ 100！
根据谷歌这使2.89 * 10 ^ -9
这几乎是零
因此，即使囚犯们知道那些箱子，以前幸运的人在里面找到了他们的号码，也没有希望。