聪明人翻杯子计数
Wise Men
题目详情
苏丹抓了 50 位智者。桌上有一个杯子，初始正放。
每分钟随机召唤一位智者进入房间。被召唤者可以选择翻转杯子（正放↔倒扣）或什么也不做。
每个智者可能被召唤任意多次。
如果在某时刻有人说出“我们 50 人都至少被召唤过一次”，且该陈述为真，则全部获释；若说错，则全部处死。
他们可提前商量策略，但之后被隔离无法交流。
问：是否存在策略保证最终必获释？
A sultan captures 50 wise men. He has a cup set upright initially. Every minute, he summons one random wise man. The summoned wise man may flip the cup (from upright to upside down, or vice versa) or do nothing. Each wise man can be summoned any number of times. If, at any point, someone states “All 50 of us have been summoned at least once,” and that statement is true, they all go free. If the statement is wrong, they all die. They can devise a strategy beforehand but then are kept isolated. Can they guarantee freedom?
解析
可以。
指定 1 人作为“计数者”，其余 49 人为“普通人”。规则：
- 每个普通人第一次被召唤且看到杯子为倒扣时，把杯子翻为正放（且一生只做这一次）。
- 计数者是唯一负责把杯子从正放翻回倒扣的人；每当他这样做一次，就把计数加 1。
当计数者累计数到 49 次“普通人贡献”的翻转后，就能确定 49 个普通人都至少被召唤过一次（计数者本人也当然被召唤过），此时宣布即可。
Original Explanation
Yes. They designate one “counter” wise man. The other 49 are “ordinary.” Only an ordinary wise man who has never flipped the cup before will flip it from upside down to right-side up exactly once to indicate he has been summoned. The counter is the only one who flips it back from right-side up to upside down, each time incrementing his mental count by 1. After counting 49 flips, he knows everyone has been summoned at least once and declares it.