之所以写下这个题目,是因为我时常浏览 Springer 出版的杂志
Mathematical Intelligencer,觉得其中有很多有意思的东西,
值得大家去读一读,也适合拿到这里来讨论。这个事情,偶尔为之,
意义也不大;我打算长期坚持下去。这次起个头,是为第一章。
(顺带说一句,这份杂志,在数学学院图书馆有最近的几期,大家
可以闲时去翻翻。可惜的是没有电子版。)
今天中午,翻看的是2002年秋季的一期,游戏数学专栏。作者说,
许多数学游戏和谜题,都喜欢拿帽子来作为道具。这次的游戏呢,
也是这样,早两年在美国的数学圈子里风行一时,甚至于纽约时报
也为此专门写了篇报道,题目是---
Why Mathematicians Now Care About Their Hat Color?
这篇文章的网址是
http://www.msri.org/activities/jir/sarar/010410NYTArticle.html
可以访问国外网址的同学,自己去看吧,我就不侵犯版权了。:)
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。
规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。
游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种
颜色,可以认为它们在我们各自头上的分布是临时随机决定的。
小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己
的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们
各人面前有三个按钮,可以选择“黑色”“白色”或“弃权”(也
就是 pass,不作猜测的意思)。小组成员彼此之间没有任何信息
交流,他们必须各自独立地作出自己的选择,并且谁也不知道其
他人的选择。如果小组成员全部选择了 pass,也就是每个人都
弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个
人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每
个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
这个游戏还有最关键的一点:在游戏开始前(帽子戴上之前),有
一个“协商时间”,小组成员可以聚在一起,讨论决定小组应采取
什么样的策略。但这个交流过程在游戏开始时自然终止。
现在的问题是:小组选择什么样的策略,才有最大的机会获胜呢?
首先可以肯定,这个最佳策略的获胜概率,肯定不会只是1/2^n。
容易找到获胜概率为1/2 的策略,但是不是就没有更狡猾的办法
了呢?
如果一般情况太难,不妨先想想 n=3 的情形。
=================================
注记和问题:
一,我们看到,原问题可以被归结为一个编码问题:在长度为n,各位取0或1的符码中,取尽量少的字码集合,使得对于任一字码,此集合中都存在一字码,其距离小于或等于1。一般地,距离“1”可以改为其它步长。这类问题称为 covering code problem,是目前一个比较活跃的研究领域。
二,根据上一次的分析,由于每个顶点只有n个相邻顶点,因此每个半径为1的单位球只能覆盖 n+1 个顶点。为了用覆盖所有顶点,必须有至少 2^n/(n+1)个这样的球;或者说至少有2^n/(n+1) 个顶点。这个上界称为 sphere packingbound。达到此上界的方案称为 hamming code。可以看到,此上界仅当 n+1=2^k时才可能达到。这个条件不但必要,也是充分的。对应的设计方案非常简单而巧妙,与博弈论中的 Nim(音译为“匿门”,是德语中的“拿”的意思,来自于取火柴的游戏)游戏有异曲同工之妙,同样利用了二进制表示。自然,对应的策略也是最优的。不但如此,对于 n=2^k 的情形,如果采用 dump 策略,即其中一人被假定为不存在,而对剩下的 2^k-1 个顶点应用上面所说的策略,则可证明这同样是最优的。
三,一般情形,这个估计不是最优的。在 n=9 或者更大的情形,就已经不知道最佳策略和最佳估计为什么。换句话说,这个领域中相当大一部分依然是 open 的。(对于n分别为3,4,5,6,7,8 的情形,所取的最优覆盖分别要用2,4,7,12,16,32 个单位球。)