大家怎么看：【官方双语】不可能的棋盘谜题[第一更新]

http://datagenetics.com/blog/december12014/index.html
这个是Stand-up Maths给出的一个网站，里面有完整的解决方案和你可以玩的互动板

谈：可是如果能编序号的话，直接告诉狱友藏在哪一号下面不就行了吗？？比如依靠翻出一个标志性的排列为第一排，然后告诉狱友从左往右的顺序，那么就可以说明在第几排第几列了啊

数学竞赛路过，卧槽这不是染色问题？组合数学的经典！

谈：我不配进监狱

虽然棋盘问题是为了引出高维图形着色，但棋盘问题本身是不是有更简单的办法，我想了个办法，没办法证明。首先从0-63编编号，用0和1代表硬币正反面，然后64位二进制数字可以转换成一个十进制数字，用这个十进制数字除以64，余数是0-63，现在的问题是可不可以在改动一个位数的情况下让余数正好等于你需要的数字。如果不行的话可以继续约定除以某个数，让其中的某些数位表示出0-63来

谈：两个被关在监狱的数学家[小电视_困惑]

把那枚硬币竖起来不就完事了吗[doge][doge]

谈：侧着立在格子上[妙啊]

在《算法谜题》上看到过类似的题，当时还觉得云里雾里的，现在清楚多了[拥抱]

谈：[笑哭]有点打脑壳，说实话
放在4维立方体空间，就发生了一个我不想看到的情况，每个点花了4个位来储存数据，却只能染3种颜色
等等，我觉得我有思路了
如果可以染三种颜色，那么我们可以用两种颜色来表达正确（绿、蓝），但是一旦推算出红色，就立马排除两个格子，再用剩下两个格子来推算（还原到2格的情况）
但是只能翻转一次，这就麻烦了，让我再思考一下
会不会跟我们染色法的出发点有关？如果就在自己这格，就没必要用自己的颜色来染色？
我觉得有搞头，假设我们用红黄蓝绿来做这个四维魔方，保证每次位移都可以走往每种颜色即可
也就是说只要能够保证四维立胞每个点都与其相邻的颜色不同，即可完成证明
感觉有希望
完成了，图片放在图床了
https://s1.ax1x.com/2020/08/06/a2kIPg.png
把四维胞体变成平面就好展示了
目前就到这里，只证明了四维下可以完成四个球的推算
等等，我好像对从低维度向高维度推算有一点思路了
晚一点去验证这个思路，先去吃饭了

這兩硬幣，投了[热词系列_吹爆]
將棋盤上的正反硬幣化為1與0，並事先商討好這些0與1的組合，唯一指向了一個數字，這個數字即是鑰匙所在的格數。
而你也可以根據鑰匙的位置，判斷對應的01組合，並將現有的組合嘗試更動為想要的組合。
嚴重的問題來了，萬一現有的組合，無法更動一位數，就變成想要的組合……
這大概是我對視頻內容的理解，但我不理解，是否有其他策略可以解決非2次冪的問題，看來得看看另一部視頻了，之前看了那個up關於黃金比例與複數的結合，非常有趣，非常沙雕[热词系列_知识增加]
除此之外，似乎可以任意延伸？像是變成三種硬幣、兩把鑰匙、翻動兩個硬幣……

谈：B站根本没有Stand-up Maths的任何一个视频，是不是不允许搬运？

一年一更，一更学一年

谈：64个格子需要64种颜色，如果钥匙在第5格，就用第5种颜色，这样狱友2进到房间里看见棋盘上显示第5种颜色的信息，他不需要知道之前是哪种情况，只需要“当前情况”就能知道是第5格
那么这个问题就变成，是否存在一个n种颜色的染色方案，令一个n维立方体的每个顶点都有所有n种颜色的相邻顶点，因为只有存在这种方案，才能在任意起始局面（代表一个顶点）下走到你想要表达的颜色（代表另一个你想要的颜色的顶点），狱友2进来看见这个颜色，直接往这个颜色代表的格子下找，就能找到钥匙
[芮小凸小凹_哭]大概框架是理出来了，但是实际数学语言是不可能理解了

我居然题目都没听懂 我好菜啊[生病][生病]

谈：其实那个填色问题和小学奥数的抽屉原则挺像的

高中辍学生成功看懂解出，回形针的二维码一期其实讲得挺好的。直接套用就可以得到答案了。
个人思路描述
1.64个格子可以用6位的二进制表示。
2.任意布局的正面格子可以计算出一个指定的格子A。（初始状态）
3.钥匙在格子B，格子B 和格子A 之间可以计算出一个格子X。
4.翻动X 。这样新的布局计算出来的答案就是格子B了。

《异或运算》是方法
《伽罗瓦域》是验证工具

谈：这个染色问题倒是能理解，但是真正怎么能解原题是真的想不明白，就是不知道视频里面推荐的视频能不能转一下[呆]

昨天晚上做梦解开了，0-63编号，把所有现有的正面硬币位置用二进制异或再转十进制即为要翻的位置

谈：如果把6×6的棋盘假设成8×8的棋盘并在开始前指定假设的正反那么6×6的是不是也有解呢

三蓝一棕有小闪电啦[大笑][大笑]

谈：Did you find your Bilibili account？[doge]

把硬币叠放在那个有钥匙的格子上[doge]

谈：[热词系列_爷关更][热词系列_爷关更]

口头证明一下视频中的正方体着色问题[妙啊]
假设存在每个顶角都有三种颜色的邻角，每种颜色就有8次出现在邻角中。每用一
某种颜色标记一个顶角，这种颜色就会有3次出现在邻角中。但是8不是3的整数倍，因此这种标记的正方体不存在。
如果拓展到n维情况，n维立方体有2^n个邻角，每个顶角有n个邻角，用n种颜色标记。同样假设存在每个顶角都有n种颜色的邻角。每种颜色2^n次出现在邻角，每用某种颜色标记一次，这种颜色就有n次出现在邻角，如果2^n是n的整数倍，则假设成立。显然当n为2的正整数次幂时可成立。如视频中8*8棋盘。[妙啊]

谈：快百万粉却依然没有小闪电[doge]

唔，“我完全理解了”[2233娘_大笑]

谈：爷关更[大哭][大哭][大哭][热词系列_爷关更][热词系列_爷关更][热词系列_有生之年][热词系列_有生之年][热词系列_有生之年][热词系列_镇站之宝][热词系列_镇站之宝][热词系列_镇站之宝][热词系列_镇站之宝]

文科生表示来看视频就是来练听力的[妙啊]

谈：有个疑问，如果商量讨论64格解法，被监狱长听到了，给你扣掉一格怎么办[doge]

全部红或者黄，你发哪里我翻哪里[doge]

谈：看不懂解释的话我可以用简明扼要说一下。
首先思路，1号拿到的棋盘，可以当作是随机的(人家无论如何都会干扰你)。所以目标就是无论这个棋盘是什么样的，你都要能在变一个棋子的情况下，让后者通过某种方法知道你想表达的东西。
因为是正反两面的棋子，所以能表示出来的东西自然是2^n，这就视频里前面说的，涂色也和这个有关。所以3格是不可能的，当然你要是允许棋子立起来变成有三种情况，变成3^n就可以了。
他的方法是用的代数的方法，构造一个交换群(学过抽象代数估计知道)。他这个方法重点就在于可以通过计算，可以让后者知道他的意思。特点就是自己加自己为0(逆元是自己),所以计算之后原本正面的棋子表示的值全部抵消，只剩下表示钥匙的内容。a+x(a是所有正面之和,x是目标点位),翻开a+x点，后者看到a+(a+x)（a是先前就有的，a+x是前者后翻开的）得出x。

和狱友商讨策略，可看做事先定义一个从集合A（内含2^n个元素）至集合B（内含n个元素）的映射，该映射是满射（否则会有暗格无法表示）
简单说，就是把2^n个数分成n组，每组对应一个暗格。狱友将棋盘布局二进制化，看哪一组包含该数，便知对应哪个暗格。为方便讨论，将狱友所见布局称为“救命数”
当然，救命数并非初始就有，而是进行一次强制翻转操作后产生的，以下将典狱长设置的原布局称作“咸鱼数”
你要做的，就是正确地翻转咸鱼数，让它变成救命数，使狱友在事先定义好的某组内找到相同的数，根据组别得知暗格
翻转，即改变二进制咸鱼数中的某位元，对于每个咸鱼数，该操作都能产生n个对应的数（分别翻转第1，2……位）比如0可对应1、2、4…(2^n-1)，这些数都是0“身边”的数（以下简称翻转所得的数为身边数）
再看分组要求：要想万无一失，对于每个组，都须满足：对任意一咸鱼数，在进行恰当翻转后，需在组内找到至少一个对应的救命数。就是说，对任意一个属于2^n的数，在它的n个身边数中，必须至少有一个是组内的元素
反过来看，组内所有元素的身边数加在一起，必须囊括整个2^n个数的集合，否则就能找到这样一个咸鱼数，翻来覆去，在该组内都找不到对应的救命数，那该组对应的暗格就无法表示了
设某组元素个数为E，每个元素对应n个身边数，则组内所有元素的身边数相加，最多就只能是nE个（假设完全不重复），由上可知需满足nE>=2^n，推出E>=(2^n)/n
回头看组的定义：“将2^n个数分为n组”，可知，组数为n，所有组的元素数量和为2^n，因此对上述不等式，要想使之成立，就只能是E=(2^n)/n
由于E指组内元素个数，必须是整数才有意义，因此需满足(2^n)/n是整数，推导得n=2^m（m为整数）
对于一个正确的分组方式，每组中的任何元素的身边数都不会重复
以n=4为例：
(0, 1, 14, 15)对应暗格1
(2, 3, 12, 13)对应2
(4, 5, 10, 11)对应3
(8, 9, 6, 7)对应4
对于翻转，0可得1, 2, 4, 8
1得0, 3, 5, 9
14得15, 12, 10, 6
15得14, 13, 11, 7
可见，对于第一组，身边数无重复，覆盖所有16个可能的咸鱼数。其他组也满足这个条件（不难发现，其他组就是根据该组身边数有序推导出来的）

谈：有同样从ICPC昆明D题过来的不[doge][doge][doge]

这可太简单了，把浓浓的脚丫子臭味抹到那块上面就行了[doge]

谈：在这种编码要求下，会且只会在方格数量为2^k的情况下（k为正整数），能够构建完备的编码，证明过程是，方格数量为n；此时，空间是n维，染色点总数是2^n，颜色种类是n，如果没有其他要求，那么可能的染色方案是n^(2^n)种，在这么多种方案中，要求每个点的n个相邻点均为两两异色，每种颜色的点全部等价，则每种颜色的点有（2^n）/n个，所以需要2^n被n整除，因为没有别的质因数，于是只有n也可以表达为2^k的形式时才有解，并且也一定有解。

我把钥匙上的硬币立起来[妙啊][妙啊][妙啊]

谈：问：数学家是如何被关进监狱的???

等商量完对策，都刑满释放了。

谈：问题一我解出来了，只要把第一个硬币的状态当作易位符号即可

未经允许不得转载：易贰评 » 大家怎么看：【官方双语】不可能的棋盘谜题[第一更新]