从群论角度看待3b1b的“不可能棋盘问题”
发布网友
共1个回答
热心网友
一、问题的图论叙述与群论解法。
之前观看3Blue1Brown的《不可能的棋盘问题》视频，对其中将棋盘问题转化为染色问题的方法感到震撼。但视频并未给出完整解决方案，我因此搁置了这个问题。直至昨天，一位朋友再次提及该视频及未解问题，我重新思考并整理了以下内容。
视频介绍了将棋盘问题转化为N维正方体的顶点涂色问题，并证明了N非2的幂时不可解，给出了N=4时的一种解法，并断言对任意N问题均有解。原问题较为复杂，转化过程也颇具巧思，具体可参考视频。以下将从转化后的涂色问题入手：
对给定的N，能否用N种颜色给N维的超正方体的顶点染色，使得任意顶点与其相邻的格点恰包含所有N种颜色？N维超正方体的顶点定义为[公式]，两个顶点相邻是指两个点的坐标只有一个分量不相同。
由涂色规则，与每个点相邻的顶点恰为N种不同的颜色。对所有顶点分别计数一次与其相邻的点及其颜色，恰好数遍了所有点相同的次数，每次计数时每种颜色出现的次数都+1。这说明每种颜色的点的个数应该相同，为[公式]个，这必须是个整数，因此N必须为2的幂才可能有解。
视频分析到这一步就停下了，现在我们需要对任意[公式]给出一个解。为此，我们先看看视频里给出的N=4时的解法以寻求启发：
染色问题的关键是“相邻”，而在4维时，每个点都有四个方向的邻居。让我们看看顶点向这四个方向走动会发生什么。以向上走为例，最左边红色的点走到了绿色点，最右边绿色点走到了红色点，与左边恰恰相反。我们可以把“向上走”这一操作理解成4种颜色间的一个置换！这启示我们问题之后的解决很可能跟群论有关。
...
二、Hamming Code与群代数。
朋友向我介绍了视频里的解法，该解法使用了一种编码技巧，灵感来源是汉明纠错码（Hamming code）。以N=4为例，我们可以用四位二进制数来编码超正方体中的16个顶点，然后用二位二进制数来编码上述二进制数的位数，然后将所有非零项对应的编码加起来得到一个二位二进制数，这个数即对应了这个点的颜色。
...
至此，我们终于找到了正确的看待问题的方式：引进群代数。于是我们终于可以用群代数的语言来给出前两个问题的答案了，叙述如下：
命题：考虑群代数 [公式]，则：
证明：直接计算可得。
至此，我们终于用群代数的语言统一了如上两种解答，并且给出了一个足够简洁的算法来得知任意一个点需要被染成何种颜色。可以算是完美解答了。至此我们走过了一段相当愉快的探索之旅，那么本文也就到此结束了，感谢阅读，我们下次再见！
