16囚犯问题所有解

yuange1975

#每日一题[超话]##数论[超话]##代数#  

新来的囚犯冒犯了典狱长。

这一天，他随便找了个罪名，将16个囚犯带到了审讯室。

“你们要为自己新的罪行付出代价，不过，出于仁慈，我再给你们一个机会。

我会给你们每个人背后贴一张纸，纸上的数字从1到16都有可能，不同的人数字可以重复。你们每个人都可以转过身来给别人看自己背上的数字。

从现在开始你们不准无故发出任何声音。之后你们会被警卫依次带到我的办公室，告诉我你自己背后的数字是多少。

只要你们16人中有一人猜对自己背后的数字，我就会既往不咎；但如果你们都猜错了，则全部吊死。

要怎样做才能避免死亡的命运呢？我最后给你们5分钟商量对策。5分钟之后就不准再发出声音。同时，如果游戏过程中有任何人做出令人生疑的好似传递信息和暗示的举动，则所有人都要死！”

朋友们，要如何度过这一难关呢？能帮他们想出求生策略吗？

——————
这个问题当年升到了未名bbs话题榜前三。


这个比较有名的16囚犯问题，找到一个解比较容易，其实就是一个“拉丁球”问题，可以找出所有解。

https://weibo.com/6236276241/4874453014548415

答案：
只要找一个n个元素的群，就可以符合上面题目的要求了。每个人不重复分配n个中的一个，然后和他看到的其它n-1个元素运算，得到的数字报出来就行。

其实很简单，n个元素的群，群里有某个封闭的运算f满足n个方程f(a1,a2,…an)=k（k从1-n，更准确的表达是1-n号元素）简单的群的知识必定有1个方程是正确的，也只有1个方程是正确的。而每个方程f里有n-1个已知数，1个未知数ai，那么剩下一个ai就可以解出来。对的那个方程必定会得到自己正确的ai。另外也可以看出来，这个有也只有1个报出了正确的ai。

n个元素的群就太多了，比如n的同余。
xor运算是2^m个元素的群，所以比如16等这种数字xor运算可以满足。

我们再仔细分析，其实n个元素的集合的f运算，只需要满足：
(1) 封闭性。n个元素的集合，f运算都在集合内。
(2) 可逆性。方程f(a1,a2,…an)=k（集合的第k个元素）对于任意n-1个已知数都可以求出ai，ai取值范围是n个元素。这就要求ai取遍n个元素，k也必须取遍n个元素，也就是一一映射。

注意这题目ai可以重复，ai可重复实际上是一个类似拉丁方一样的n^n的超级“拉丁球”，可以想象成每一条直径是n的一个排列。
这个“拉丁球”就是这道题的通解，比如n的同余只是其中一个比较常见和方便的解。

比如15个人，写的数字是1-15，1-15的数字做一个15的剩余的映射，这个只要一一映射就行可以是任意n对n的任意置换，显然这个映射可以取数字本身。取f=∑ai=k mod n 解得ak=k+(ak-∑ai) mod n ，(ak-∑ai) 表示求和里少了自己那一项。然后再对ak和1-15做一个前面映射的逆映射就行，比如前面1-15取数字本身的映射简单的可以15的剩余0算成剩余15，这样就逆映射到了1-15去了。

比如1-5 的5个人数字分别是 3，4，1，1，3
1号看到的是4，1，1，3算出来就是1+3-12=2 mod5
2号得到2+4-12=4 mod5

3号得到 3+1-12=2 mod 5
4号得到 4+1-12=3 mod 5
5号得到 5+3-12=1 mod 5

显然∑ai=12=2 mod n 就2号成功的正确得到了自己的ai，别的都错误了。

这个也可以从信息论或者概率论角度出发，得到要保证每次都有一个正确答案也每次只能一个正确答案，n*1/n=1。


前些天解一个囚犯猜数字问题，发现通解是一个n维“拉丁球”。
n维“拉丁球”的一个二维切面就是一个n*n的拉丁方，拉丁方还是很有意思的。

拉丁方或者拉丁方阵（英语：Latin square）是一种 n × n 的方阵，在这种 n × n 的方阵里，恰有 n 种不同的元素，每一种不同的元素在同一行或同一列里只出现一次。常规数独就是一个拉丁方阵。

当一个拉丁方阵的第一行与第一列的元素按顺序排列时，此为这个拉丁方阵的标准型。

拉丁方阵的标准型行之间交换和列之间交换就可以得到普通型，普通型也可以交换后得到标准型，所以基本上可以只考虑标准型。

1-3阶拉丁方阵标准型都只有1个，1阶的拉丁方阵有1*1个，2阶有2*1！=2个，3阶有3！*2！=12个。n阶方阵标准型有m个，那么n阶方针有m*n!*(n-1)!个。

0

01
10

012
120
201

2阶是xor或者模2的+法同余（可以看成+法）群，这时候两个运算其实是同一个运算。

3阶是模3的+法同余群。

3阶的拉丁方阵只有一种标准型，那么标准的3阶的拉丁球也只有一种。3阶的拉丁球也都是这个拉丁方阵的行、列变换，3*2*2*2=24种。

4阶标准型有4个:

0123
1032
2301
3210

xor ^

0123
1032
2310
3201
#

0123
1230
2301
3012

+

0123
1302
2031
3210

*

第一个是xor异或运算(^)群。

第二个是部分异或运算群，暂时叫#运算吧。异或运算也很有特点，2^m个元素，方阵本身又分块，2^（m-1）阶的^运算方阵是其子方阵。

第三个是模4的+法同余群。

第四个是模5（n+1素数）的*法同余群。f(a,b)=(a+1)*(b+1)-1=ab+a+b mod 5。+1和-1是对应值域一一映射。

可以看出还是模n的+法同余运算是最简单最通用的。不过这个运算太规律，在拉丁方阵的一些应用中也已因为这种太规律反而不好被淘汰。

一般性，f(a,b)=H(F(a)⊕G(b))，F(a)、G(b)、H(c)都代表值域的一一映射，一一映射也就有其对应都逆映射。⊕代表运算符，不是特指异或运算。

4阶的拉丁球，就可以四种运算之间组合，可以同一个运算，也可以不同运算。

l4m2

并不需要它是群，在三个人的情况下，f(a,b,c)=a+b+2c(mod 3)是合法解