囚犯A和B被告知,他们可以提前释放,只要他们能解决警卫在8X8方格棋盘上随机选择一个方格的谜题。在该8X8方格中,每一块方格可以只有一个硬币或者是空格。守卫隔离A,并在棋盘上仅向B展示一个他随机选择的方格,要求B在棋盘上的某个方格中只添加或移除一枚硬币作为对A的提示,尔后A不与B交流,仅通过观察棋盘上硬币的分布辩别守卫向B显示的特定方格。如果A能通过棋盘上硬币的分布分辨出守卫选择的方格,A和B都可以释放。在警卫向B展示棋盘之前,A和B知道要采取的规则和步骤,并被允许设置游戏策略,即构建算法来解决谜题。
例如下图是有14枚硬币在棋盘上的一个分布,其中x表示该方格占有硬币,显示红圈的为守卫选择的方格(一般情况下该方格硬币可有可无)。囚犯B需要在棋盘某一方格中添加(如果为空)或取下(如果己占)硬币,用以提示A守卫所选择带红圈的方格。哪个方格需要添加或取出硬币?为方便起见,可以假定在方格中取出硬币等价于在该方格上添加第二枚硬币,问题则为囚犯B在采取某种策略的前提下,应该在哪一个方格里添加一枚硬币可以正确地提示囚犯A关于守卫在棋盘上所选择的方格?
囚犯A和B可以约定对棋盘上硬币标号进行异或运算操作。棋盘上每一方格可以用数字0-63标号,故每一枚硬币所处的方格可以唯一地用0-63中一个数字表示出来。B进一步对所有硬币所占方格的标号以及守卫选择的方格进行异或运算,结果就是囚犯B需要添加一枚硬币方格的标号,注意棋盘方格标号是随机但是唯一的。假定所有硬币标号在异或操作后结果为a,守卫所选方格标号为b,c = (a异或b)则为需要添加硬币方格的标号。因此A仅需对其后所有硬币方格的标号进行异或运算,其结果就是守卫选择的方格标号。
证明十分简单。因为c=(a异或b),故(c异或c)=((a异或b)异或c)=((a异或c)异或b)=0,从而(a异或c)= b。
由此可见,在囚犯B选择方格标号c放置一枚硬币后,囚犯A可以将他所观察的硬币通过事先约定的方格标号,将所有硬币的标号作异或操作,得出守卫所选择的方格。这里我们无需考虑取出硬币(等价于同一方格两枚硬币)的情况,因为有两枚硬币同一标号的异或运算等价于0。
在上例中,如果我们先自左向右然后从上到下将棋盘方格顺序标号,则所有硬币方格标号异或操作后为十进制数49,守卫所选方格为21,(49异或21)=36,当囚犯添加一枚硬币于标号36(注意这里是取出或添加第二枚硬币)的方格后,(49异或36)=21。显然,守卫的方格无需定义在8X8棋盘上,它们可以排列为64个方格为一行顺序标号。这种异或运算操作可以解决各种类似的智力问题,如著名的尼姆愽弈。
参见http://datagenetics.com/blog/december12014/index.html