100 个囚犯的随机选择问题
内容提要
一百名囚犯被随机分配编号，需在50步内找到自己的编号。通过链表策略，囚犯可以提高找到自己编号的成功率至30%以上。囚犯按抽屉数字指向下一个抽屉，形成环状链表，若链表长度不超过50，则必能找到自己的编号。如果能交换抽屉内的数字，成功率可达100%。
延伸解读
策略核心：为什么必须从自己的编号抽屉开始
囚犯抽到的数字对应一个抽屉序号，策略要求他首先打开这个抽屉，然后根据里面的数字指向下一个抽屉。这样做的原因是，每个抽屉内的数字唯一且与抽屉序号一一对应，形成多个有向环。如果从自己的编号抽屉开始，那么沿着环走，最终必然回到起点，即找到自己的编号。如果随机选择起始抽屉，则可能进入其他环，无法保证找到自己的编号。因此，起始点的选择是策略成功的关键。
成功概率的数学推导：为什么是30%以上
成功概率等于1减去存在长度超过50的环的概率。对于长度为n的环，其出现概率为1/n。因此，存在长度大于50的环的概率是sum_{n=51}^{100} 1/n，约等于0.688。所以成功概率约为0.312，即31.2%。这个结果远高于随机策略的0.5^100，展示了链表策略的巧妙。
交换数字：从概率游戏到必胜策略
如果允许囚犯在游戏开始前交换抽屉内的数字，他们可以主动将数字排列成多个长度不超过50的环，从而保证每个人都能在50步内找到自己的编号。例如，可以构造两个长度为50的环，这样每个囚犯最多需要50步。因此，成功率可达100%。这突显了信息与操作权限对结果的影响。
Q&A
囚犯如何在50步内找到自己的编号？
囚犯可以通过链表策略，按照抽屉内数字指向下一个抽屉的方式进行查找，形成环状链表。
随机打开抽屉的成功率有多低？
随机打开抽屉的成功率极低，约为10的-31次方。
链表策略如何提高成功率？
链表策略可以将成功率提高到30%以上，因为如果链表长度不超过50，囚犯必能找到自己的编号。
如果囚犯可以交换抽屉内的数字，成功率会怎样？
如果囚犯可以交换抽屉内的数字，成功率可达100%。
形成链表的条件是什么？
形成链表的条件是抽屉内的数字指向下一个抽屉，且链表长度不超过50。
成功找到编号的概率是如何计算的？
成功找到编号的概率是1减去链表长度大于50的概率，形成链表的可能性为1/n。
