自从秦始皇以来,暴君们就一直陷入两难境地:他们知道自己需要人身保护,但也知道自己的保镖可能会背叛他们。
暴君T有一队7人的保镖。他知道,如果房间里叛徒的数量和忠诚卫士的数量一样多或更多,他就会遭到攻击。
有一天,他鼓起勇气,将所有7人带到一个房间。他没有受到攻击,所以他知道他的大部分保镖是忠诚的。问题是即使是保镖也必须休息,所以每个保镖值班16小时,休息8小时。
关于支持科学新闻业
如果您喜欢这篇文章,请考虑通过以下方式支持我们屡获殊荣的新闻业 订阅。 通过购买订阅,您正在帮助确保关于塑造我们当今世界的发现和想法的具有影响力的故事的未来。
因此,T必须将他的警卫分成小组,以便每个小组都有多数忠诚者,并且每个小组由两个或更多忠诚者组成。我们称这样的组为“可靠”小组。他请他的宫廷数学家M帮助他。
M进入,鞠躬并说:“陛下,为什么不问问保镖自己呢?他们可能知道。”
“是的,但我不知道该信任哪些指控,”T回答道。
“皇帝的判断非常英明,”数学家M说,“但我们仍然可以学到一些东西。我们可以假设,一个忠诚的警卫会说实话。一个不忠诚的警卫可能会也可能不会。陛下,必要的结论是,每一项指控都意味着指控者或被指控者中至少有一人是不忠诚的。在不忠诚的警卫提出指控的情况下,可能两者都是。”
热身题
假设皇帝只有五名保镖,其指控情况如下
其中从警卫X到Y的箭头表示X指控Y不忠诚。假设大多数警卫是忠诚的,哪些人一定是忠诚的?
热身题解答
C和E必须是忠诚的,A和D中也必须有一个是忠诚的。为什么?在A、B、C、D中,至少必须有两个叛徒。这是因为,例如,从D到A的指控表明A和D中至少有一个是不忠诚的;同样,B和C中也必须有一个是不忠诚的。因此,E肯定必须是忠诚的。
在A、B、C和D中,最多也只能有两个人是不忠诚的,因为如果该组中有更多的叛徒,那就意味着只有两名忠诚的警卫。现在,如果C是不忠诚的,那么在A、B、C和D中将有三个不忠诚的人,因为A、B和D中必须有两人是不忠诚的(指控A指向B,B指向D,D指向A)。C是忠诚的,B是不忠诚的(因为B对C撒谎)。因此,在A和D中恰好有一个忠诚的人,但这项分析并没有告诉我们那可能是谁。
现在是问题: 1. 继续使用此指控情况
您能制定一个时间表来保证暴君T始终由一个“可靠”小组守卫吗?
2. 现在考虑一个新的指控情况
暴君T能否确保始终由至少有两名忠诚成员且忠诚成员占多数的保镖小组守卫?请记住,警卫工作16小时,休息8小时。
现在,这是一个开放性问题:如果七名警卫中至少有四名是忠诚的,那么他们之间最多可能有多少条指控边?将A指控B的边与B指控A的边区分开来计算。