Martians in a Circle


分析

答案是:这个比例是 1/2,且君子和小人一定是交替排列的。

证明思路如下:

首先,观察单个提问的结果。设 A 的右边是 B,则有:

A 类型 B 类型 A 的回答
君子 君子 君子
君子 小人 小人
小人 君子 小人
小人 小人 君子

从表中可见:若回答为“君子”,则 A 与右边同类;若回答为“小人”,则 A 与右边异类。把这看作关于相邻两人是否同类的布尔关系(有点像异或)。

然后看下询问所有人后的回答。题目说明逻辑学家能确定圈中说谎者的比例,说明回答信息足以确定说谎者人数的比值。

注意存在整体取反的对称性:把所有人的身份取反(君子↔小人)不会改变每个人对“右边是君子/小人”的回答模式,因此从回答本身无法区分一种排列和其全取反排列。这意味着回答只能确定说谎者数k与诚实者数n−k中的较小/较大关系,而不能区分kn−k,除非k = n−k

因此,要能唯一确定说谎者的比例,必须有k = n−k,即k = n/2。进一步,这对应每一对相邻两人类型都不同的情形(因为回答都是“小人”),也就是君子与小人交替排列。这又要求n为偶数。

因此,从回答到相邻关系,再由全体取反的对称性得到必须k=n/2,故说谎者比例为1/2,且君子与小人交替排列(n为偶数)。

Next