生活中无处不在的奇偶校验法，你注意到了吗？

说到奇偶, 我们很自然地会联想到奇数和偶数. 奇偶校验法就是利用奇偶数的特性来判断事物可行性的一种思想方法. 我们可能在很多场合于不经意间都有使用过它. 下面我们就来介绍这一简单而强大的方法如何在解决现实问题和数学谜题中发挥作用的.

铺瓷砖问题

客厅地板上铺着 块 的正方形瓷砖（如图）. 但这些瓷砖已经破损, 需要重新更换。可惜, 目前这种正方形的瓷砖缺货, 只有 的长方形瓷砖。如果我们购买 块 的瓷砖, 能不能将地面重铺呢?

如果我们把图中 个格子涂上颜色, 使得格与格成黄白相间. 再数一数, 有 个黄格、 个白格(也可涂成 个白格、 个黄格). 而一块 的长方形瓷砖, 总能而且也只能盖住一个黄格和一个白格, 这样最多只能铺 块 的长方形瓷砖, 剩下的 个黄格（或 个白格）无法被铺盖. 所以, 用 块 的长方形瓷砖永远不能铺满.

奇偶校验法

把以上思考问题的方法体会一下, 我们会从中发现一些带有普遍性的东西.

如果两个整数都是奇数, 或都是偶数, 我们称这两个整数具有相同的奇偶性；如果两个整数, 一个是奇数, 一个是偶数, 就称这两个整数有相反的奇偶性.

在铺瓷砖问题中, 黄格、白格就如同奇数、偶数一样. 我们可以认为, 同色的两个格子具有相同的奇偶性, 不同色的两个格子, 具有相反的奇偶性. 显然, 一块 的长方形瓷砖能而且只能盖住相邻的具有相反的奇偶性的两个方格. 当用 块长方形瓷砖铺满后, 剩下的必然是两个同色的格子, 具有相同的奇偶性, 并且这两个格子肯定不相邻, 所以第 块长方形瓷砖是无法铺上去的.

这种用奇偶性对问题作出分析判断的思想方法可以称为奇偶校验法, 在密铺理论（属于组合几何学）中很有用处, 在其他场合也有用处。1957年, 著名的物理学家李政道、杨振宁因推翻了“宇称守恒定律”而获得了诺贝尔奖, 其中也用到了这一思想.

了解了奇偶校验法的基本原理后, 现在你能用奇偶校验法解决下面的问题吗？

国际象棋棋子战车（城堡）的走法是直线移动, 即战车可以在棋盘上沿直线水平或竖直方向移动任意格数. 那么战车从左上角的格子出发, 每步走 格, 是否存在一条路径能走遍每一个格子且每个格子只经过一次, 并最终到达右下角的格子？

答案：

根据题意, 国际象棋棋盘共64个格子, 一条成功的路径必然是白黑交替的, 从左上角的白格子出发, 经过所有64个格子即偶数个格子最后到达的必须是黑格子, 而右下角的是白格子, 因此以右下角的格子为终点这是不可能的.

从奇偶性来看, 棋盘上相邻两个格子一黑一白就是一奇一偶, 是具有不同的奇偶性的, 战车要走遍每个格子一次且只一次, 一条成功的路径必然是奇偶交替的, 如果总的格子数是偶数个, 则起点终点的奇偶性不同, 否则奇偶性相同, 由此便能判断可行性. 所以奇偶校验法可以在上述问题中, 给出判断可能性的必要条件, 一旦条件不满足, 就能得到否定的结论.

奇偶校验码

除了判断可行性, 我们还能利用奇偶性传递信息并判断信息的准确度, 一个典型的例子就是编码理论中的奇偶校验码.

编码理论属于计算机科学, 用于确保信息可以被存储和传输, 即使出现错误, 也能够检测到错误并恢复原始信息.

我们知道计算机通过网络传输比特序列, 在通过电缆或无线通道传输比特序列时, 可能发生单个比特或多个比特的错误. 通常情况下, 翻转单个比特的概率要比翻转两个或三个比特的概率更高.

比如, 计算机A计划传输字符串 " ", 在传输时有可能左起第三位发生翻转, 导致 " ". 那么如何使用编码来检测是否存在错误呢？常用的编码之一就是奇偶校验位.

这个想法很简单：我们在原始字符串的末尾附加一个额外的比特, 指定原始字符串中的 的数量是奇数还是偶数. 也就是, 如果原始字符串中的比特数是奇数, 额外的比特记为 " ", 如果是偶数, 则是 " ".

比如：

原始的 比特序列是 " ".

带有奇偶校验位的比特序列是 " ".

这里的额外比特是一个奇偶校验位, 表示前 位中的 的数量是奇数. 通过奇偶校验, 我们可以检测在传输过程中是否发生了单比特翻转错误. 假设由于传输错误导致第三位发生翻转, 我们得到 " ". 观察奇偶校验位, 我们发现它是 " ", 而比特序列中却有偶数个 " ". 因此, 我们得出结论传输中发生了错误.

下面我们给出经典的帽子谜题, 你能否用奇偶校验码的思想给出策略呢？

帽子谜题

有 名囚犯前后站成一排, 每个人都戴着红色或蓝色的帽子. 每个囚犯可以看到前面的人戴着什么颜色的帽子, 但看不到自己或后面的人的帽子颜色. 如果一个囚犯猜错了自己帽子的颜色, 他就会被处决.

现在的问题是, 囚犯们该如何合作以最大程度地减少被处决的人数？具体的, 如果囚犯们没有关于红蓝帽子数量的信息, 但仍要确保至少 人生存, 他们应该采取怎样的策略？

如果你没有想法, 你可以尝试着思考下面的问题.

根据题意, 每个囚犯可以看到前面的人戴着什么颜色的帽子, 那么这对他猜测自己的帽子颜色有什么帮助吗？

似乎信息是不够的, 因为不知道红蓝帽子的总数. 但是他后面的人知道啊, 那他后面的人能否将这个信息传递给前面的人呢？

根据题意, 每个囚犯只能回答自己帽子的颜色, 那么帽子的颜色能否与红蓝帽子的总数这一信息相关联, 或者与红蓝帽子数的奇偶性相联系呢？

下面我们就用编码理论中的奇偶校验位的思想提出一个有效的解决方案.

囚犯们在开始前聚在一起, 制定了以下方案：

• 最后一个囚犯, 向前看, 如果他前面的红色帽子数量是奇数, 他就说 "红色", 如果是偶数, 他就说 "蓝色". 也就是, 他计算了红帽子数量的奇偶性并将这一信息传递给其他人. 而这个囚犯有大约 的几率猜对.

• 倒数第二个囚犯, 他知道前面帽子的颜色, 也知道最后一个囚犯提供的 "奇偶性" 信息. 他可以计算出前面红帽子数的奇偶性, 然后推理出自己帽子的颜色.

• 其他任何囚犯, 他们知道前面帽子的颜色, 也知道所有在他们后面的帽子的颜色（除了最后一个囚犯的帽子）, 还知道最后一个囚犯提供的 "奇偶性" 信息. 这些信息足够他们来推断出自己帽子的颜色.

奇偶校验不仅能帮助我们判断一些问题的可行性, 同时利用奇偶校验码我们还能有效的传递信息, 你学会了吗？

参考文献

[1] 陈永明. 少年趣味代数学[M]. 北京：商务印书馆. 2012, 290-292.

[2] Parity and the Prisoners Hat Puzzle.

https://home.cs.colorado.edu/~srirams/courses/csci2824/lec1.pdf.

来源：数来数趣

编辑：十一

转载内容仅代表作者观点

不代表中科院物理所立场

如需转载请联系原公众号

1.2.

3.

4.

5.

6.

7.

8.

9.

10.