5人猜数问题

KeyTo9_Fans

$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$。

这个上界能否达到呢？

我们期待编程高手给我们一个完美的答案。

geslon

为什么极限是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，这些只能放弃了。

geslon

对不起，看不到全部人的帽子，我看错题目了，呵呵。

jsliyuan

如果策略是线性的 比如定点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 我们知道这是可以达到的

KeyTo9_Fans

对于非线性的情况，比如：
$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? ... +Network+Codings%22

……报告中听到的。

zgg___

我算了一下，得到了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。）

1. 
   
2. c[s1_,s2_]:= Module[{x},If[s1>=s2,Return[0]];
   
3. x=Map[First[#]==Last[#]&,Transpose[{IntegerDigits[s1,3,5],IntegerDigits[s2,3,5]}]];
   
4. x=Join[x,x];If[Apply[Or,Table[And[x[[i-1]],x[[i+1]],Not[x[[i]]]],{i, 2, 6}]],0,1]];
   

复制代码

3、寻找某个图的最大完全子图
243个节点根据其相容性构成一个图，对于这个图的某个完全子图，可以找到猜测的策略，使得帽子分布
是这个完全子图的某个节点时，5个人都依据这种策略都猜对。反之，这个243个节点的图的最大完全子图
的节点个数，就是能够猜对的最大状况数。因为更多的节点中存在不相容的节点，不相容的节点意味着会
有人当输入确定时要求输出不同的数。
寻找某个图的最大完全子图是一件麻烦的事情，这是一个NP问题，还好，这个图具有一定的对称性，而且
规模不算太大。算法是这样的：穷举删除所有的节点中的一个，生成一些少一个节点的图，然后合并彼此
同构的图，然后循环，是广度优先搜索的方法。
在图ms中，删除第k个节点实现代码如下：

1. 
   
2. delk[ms_,k_]:= Module[{vs1},vs1=Join[Map[First,Select[ms,Last[#]==k&]],
   
3. Map[Last,Select[ms,First[#]==k&]]];Select[ms,Length[Intersection[#,vs1]]==2&]];
   

复制代码

生成那个243个节点的图的代码如下：

1. 
   
2. ms=Rest[Union[Flatten[Table[If[c[i,j]==1,{i,j},0],{i,0,3^5-1},{j,0,3^5-1}],1]]];
   
3. ms//Length
   
4. ss={{ms,{}}};
   
5. f=0;ff=StringJoin["d:\\fan\\f", ToString[f],".txt"];Put[ss,ff];
   

复制代码

代码生成一个含有20898条边的图，放在一个文件里。
下面是搜索最大完全子图的代码，运算时间较长，每运行一次生成一个文件，要手动循环，其中的判断图
同构的函数IsomorphicGraphQ貌似要M8的版本。

1. 
   
2. ss0=Get[ff];ss={};ssg={};
   
3. For[n=1,n<= Length[ss0],
   
4.   ms=First[ss0[[n]]];If[ms=={},n++;Continue[]];
   
5.   mk=Last[ss0[[n]]];vs=Union[Flatten[ms]];
   
6.   For[i=1,i<= Length[vs],
   
7.    k=vs[[i]];m=delk[ms,k];If[m=={},i++;Continue[]];v=Union[Flatten[m]];
   
8.    g=Graph[v,Map[First[#]\[UndirectedEdge]Last[#]&,m]];
   
9.    For[j=1,j<=Length[ss],If[IsomorphicGraphQ[g,ssg[[j]]],Break[]];j++];
   
10.    If[j==Length[ss]+1,AppendTo[ss,{m,Append[mk,k]}];AppendTo[ssg, g]];i++];
    
11.   If[Mod[n,2]==0,Print["n=",n," s=",Length[ssg]];];n++];
    
12. ss//Length
    
13. f++;ff=StringJoin["d:\\fan\\f",ToString[f],".txt"];Put[ss,ff];
    

复制代码

循环10次后（循环11次后结果为空），用下面代码输出最大完全子图的节点：

1. 
   
2. s={};For[i=1,i<=Length[ss],as=ss[[i,1]];bs=ss[[i,2]];s=Join[s,Map[Join[bs,#]&,as]];i++]；
   
3. Union[Map[Sort,s]]
   

复制代码

可得到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的几率，更大的貌似就没有了。呵呵。

mathematica

4# jsliyuan


我以为你看懂了这个问题，原来是首帖奖励！

mathematica

7# zgg___


牛逼呀，我没看明白。。。。。