algorithm - 黑盒计数到 19 只有 2 位，并且只能切换？

Question

有些学生在另一个网站上问过这个问题，但没有得到答案。我尝试了几次，但发现它非常棘手。

只用开关来完成它需要 9:1 的压缩比，所以我猜这个技巧很大程度上取决于你分配给学生的规则。也许每个学生都需要一套不同的规则？

我考虑过在没有答案的情况下允许多次迭代，方法是只关注正确顺序的学生。我还考虑过将学生编号编码为二进制，并将其与开关中的位结合起来，以获得更多的位来使用，但这仍然是一个压缩/验证问题:即使其中一个位用于奇偶校验，您仍有很大的误报可能性。

如果没有某种方法，大概不会问这个问题。也许这是comp-sci类(class)中的常见问题并且众所周知？无论如何，事不宜迟...

“这是我在计算机课上遇到的一个问题。对我来说这似乎有点数学性质，可能涉及二进制代码。我不确定，我所有的想法都会走向死胡同。

十九名学生有机会通过玩游戏赢得奖品。经过一段时间决定策略后，所有学生将被安置在单独的隔音隔离室中，完全无法交流。

游戏的玩法如下。房间里有两个电灯开关，从“关闭”位置开始。我会一次带一个学生进入这个房间。每次学生进入房间时，他或她都必须拨动其中一个开关。所有的学生最终都会被带进房间，但有些学生可能会被带进不止一次。

如果一个人正确地告诉我每个人都在房间里，那么每个人都会中奖。但是，如果有人错误地告诉我每个人都在房间里，那么每个人都会被喂给鳄鱼!请注意，要么所有学生都获得奖品，要么所有人都输。

你的任务是确定一个策略，确保每个人都能赢得奖品(而不是被鳄鱼吃掉)。”

Answer 1

这听起来像是 Prisoners and the Light Switch riddle 的变体，其中一名囚犯被指定为“计数器”，其他所有人仅“增加计数”一次。

大概计数器会打开一个开关，如果你从未被计算过，你会关闭那个开关；另一个开关是“垃圾”。一旦计数器关闭开关 18 次，他就知道所有其他学生都去过房间。