一个看起来不可能赢的游戏


游戏一共涉及三个人,你和一个小伙伴组成一队答题,另一人来出题。题目的内容是这样的:

  • 有一块方形木板,上面共有 64 个格子(8x8),旁边有 64 枚硬币
  • 出题人会将所有硬币都放到格子上,但硬币是正面朝上还是反面朝上,完全看出题人的心情
  • 全部摆放完后(每个格子上都有一枚硬币),出题人会将其中一枚硬币指定为魔币,当然会指哪个也全看出题人的心情
  • 整个过程你作为旁观者只能看着。在叫队友进来答题(找出该魔币)之前,可以将这 64 个硬币中的任意一个进行翻转
  • 队友进来之后,不能与他进行任何通信,他的目标是找到出题人指定的那个魔币(事先可以和队友商量策略)

真的可能吗?

信息量太少了,将一枚硬币翻转,只有 1 比特的信息,而且队友进来之后完全不知道哪个被翻转了(就算看到 63 个正面,一个反面,也不知道是不是这个反面被翻转过),更别说要找到出题人指定的魔币。

这个魔币可以出现在 64 个格子的任意位置,用二进制来表示的话,需要 6 位($2^6$ = 64),同时硬币的翻转可以带来奇偶的改变,结合这两点能不能找到点思路呢?

发散一下,10 个老鼠从 1000 瓶水中找毒水是不是跟这个场景有点像?难道把 64 个数字用二进制表示会有什么不同?

000000 = 0
000001 = 1
000010 = 2
000011 = 3
...
111111 = 63

那个魔币一定是这组数中的一个,假设吃了它会死,只要找到 6 只老鼠,emmm···

那有没有可能棋盘本身就能组成 6 只老鼠呢?假如可以,就让每只老鼠分别代表一个二进制位

老鼠 A -> $2^0$
老鼠 B -> $2^1$
老鼠 C -> $2^2$
老鼠 D -> $2^3$
老鼠 E -> $2^4$
老鼠 F -> $2^5$

然后通过硬币正面朝上数量的奇偶性来表示该位是 1 或 0,这样队友进来时,先按照某种约定的方式找到「老鼠 A」,然后判断它的奇偶性,这样就能知道第一位(最右边)是 0 还是 1,同理找到「老鼠 B」,判断奇偶,确定第二位。最后会形成一个完整的二进制数,比如 001100,也就是 12,那么魔币所在的位置就是 12。

因为翻转硬币就能改变奇偶性,如果能通过翻转硬币达到随意控制某一/几位变成 0 或 1,就能把二进制调整为魔币对应的数字,按照该策略,计算出二进制数后,就能知道魔币所在位置。

接下来的问题是,如何让棋盘本身形成 6 个比特位?

继续思索

假如你跟队友约定,左边四列代表第 1 位,右边四列代表第 2 位,上边四行代表第 3 位,下边四行代表第 4 位,中间四列代表第 5 位,中间四行代表第 6 位,也就是每 1 位都有特定的区域,然后数该区域里硬币为正面的个数,如果为奇数则表示该位为 1,偶数则为 0。而你可以通过翻转硬币来将这个二进制数变为魔币所在位置的二进制数,是不是就妥了?

那应该怎么分呢,如果按照上面的分法,该如何达到翻转某个硬币来调整各个组的奇偶性呢?

划分组的策略

假设出题人摆放完硬币后,按照上面的分组查找,得出的二进制数为:001100,出题人指定魔币的位置为 42,也就是 101010,这个数的 $2^0$,$2^2$,$2^5$ 与得出的二进制不同,因此这 3 组需要翻转,其他组不动。

理想状态自然是每个组之间没有重叠,然后将各自组的其中一枚硬币翻转,但这样最多需要翻转 6 次(原始二进制数和目标二进制数各位都不相同)。所以一定会有交叉,那如何交叉才能使得所有可能的翻转组合都被覆盖到呢?如果用 1 表示翻转,那么二进制表示的 64 个数字,不就是所有可能的翻转组合么?

比如 3,也就是 000011 表示翻转 $2^0$ 和 $2^1$ 所在的组,原先为奇数个正面的硬币,就变成偶数个,反之亦然,其他 4 个组维持原状。

好像有思路了。对于 $2^0$ 这一组,包含的数为末尾为 1 的二进制数,$2^1$ 这一组,则包含倒数第二位为 1 的二进制数,以此类推(下图可点击放大):

这样 6 个组就划分完了,假设经过计算后发现要调整 $2^5$, $2^3$, $2^1$ 这 3 个组硬币的奇偶性,也就是 101010,对应十进制就是 42,那么将 42 号硬币翻一面就行了。

是不是只影响了 $2^5$, $2^3$, $2^1$ 这 3 个组,$2^0$, $2^2$, $2^4$ 这 3 组安然无恙。

实战

假设出题人最后的硬币摆放如下(白色为正面,灰色为反面,),指定魔币序号为 39。

按照上面的分组规则,看看每个组包含的硬币正反面情况

分别为:

$2^0$ 正面数量为 23,奇数,该位为 1
$2^1$ 正面数量为 20,偶数,该位为 0
$2^2$ 正面数量为 22,偶数,该位为 0
$2^3$ 正面数量为 22,偶数,该位为 0
$2^4$ 正面数量为 19,奇数,该位为 1
$2^5$ 正面数量为 22,偶数,该位为 0

这个二进制数就是:010001。目标数是 39,对应的二进制表示为:100111,需要调整的是 $2^5$, $2^4$, $2^2$, $2^1$ 这 4 个组。110110 这个数变成 10 进制就是 54,也就是将序号为 54 的硬币翻转一下。

答题人进来后,按照约定的分组规则,分别计算各个组的奇偶数:

$2^0$ 正面数量为 23,奇数(不变),该位为 1
$2^1$ 正面数量为 21,奇数,该位为 1
$2^2$ 正面数量为 23,奇数,该位为 1
$2^3$ 正面数量为 22,偶数(不变),该位为 0
$2^4$ 正面数量为 20,偶数,该位为 0
$2^5$ 正面数量为 23,奇数,该位为 1

最终得到的二进制位 100111,也就是十进制的 39,魔币的位置找到了。

发散

二进制操作中,让一部分保持不变,另一部分翻转,这个行为不就是异或(不变的部分为 0,变化的部分为 1)么,比如想让 100111 的最后一位变成 0,那么只要与 000001 执行异或操作就行了。异或还有一个性质是与同样的数再次异或可以得到原先的数,利用这个特性,也可以将异或用在一些加密场景。

参考


根据 Phuker 提供的 3B1B 视频链接,再进行一些延展。视频里提到如果不是 64 个硬币,而是 3 个硬币,就没有必胜的策略了。这就很有意思了,3 个硬币中找一个不是比从 64 中找一个简单么?还真不是。

视频中把「找硬币」映射为「顶点着色」问题,翻转硬币就是从某个顶点到相邻顶点(n 个硬币表示 n 维空间),3 个硬币(对应 3 位二进制)翻转任意一个,也就是从一个正方体(每个顶点是一个 3 维坐标,具体可以参见视频)8 个顶点的任意一点到相邻点。因为不知道这三个硬币会被如何摆放,也就是 8 个顶点都有可能(3 位二进制一共有 8 种摆放形式),需要从任意一个顶点出发,应用某种规则,让相邻的 3 个点对应 3 种状态,而这是无法做到的:把 3 种状态标记为红点、绿点、蓝点,每个顶点对应一种颜色,如果要满足需求,则在每个顶点看来,相邻的点一定有红色的点(其他点也一样,红色只是其中一种),也就是 8 个点,又因为 1 个点周围有 3 个点,所以每个点都被数了 3 次,这样的话红色的点就有 8/3 个,自然无法实现。要能被整除,也就是 $2^n$/n 为正整数,则 n 本身必须是 2 的次方,如 2,4,8,16… 才可以,题目中的 64 是 2 的 8 次方,因此可以实现。

视频中还提到了「海明码」,原理上跟这道题的解法很像,也是根据二进制的位数来切分区域,不同的是每个区域有一位(第一位)是校验位,可以是奇校验(该区域的1的个数为奇数,可以通过校验位来确保)或偶校验。如果其中某一位出错(比如 0 -> 1),那么不仅可以知道有错(只要是一位出错,奇偶性一定发生改变),还能知道第几位错了(就像这道题中找到那个魔币)。具体原理可以看 3B1B 的这个视频