【官方双语】不可能的棋盘谜题

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。

【回复】标数字从零开始，老程序员了[妙啊]
【回复】Stand-up Maths频道上的解答：https://youtu.be/as7Gkm7Y7h4 特别感谢以下赞助者：https://3b1b.co/chess-thanks 官网地址：https://www.3blue1brown.com 动画是用manim制作的，一个挺简陋的开源python库： https://github.com/3b1b/manim 如果你想试着用这个库，我得先给你打好预防针：它的说明文档不怎么全，而且这个工具原本是打算我自己用的，所以你会碰到不少奇怪的写法和bug 音乐由Vincent Rubinetti制作 在Bandcamp上下载音乐： http://t.cn/EGECRPw ----- 3blue1brown是一个制作数学动画的视频频道，致力于将数学活灵活现地展示出来。想要第一时间看到最新视频的话请点击关注。 官网：https://www.3blue1brown.com 推特: https://twitter.com/3Blue1Brown Reddit: https://www.reddit.com/r/3blue1brown Instagram: http://t.cn/Eq3ymmq Patreon: https://patreon.com/3blue1brown Facebook: https://www.facebook.com/3blue1brown
【回复】太厉害了！看视频的时候还云里雾里的，看了评论以后瞬间明白了！简单来说就是通过互相之间的异或运算以及异或运算的性质来算出结果，上个学期学的离散数学和数字逻辑果然没白学[打call]
一洗三拭:
↓想看海明码和纠错方案[妙啊]（催更[doge]）

【回复】BV1ix41137Eu 的P36开始，请[OK]
【回复】回复 @不变的七月火 :视频不见了……能说下是啥视频吗？
MetaMiku:
1blue1red1brown[热词系列_知识增加]（确信）

【回复】暗示3blue1brown是四维生物（
【回复】回复 @-Carl-Czerny- :老三体了
【回复】回复 @墨漓甘棠 :因为有四个颜色，所以四维
萌龙少主:
视频给了染色方案，但没给对应的策略是什么。我对着4维（也就是4个格子的情况）的着色图琢磨了一下，下面是一种可用的策略： 只看前三个硬币的状态→如果有某一枚状态与另外两枚不同，则钥匙在这个格子下；如果三枚状态都相同，那么在第四个格子下。 || 举个简单的例子，初始状态0010。①钥匙在第一格，反转第二个硬币得到0110；②钥匙在第二格，反转第一个硬币得到1010；③钥匙在第三格，反转第四个硬币得到0011；④钥匙在第四格，反转第三个硬币得到0000。

【回复】[热词系列_妙啊]这个应该是四维的最优解法了，因为mod3刚好形成一个操作可解的闭环不会被典狱长反制策略，而且多出了四号位这个可以参与补位操作的编码防止出现前三位不能动的尴尬处境
【回复】如果延拓你这种方法，加入更高级的逻辑关系…
【回复】白把四维的图画出来了哈哈哈哈哈c
花依镜:
或许数学就像一个牢笼，外面的人不想进，里面的人出不去[妙啊]

爱学习的天冬:
其实就是给定任意64bit， 让你改变1bit，从而得到一个1-64之间的数字，重点是确定之间的映射关系。 由于你不可能让别人知道你改变的是哪个，所以只能将改变后的64bit映射到1-64之间的一个数字。 所以问题变成了你需要从给定的64bit中抽象出一个数字，然后用这个数字和你改变的bit所代表的数字进行一些操作得到另外一个数字。 由于这些数字都是1-64的，经过运算后得到的也是1-64的，而如今常见的运算中有异或有这一性质，所以可以利用异或求解。

【回复】回复 @哔哩嘻哩 :楼主用matlab编程的[微笑]
二楠早睡觉:
后面提到的Stand-up Maths的具体解法：BV1yt4y1D7PV。刚搬的，生肉警告。

【回复】双语字幕版视频已发 https://b23.tv/boB9HJ 翻译错漏请在弹幕指正[笑哭]我自己翻译的菜勿喷[doge]
一个磁通量:
所以那个解法的视频有人搬运吗(￣(エ)￣)

【回复】https://b23.tv/pk6R4O 个人翻译，有错漏请弹幕指正。
【回复】转录完了 那有人可以翻译一下吗
【回复】有人搬了。可以翻翻评论去
Cubeneo:
Do math × Do meth √ [doge] 另外，[热词系列_爷关更]

【回复】啊！我竟然在首页苟住了！[热词系列_泪目]
no996plz:
我去我上个学期信息论课题刚刚写的这个，我最喜欢的科普类up就发了这个问题[热词系列_知识增加]，太巧了吧[星星眼]发出来不知道你们能不能点开[doge] https://share.weiyun.com/rz2bTouu

【回复】老哥连名带学校一起发出来真的好吗
zeta函数:
刚刚学完抽象代数的来说明一下为什么8*8的棋盘可行但是对于6*6或者63格的棋盘就不可行。因为解法中需要规定“加法”和“乘法”，也就是需要构造域。而有限元的域的元素个数只能是p^n（p为质数），这样的域被称为伽罗瓦域。请注意回形针的一期节目里说伽罗瓦域中的加法和减法等价，这是错误的，这是只有在2^n的情况下才成立的特殊性质。

滑稽的柯基:
评论能不能别刷理科生/文科生了[无语]文科生不需要学数学吗？文科生不需要逻辑推理思维吗？

【回复】就是，还有一堆刷学历的，看着就烦。(虽然弹幕我基本不开)
宋荣子的微笑:
谁还记得概率论系列，开了个头没填完坑[tv_doge]

Thomas_y0ung:
关于三个格子的解法，请问可不可以用100 011代表钥匙在第一个格子，101 010代表在第二个格子，001 110代表在第三个格子来解啊，直接弃用111 和000，因为无论初始情况如何都可以摆出一个格子和另外两个不同的摆法，有错误请指正[捂脸]

【回复】是由监狱长决定摆怎样的棋钥匙放哪，100钥匙放第一个格子就猜不出来了哦
【回复】如果初始状态100，放在第一个格子，你必须翻转一个，不可以不翻转
【回复】回复 @老司机骨灰盒 :立方体证明中以“不存在所有顶点都满足其它3个相邻顶点分别是3种不同的颜色”就明确了不允许不进行移动（即不翻转）了。 否则的话，需要证明的就变成了”不存在所有顶点都满足【其自身与】其它3个相邻顶点至少含有3种不同的颜色。”了。如果是这样证明哪些不可能也会复杂很多。