5人猜数问题
5个人围成一圈玩猜数游戏，如下图所示。庄家给每个人的头上各戴1顶帽子。
帽子上都写了$1$个数。
每个数是$1$、$2$、$3$的概率均为$1/3$，且相互独立。
这$5$个人都只能看到与他相邻的$2$个人的帽子上的数，看不到自己的和较远的$2$个人的帽子上的数。
庄家要求他们同时说出自己头上的数。
如果$5$个人都说对了就算赢，如果有人说错了就算输。
问：如何猜才能使赢的概率最大？
例$1$：
$5$个人的策略都是不管看到什么都猜$1$。
结果只有当$5$个数都是$1$的时候赢，其余情况输。
赢的概率为$1/243$。
例$2$：
$5$个人的策略都是右边是什么数就猜什么数。
结果只有当$5$个数都相同的时候赢，其余情况输
赢的概率为$3/243$。
例$3$：
第$1$个人说第$2$个人的数，
第$2$个人说第$1$个人的数，
第$3$个人说第$4$个人的数，
第$4$个人说第$3$个人的数，
第$5$个人说$1$。
结果当前$2$个人的数相同，第$3$个人和第$4$个人的数相同，第$5$个人的数是$1$的时候赢，其余情况输。
赢的概率为$9/243$。
通过信息论可以知道，无论他们采取什么策略，赢的概率都不会不超过$15/243$。
这个上界能否达到呢？
我们期待编程高手给我们一个完美的答案。 为什么极限是15/243？我来抛个砖，能达到63/243，超过1/4.
我的办法是，抓住所有形如AAAAA（5个一样）和AAABC（三个一样、另两个不同）的机会，机会是3+60=63.
策略：所有人看到AAAA就猜A（确保5个一样时中）；看到AAAB就猜C，看到AABC，就猜A（确保AAABC中）。
万一看到AABB，就随便猜吧，一定中不了了。AABBC的出现概率为3*5*6*2/243=180/243，这些只能放弃了。 对不起，看不到全部人的帽子，我看错题目了，呵呵。 如果策略是线性的 比如定点x2它的猜测为x2 = A1x1+B1x3+C1
为了方便 把运算都限定在GF(3)上
那么最后能hit中的解数=3^{5 - rank}，rank为线性方程组的秩 线性方程组具有以下的形式
x1 x2 x3 x4 x5
? 1 ?
? 1 ?
? 1 ?
? ? 1
这个矩阵的秩至少为3 因此线性策略的概率<= 9/243 并且通过例3 我们知道这是可以达到的 对于非线性的情况，比如：
$x_2$ = ? + ?$x_1$ + ?$x_3$ + ?$x_1^2$ + ?$x_3^2$ + ?$x_1x_3$ + ?$x_1^2x_3$ + ?$x_1x_3^2$ + ?$x_1^2x_3^2$
需要填入$9$个$0$到$2$的系数，一共有$3^9$种方案。
$5$个人一共有$(3^9)^5=3^45$种猜数方案。
经枚举，方程组最多有$12$个解。
即最佳策略下赢的概率为$12/243$，没有达到$15/243$的信息论上界。
该信息论上界是从冯克勤的"Guessing Number of Graphs and Network Codings"……
http://www.google.com.hk/search?hl=zh-Hans-HK&source=hp&q=%22Guessing+Number+of+Graphs+and+Network+Codings%22
……报告中听到的。 我算了一下，得到了12/243的解，如果计算没有问题，貌似没有更好的解了。
计算过程如下：
1、先说明一下“确定性”方案和“概率性”方案的区别。
那5个戴帽子的人中的每一个人都会采取一种方案，这种方案的输入是他旁边的两人帽子上的数，输出是
他猜测的数。如果他在输入确定的情况下，输出的猜测总保持不变，那么方案就是“确定性”的，反之就
是“概率性”的。即如果根据两边帽子上的数完全决定了所猜测的数，那么他采取的就是“确定性”方案
。比如说：他总猜1，就是“确定性”方案；他看到两边的人帽子上的数都是1，那么他通过投币来决定是
猜1还是2，就是“概率性”方案。如果5个人都采用“确定性”方案，那么整个方案就是“确定性”的。
可以看到：“概率性”方案是某几个“确定性”方案的加权平均，所以最优方案一定是“确定性”的。好
了，我们下面只讨论“确定性”方案了，啰嗦了半天，呵呵。
2、节点的相容性
5个人的帽子上的数一共有3^5=243种可能性，我们称为243个节点，为什么叫节点，看了下面可能就会明
白，呵呵。
比如说：5个人帽子上的数依次是{0,1,2,0,0}（为了方便，从现在起帽子上的数是012而非123了），其中
第2个人看到，左右的人的数分别是0和2，那么他要猜1才正确，而另一个节点{0,0,2,0,0}是和节点
{0,1,2,0,0}不相容的。因为对于第2个人来说，他在两个节点上，不能都猜对。而节点{0,1,2,0,0}和节
点{2,2,2,2,2}是相容的。如果243个节点对应0到242的数，那么节点s1和s2的相容性可以由下面的代码确
定。（当s1和s2相容时，返回1。）
c:= Module[{x},If];
x=Map==Last[#]&,Transpose[{IntegerDigits,IntegerDigits}]];
x=Join;If],x[],Not]]],{i, 2, 6}]],0,1]];
3、寻找某个图的最大完全子图
243个节点根据其相容性构成一个图，对于这个图的某个完全子图，可以找到猜测的策略，使得帽子分布
是这个完全子图的某个节点时，5个人都依据这种策略都猜对。反之，这个243个节点的图的最大完全子图
的节点个数，就是能够猜对的最大状况数。因为更多的节点中存在不相容的节点，不相容的节点意味着会
有人当输入确定时要求输出不同的数。
寻找某个图的最大完全子图是一件麻烦的事情，这是一个NP问题，还好，这个图具有一定的对称性，而且
规模不算太大。算法是这样的：穷举删除所有的节点中的一个，生成一些少一个节点的图，然后合并彼此
同构的图，然后循环，是广度优先搜索的方法。
在图ms中，删除第k个节点实现代码如下：
delk:= Module[{vs1},vs1=Join==k&]],
Map==k&]]];Select]==2&]];
生成那个243个节点的图的代码如下：
ms=Rest==1,{i,j},0],{i,0,3^5-1},{j,0,3^5-1}],1]]];
ms//Length
ss={{ms,{}}};
f=0;ff=StringJoin["d:\\fan\\f", ToString,".txt"];Put;
代码生成一个含有20898条边的图，放在一个文件里。
下面是搜索最大完全子图的代码，运算时间较长，每运行一次生成一个文件，要手动循环，其中的判断图
同构的函数IsomorphicGraphQ貌似要M8的版本。
ss0=Get;ss={};ssg={};
For,
ms=First]];If];
mk=Last]];vs=Union];
For,
k=vs[];m=delk;If];v=Union];
g=Graph\Last[#]&,m]];
For,If]],Break[]];j++];
If+1,AppendTo}];AppendTo];i++];
If==0,Print["n=",n," s=",Length];];n++];
ss//Length
f++;ff=StringJoin["d:\\fan\\f",ToString,".txt"];Put;
循环10次后（循环11次后结果为空），用下面代码输出最大完全子图的节点：
s={};For,as=ss[];bs=ss[];s=Join&,as]];i++]；
Union]
可得到15组结果，如下：
{{0, 4, 8, 36, 40, 72, 116, 122, 154, 224, 230, 236},
{0, 4, 8, 36, 40, 72, 116, 148, 154, 224, 230, 236},
{0, 4, 8, 36, 72, 80, 112, 118, 133, 200, 215, 220},
{0, 4, 8, 36, 72, 80, 112, 118, 133, 200, 220, 241},
{0, 4, 8, 36, 72, 112, 118, 133, 200, 215, 220, 224},
{0, 4, 8, 36, 72, 112, 118, 133, 200, 220, 224, 236},
{0, 4, 8, 36, 72, 112, 118, 133, 200, 220, 236, 241},
{0, 4, 15, 45, 86, 98, 153, 161, 193, 208, 215, 229},
{0, 4, 15, 45, 86, 98, 153, 161, 202, 206, 208, 220},
{0, 4, 15, 45, 86, 98, 153, 161, 202, 206, 220, 235},
{0, 4, 15, 45, 86, 98, 153, 161, 202, 208, 215, 220},
{0, 4, 15, 45, 86, 149, 150, 153, 193, 209, 214, 229},
{0, 4, 15, 45, 86, 149, 150, 153, 193, 209, 214, 232},
{0, 4, 15, 45, 86, 149, 150, 155, 193, 209, 214, 229},
{0, 4, 15, 45, 86, 149, 150, 155, 193, 209, 214, 232}}
可以看到它们都对应12/243的几率，更大的貌似就没有了。呵呵。 4# jsliyuan
我以为你看懂了这个问题，原来是首帖奖励！ 7# zgg___
牛逼呀，我没看明白。。。。。
页:
[1]