The impossible chessboard puzzle_AVS-【官方双语】不可能的棋盘谜题
热门回复:
- 3Blue1Brown:64格棋盘问题的解法,精简版:
首先定义非负整数a、b的异或运算a⊕b为不带任何进位的二进制加法。
例如:6⊕13,也即二进制里的110⊕1101,二进制个位是0+1=1,二位是1+0=1,四位是1+1=(1)0,不进位
只保留一个0,八位是0+1=1,所以结果是二进制的1011,也即6⊕13=11。
异或的性质有:
1. 交换律:a⊕b=b⊕a
2. 结合律:a⊕(b⊕c)=(a⊕b)⊕c
3. 单位元:a⊕0=0⊕a=a
4. 加即为减:a⊕a=0
5. 对2的幂封闭:假设存在非负整数n使得a,b<2^n,那么有a⊕b<2^n。
证明及其他具体细节请参考百度等。
给64个棋盘格标号为0、1、……、63。假设在某一时刻棋盘上任意摆满了硬币,那么从这个硬币的排列里挑出所有
正面朝上的硬币,把所有这些硬币的序号取异或运算,然后可以把棋盘上的这一种硬币排列对应到序号为这个运
算结果的棋盘格上,如果没有硬币朝上则取0号棋盘格。当1号囚犯进入时,会见到对应某a号方格的硬币排列,
和藏在某x号方格下的钥匙。此时,1号囚犯翻转a⊕x号方格上的硬币。
例如:1号囚犯见到3、14、15号硬币正面朝上,此时对应a=3⊕14⊕15=2。如果钥匙藏在x=9号格下,那么1号
囚犯选择翻转a⊕x=2⊕9=11号硬币。2号囚犯进入,见到3、11、14、15号硬币正面朝上,会计算x=3⊕11⊕14⊕
15=9。
接下来分析这个策略为什么会成功:由以上性质5,1号囚犯永远有硬币可以翻。
1. 如果这个硬币a⊕x本来正面朝下,那么翻转之后的硬币排列对应的结果是a⊕(a⊕x),这其中a是本来所有
硬币的运算结果,而(a⊕x)是新多出来的一项。由于上述性质2到4,a⊕(a⊕x)=x,那么2号囚犯顺利得到钥匙
x。
2. 如果这个硬币a⊕x本来正面朝上,那么翻转之后本来的运算结果仍然是a,但是少了(a⊕x)这一项。由于性
质4,从a中“减去”(a⊕x)等同于向a中“加上”(a⊕x),因此得到的结果仍然是a⊕(a⊕x)=x,2号囚犯顺利得
到钥匙x。
- 默默当学霸:半年更一期,一期看半年[tv_doge]
- 一洗三拭:↓想看海明码和纠错方案[妙啊](催更[doge])
- Rich_Tang:哇這是總算找回B站帳號密碼了嗎[doge]
- Minecraft009:1blue1red1brown[热词系列_知识增加](确信)