中转中的危险

加入我们的科学爱好者社区!

鲍勃和爱丽丝在信封中互相发送原钻货物。每批货物都经过五个可能的中间人中的正好三个之手,这些中间人以其数字代号 M1、M2、M3、M4 和 M5 闻名。为了保密,每个参与者(鲍勃、爱丽丝和每个中间人)都有一个类似邮箱的保险箱。为了将货物转移给 X,需要将信封放入 X 的保险箱的投递口中。X 会在确信无人监视时进来,并将信封从保险箱中取出。只有保险箱的所有者才能取出信封。

每当信封货物到达鲍勃或爱丽丝处时,两人都会商议。接收者会告诉发送者所有钻石是否都已到达。您可以相信鲍勃和爱丽丝会说实话。两人也完全信任彼此。

热身题
假设最多只有一个中间人是小偷,并且小偷总是会偷窃。鲍勃和爱丽丝如何在最多三次发货后确定谁是小偷(如果存在小偷)?


关于支持科学新闻

如果您喜欢这篇文章,请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅,您正在帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事的未来。


热身题解答

尝试在第一次发货中使用 M1 M2 M3 作为中间人

如果东西被盗,则在
第二次发货中尝试 M3 M4 M5
如果东西被盗
那么小偷一定是 M3
否则(M3 M4 M5 不是小偷)在
第三次发货中尝试 M1 M4 M5
如果东西被盗
那么小偷是 M1
否则小偷是 M2
结束 if
结束 if
否则(第一次发货中没有东西被盗)
在第二次发货中尝试 M1 M2 M4
如果东西被盗
那么 M4 是小偷
否则在第三次发货中尝试 M1 M2 M5
如果任何东西被盗
那么 M5 是小偷
否则没有小偷
结束 if
结束 if

热身题结束

正如您所见,推理可能会变得复杂。这是一个更难的问题。

1. 和以前一样,仍然有五个中间人,鲍勃和爱丽丝每次发货选择三个。但是,现在可能有多达两个小偷。和以前一样,小偷每次有机会都会偷窃。鲍勃和爱丽丝最少需要多少次发货才能确定谁是小偷,以及是否有零个、一个或两个小偷?

这是一个我尚未解决的问题

2. 假设信封在发货源处被密封。偷窃货物需要破坏封条,但即使部分或全部内容物已被移除,信件也总是会到达目的地。进一步假设,在信封的封面上,每个中间人都用铅笔标明信封是否完好无损地到达。中间人可以撒谎,后来的中间人可以擦除和更改其他中间人写的内容。只有小偷才会撒谎或更改其他人的答案。那么需要多少次发货?

© . All rights reserved.