摸箱子问题以及应用

作者: , 共 1589 字

以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的 overhang 堆积木 - 能伸出桌面多远? 。今天这次课,来自 Aarhus 的 Peter Bro Miltersen 讲了一个很有趣的游戏问题。

现在有 100 个箱子,有一个学生,一张写着他的名字的名片被放在某个随机选择的箱子里面。现在这个学生可以检查不超过一半也就是 50 个箱子,希望能够把它的名字找出来。

很显然,这个学生没有什么好的方法,随机选择 50 个箱子打开,有一半的概率可以发现含有它的名字纸条的箱子。

OK ,现在还是 100 个箱子,但是有 100 个学生,写着这些学生的名字的 100 张纸条随机放入 100 个箱子里 ( 每个箱子恰好一张纸条 )。现在每个学生可以检查不超过一半也就是 50 个箱子,每个学生希望能找到含有自己名字的箱子。如果在游戏中,所有学生都是独立的(他们不能互相讨论以及看到其他人的开箱结果),问所有学生都实现目标的概率有多大?

如果把每个学生的结果认为是独立的,那么成功的概率只有 \( 2^{-100}\) ,但其实我们可以做的比这要好得多。事实上,让每个学生都找到含有自己名字的箱子的概率可以高达 0.3。

假设学生的名字就是它的编号,从 1 到 100。第 \( i\) 个箱子里的编号是 \( \pi(i)\) 。第 \( i\) 个学生这样做:先打开第 \( i\) 个箱子,再打开第 \( \pi(i)\) 个箱子,再打开第 \( \pi(\pi(i))\) 个箱子,以此继续下去,直到发现写着自己名字(也就是 \( i\) )的纸条或者打开箱子数到达 50 个为止。

那么当且仅当在 \( i\)\( \pi(i)\) 这个置换中含有长度超过 50 的圈时,有学生找不到含有自己名字的箱子。这个概率是 \( \sum_{j=51}^{100}1/j \sim \ln 2\) (注意一个随机置换里含有一个长度为 \( j\) 的圈的概率为 \( 1/j\) )。

所以上面策略的成功概率为 \( 1-\ln 2 \sim 0.3\)

类似于以前提到的 帽子游戏一 以及 帽子游戏二 ,我们要最大化一个团体都成功的概率,但是每个单个个体成功的概率又是一定的,那么我们只需要设计策略时,让大家要么几乎同时成功,要么几乎同时失败。就像上面的策略里,如果有人失败,意味着排列中有一个长度很大(大于 n/2 )的圈,这个圈上所有人同时也会失败,通过把失败的实例重合到一起,这样就提高了总体成功的概率。

上面这个问题不是孤立的,它可以应用在 static data structure problems 的下界证明上。对于后面这个问题,在最近是一个很热门的研究领域,但在这里写了也没人看,知道这个问题的也不需要看,所以我只提一下我们还可以做什么,下面是一个 open problem ,可以直接得出一个 data structure 问题的一个下界,是一个可以写学术论文的题目:

Open problem :假设现在有 \( 2n\) 个箱子, \( n\) 个学生,学生们的名字纸条被放入随机选中的 \( n\) 个箱子里。现在每个学生可以检查不超过一半也就是 \( n\) 个箱子,以找到含有自己名字的箱子。问这时候学生可以采取什么样的策略最大化所有学生都成功找到含有自己名字的箱子的概率。

期望结果:证明指数级小的下界或者找到常数概率的策略。

有兴趣的可以参考 The cell probe complexity of succinct data structures .

Q. E. D.

类似文章:
数学 » 搞笑, 数学之美
来自 University of WarwickMike Paterson 星期二在 Yao 的理论计算机课堂上给了一个非常有趣的小讲座。
相似度: 0.118
这个题目听说是 MSRA 的面试题。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」( 也就是 pass ,不作猜测的意思 )。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
理论计算机 (I) 课上讲的一个问题,很有意思。
相似度: 0.078
注:此游戏很有名,有同学问我其算法,我在网上找了一下,居然没多少中文资料,这里按照以前看过的一份答案回忆整理贴出。
碎碎念 » 北大
大家快来 orz 一下这个新出的北大精神。话说当年我也在此食堂站着吃过饭,没想到四年过去还是这样。
值得最近找工作的人好好读读,虽然可能有点晚了 :)