最近天 作者： 主题： 内容：
 进入版区才能发表文章 
 您当前的位置： 推理之门 > 谜题解析 > 谜题大全   【版主】：tl,艾米,popodian 字体大小：
第1页/共1页（总计9个回复）
主 题： Hat问题我的最新研究成果！（人气：625）
 holmos（大力）
1 楼： Hat问题我的最新研究成果！ 01年07月21日14点17分


经过几个晚上的苦思冥想，我想我终于找到解决那个Hat问题的方法了！
最大的体会是——创造Hamming码的人真是了不起！！实在佩服！！！确实要用到Hamming码方面东西啊，我现在已经找到了7个人时的解决方法，并用程序采取穷举法证明了它的正确性。但可惜的是我无法从数学上证明它，所以虽然我几乎可以肯定这个方法对于所有(2的n次方-1)个人的情况都适用，但我无法用数学证明，我只是用穷举法检验了n=3的时候的正确性。

举n=3，也就是7个人的例子：

在叙述整个方法之前，先把7位情况下的Hamming码列举出来，共16种，如下：

假设7位码各位的名称分别为a6、a5、a4、a3、a2、a1、a0，

a6 a5 a4 a3 a2 a1 a0
--------------------
0 |0 |0 |0 |0 |0 |0
0 |0 |0 |1 |0 |1 |1
0 |0 |1 |0 |1 |0 |1
0 |0 |1 |1 |1 |1 |0
0 |1 |0 |0 |1 |1 |0
0 |1 |0 |1 |1 |0 |1
0 |1 |1 |0 |0 |1 |1
0 |1 |1 |1 |0 |0 |0
1 |0 |0 |0 |1 |1 |1
1 |0 |0 |1 |1 |0 |0
1 |0 |1 |0 |0 |1 |0
1 |0 |1 |1 |0 |0 |1
1 |1 |0 |0 |0 |0 |1
1 |1 |0 |1 |0 |1 |0
1 |1 |1 |0 |1 |0 |0
1 |1 |1 |1 |1 |1 |1

希望上面没抄错。呵呵..

a6、a5、a4和a3在Hamming码中实际上对应的是信息位，而a2、a1、a0对应的是监督位。换句话说，就是4位信息码和3位纠错码的组合。这些我就不多写了，有兴趣的找相关书看吧。

之所以列出来，是因为后面的方法中是要用到举例说明的。

好了，该隆重介绍我的方法了，呵呵..我的方法是这样的：
首先，定义两种颜色的帽子分别对应数字1和0，这样比较好叙述，假定红色—1，白色—0。
7个人依次进入房间，被戴上帽子，然后他们站成一排，每个人都可以看到其他6人的帽子颜色，于是，关键步骤到了——每个人依次把自己当作Hamming码中的a6、a5、a4、a3、a2、a1和a0，每个人都要这么做。同时每个人手里都拿着一份象我上面一样的Hamming码的编码表，于是，每个人将其他人的组合情况与表中16组编码相应位置的组合情况去对照，如果发现在表中的16组码当中，出现了在某一组编码当中除去自己位以外的其他所有位都与自己旁边的6个人的组合一样，那好，他找到表中的那组编码，查看自己所对应的位在那一组编码中是什么，如果是0，则这个人就猜自己是1，反之，如果表中的a6是1，则他猜自己是0。如果这个人在整个表中都找不到有哪一组符合上述情况，那么这个人就放弃回答。

下面举例说明：
例如，7个人A、B、C、D、E、F、G进入房间，假设他们的帽子颜色分别是“红白红红白红红”，对应成1和0就是“1011011”
好，7个人依次站成一排，即，A的左边是B，B的左边是C，C的左边是D，...F的左边是G。
接着，分别把A、B、C、D、E、F、G看作a6、a5、a4、a3、a2、a1、a0。
于是A把B、C、D、E、F、G的组合“011011”分别与上面表中16组码中的a5、a4、a3、a2、a1、a0相对比，最后，他发现他找不到完全一样的，于是A放弃；
B把A、C、D、E、F、G的组合“111011”与上表中16组码的a6、a4、a3、a2、a1、a0相比较，看有无一样的，可惜，也没有，所以B也放弃。
依次类推，可以推出A、B、C、D、E、G都找不到一样的，于是他们都放弃。
惟独F例外，让我们看看他的情况吧，他将A、B、C、D、E、G的组合“101101”与上面码组中的a6、a5、a4、a3、a2、a0相对比，发现第12组编码“1011001”满足要求，于是F找到这组编码中自己对应位置a1的数字，发现是0，所以F便猜自己是1，也就说自己的帽子是“红”的。

按照上面这个方法，可以得出结论，只有当ABCDEFG的组合出现与上面表中16组码中的某一组完全一样的时候，才会出现所有人都猜错从而失败的情况，而对于其他的情况，则总会成功！7个人所戴帽子总共有2*2*2*2*2*2*2=128种可能，所以失败的可能性是16/128=1/8，也就是说成功的可能性是7/8=87.5%

看了上面这个例子，大家对我的方法都应该有所了解了吧，但我相信，你们的疑问也紧接着就来了：

问题1：你怎么能保证对于任意一个7位的组合，总会有某个人发现其他6人的组合与表中某条编码相应位置的数字完全一样？

对于这个问题，很遗憾，我无法用数学来证明他，但我用程序证明了！而且程序还证明了，每次成功的时候，只有1个人回答对了，而其他6人都是放弃的！关于这点，倒是不难证明，只要根据Hamming码的码间距离为3（用通俗的话说，就是任意两组码，都有3位数不同）就可以知道了。而当失败的时候，是7个人都回答错！也就是说，如果把所有128种情况都遍历一下，你会惊奇的发现，所有回答正确和回答错误的人是一样多的！
所以，如果你能从数学上证明的话，那是再好不过了！

问题2：为什么会想到用这种方法？

呵呵。。。如果让我凭空想的话，恐怕想破脑袋也想不出，好在原文作者虽然没有提供解答的方法，但提示了思路，所以我从一开始便查阅关于Hamming码的书籍，详细了解它的编码方法，虽然这些对于解决这个问题可能都没有什么用处，但这却是一个整理思路的过程。再加上几个晚上的分析、讨论与思考，才突然之间想到的。关键在于把握一点——要让所有人在失败的时候每个人都答错！这是关键。

问题3：为什么Hamming码可以很好地解决这个问题？

用Hamming码相关的知识可以很好地解决这个Hat问题，而且可以说是现在为止最好的、效率最高的方法。至于为什么它能解决这个问题，我只能说这种编码的创始人Richard Hamming太了不起了，这种编码方法太奇妙了，我无法解释更多，只能赞叹这种编码的神奇。

问题4：作为江南四大才子之一，你有没有感到压力？

压力，当然是有的（做深沉状）...不过每当感到压力的时候，我总是想到祖国在我心中，于是我就有了无穷的动力.....哎哟！！这是谁的鞋子！？...哎..这还有一只，..这也有.....好多啊........

呵呵....其他一些比较简单的问题我就不在多说了，我估计可能大多是关于编码的，其实Hamming码是很有特点的，通过仔细观察它的编码特点，相信不难解决你们的问题。


　　点击复制本贴地址：



没有完美的犯罪......

※来源: 【 推理之门 Tuili.Com 】.
 赵开方（Charlie Chen）
2 楼： Re:Hat问题我的最新研究成果！ 01年07月19日18点16分


【holmos在大作中谈到:】
＞
＞经过几个晚上的苦思冥想，我想我终于找到解决那个Hat问题的方法了！
... ... ... ...
＞问题4：作为江南四大才子之一，你有没有感到压力？
＞
＞压力，当然是有的（做深沉状）...不过每当感到压力的时候，我总是想到祖国在我心中，于是我就有了无穷的动力.....哎哟！！这是谁的鞋子！？...哎..这还有一只，..这也有.....好多啊........
＞
＞呵呵....其他一些比较简单的问题我就不在多说了，我估计可能大多是关于编码的，其实Hamming码是很有特点的，通过仔细观察它的编码特点，相信不难解决你们的问题。
＞

我虽然是不懂啦，但还是要祝贺大哥。
有句名言----成功的喜悦是一种非常熟悉的感觉。

顺便问一句：

那三大才子是谁？:l






                    才  成  学  自
        吃                                    拐 
        一                                    一
        堑                                    年
        长                                    摇
        一                                    一
        智                                    年
        谢                                    缘
        谢                                    份
        啊                                    哪

※来源: 【 推理之门 Tuili.Com 】.
 hitachi41（罗修——坑王之王）
3 楼： Re:Hat问题我的最新研究成果！ 01年07月19日18点40分


难道大力名叫唐寅？不会吧。
不过他的主页上好像是holmos_tang来着。
大力姓tang看来是没错了。
恭喜大力才子攻克难题，尽管我也没看明白，不过相信总有人懂。:e:e:e






北邻有精，其名为狐；化而为女，其名为艾。艾之魅，不知其几万迷。喜而笑，其貌倾千城之国也。东坑小骡子


有关原创小说的作者专栏开通因本人机器问题，时常无法登陆后台，暂时无法受理。

罗修的群魔乱舞http://blog.sina.com.cn/u/1417662535

※来源: 【 推理之门 Tuili.Com 】.
 三国公子（社长）
4 楼： Re:Hat问题我的最新研究成果！ 01年07月19日19点02分


【holmos在大作中谈到:】

我想问题一跟编码组合有关吧，换句话说，只要改变其中某一组，结论就不成立了。

总之，俺不懂哈明码
:b






 

哦……

※来源: 【 推理之门 Tuili.Com 】.
 dzqq（dzqq）
5 楼： Re:Re:Hat问题我的最新研究成... 01年07月20日11点50分


嘿嘿，很复杂啊，不太明白:g:g:g







※来源: 【 推理之门 Tuili.Com 】.
 bete（bete）
6 楼： Re:Hat问题我的最新研究成果！ 01年07月20日14点08分


【holmos在大作中谈到:】


大力兄的个人网页的地址是什么？:b






闪闪满天星，我要摘那天边的星。。。呵呵呵呵

※来源: 【 推理之门 Tuili.Com 】.
 mac（mac）
7 楼： Re:Hat问题我的最新研究成果！ 01年07月20日15点19分


关于汉明码的距离为3，好象不是你那么解释吧？相邻的码间距确实是3，但不是任意。

方法真的很好，汉明码也确实是个很基础的编码，不过我不知道有这么有用。当初学的时候，也不知道究竟怎么纠错。我以为4位信息就要占用3位来判断并不划算。







※来源: 【 推理之门 Tuili.Com 】.
 hitachi41（罗修——坑王之王）
8 楼： Re:Re:Hat问题我的最新研究成... 01年07月20日15点21分


【bete在大作中谈到:】
＞
＞【holmos在大作中谈到:】
＞
＞
＞大力兄的个人网页的地址是什么？:b
http://holmos_tang.home.chinaren.com






北邻有精，其名为狐；化而为女，其名为艾。艾之魅，不知其几万迷。喜而笑，其貌倾千城之国也。东坑小骡子


有关原创小说的作者专栏开通因本人机器问题，时常无法登陆后台，暂时无法受理。

罗修的群魔乱舞http://blog.sina.com.cn/u/1417662535

※来源: 【 推理之门 Tuili.Com 】.
 mac（mac）
9 楼： Re:Hat问题我的最新研究成果！ 01年07月20日15点58分


另外，我给你证明为什么任何一种情况下，一定会有人回答（也就是为什么会有人可以对上编码表，从而回答而不是放弃）。
实际情况，实际讨论。还是沿用我们熟悉的编码来回答。改变为编码的时候，问题就变成了对于其他128-16=112种情况，每种情况都有一个汉明码和它距离为1（正是有距离的那位回答正确）。但这要用汉明码的性质，因为汉明码的码间距不小于3。所以，对于每个汉明码，都有7个和它距离为一的编码，并且由于汉明码之间距离不小于3，可知这7个码不会和其他任一个汉明码距离为1（最小为2）。
那么可以得到16*7=112，也就是说，所有剩下的编码都可以找到一个和自己距离为1的汉明码。转回原来的问题，就是那112种情况下，都会有人回答并且只有他自己回答正确。

剩下的还继续探讨编码问题。对于纠错编码不知道你怎么理解，我认为汉明码纠错能力比较强，但开销并不小。因为只要传来的码不是汉明码，就认为应该是和它相近的汉明码，进行纠错（因为传错2个码比传错一个码的概率要大的多，尤其在某些可靠传输的设备上），所以事实上汉明码的纠错比较强，但它的开销大了点。
关于汉明码的距离问题，我也记不清楚了，还请你有时间转告。

最后，关于这种hat问题。不论有多少人，只要我们可以找到合适的编码方法（就是类似汉明码这种），就可以得到答案。知道结果是什么？n/(n+1)当然我们现在还不能认定这就是最好的。
要得到n/(n+1)并不难，只要你的编码能遍历2^n/(n+1)，并且码间距离不小于3，就可以。方法就是如你所说，按编码表去对。







※来源: 【 推理之门 Tuili.Com 】.
 holmos（大力）
10 楼： Re:Re:Hat问题我的最新研究成... 01年07月21日14点17分


【mac在大作中谈到:】
＞
＞另外，我给你证明为什么任何一种情况下，一定会有人回答（也就是为什么会有人可以对上编码表，从而回答而不是放弃）。
＞实际情况，实际讨论。还是沿用我们熟悉的编码来回答。改变为编码的时候，问题就变成了对于其他128-16=112种情况，每种情况都有一个汉明码和它距离为1（正是有距离的那位回答正确）。但这要用汉明码的性质，因为汉明码的码间距不小于3。所以，对于每个汉明码，都有7个和它距离为一的编码，并且由于汉明码之间距离不小于3，可知这7个码不会和其他任一个汉明码距离为1（最小为2）。
＞那么可以得到16*7=112，也就是说，所有剩下的编码都可以找到一个和自己距离为1的汉明码。转回原来的问题，就是那112种情况下，都会有人回答并且只有他自己回答正确。
＞
＞剩下的还继续探讨编码问题。对于纠错编码不知道你怎么理解，我认为汉明码纠错能力比较强，但开销并不小。因为只要传来的码不是汉明码，就认为应该是和它相近的汉明码，进行纠错（因为传错2个码比传错一个码的概率要大的多，尤其在某些可靠传输的设备上），所以事实上汉明码的纠错比较强，但它的开销大了点。
＞关于汉明码的距离问题，我也记不清楚了，还请你有时间转告。
＞
＞最后，关于这种hat问题。不论有多少人，只要我们可以找到合适的编码方法（就是类似汉明码这种），就可以得到答案。知道结果是什么？n/(n+1)当然我们现在还不能认定这就是最好的。
＞要得到n/(n+1)并不难，只要你的编码能遍历2^n/(n+1)，并且码间距离不小于3，就可以。方法就是如你所说，按编码表去对。

对对，不错，mac的分析有道理。我没有深入地从码间距离去思考，

关于开销的问题，其实Hamming Code的开销还是应该算是很小的，因为它的开销可以这么算：开销=n/2^n，当n比较大的时候，效率是很高的，接近100%。因为在实际中，通信中的误码通常是单比特误码，这种误码占总误码中90%以上，因此，纠错一般来说主要是应用于单比特错误。所以采用Hamming码可以得到很高的编码效率，例如，当我们设置20bit的纠错码时，可以用来为(2^20-20)bit信息位纠错。所以这么看来，效率还是很高的。

对于任意个人的Hat问题，实际上已经有人解决了这个问题，方法还是围绕着Hamming码的方法，只不过可能还进行了别的什么处理，我没有看到这方面的资料，只知道，可以它能达到的效率和Hamming是几乎一样的。详细还是请看我主页上的那篇文章。






没有完美的犯罪......

※来源: 【 推理之门 Tuili.Com 】.
第1页/共1页（总计9个回复）
每次上网自动访问推理之门   |    将推理之门加入收藏夹
邮件联系：zhejiong@126.com  沪ICP备2021006552号  沪公网安备31011502006128号  推理之门  版权所有 2000-2024