以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆积木 - 能伸出桌面多远？。今天这次课，来自Aarhus的Peter Bro Miltersen讲了一个很有趣的游戏问题。
现在有100个箱子，有一个学生，一张写着他的名字的名片被放在某个随机选择的箱子里面。现在这个学生可以检查不超过一...

前两天贴出了一个硬币游戏，希望寻找一种胜利策略。这是一个非常有意思的题目，没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答，因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣，请飘至原问题。

的简单情形，
Tony Liu和overwindows已经给出了正确答案：

第一步：任一对角线翻转
第二步：任一条边翻转
第三步：...

Alice和Bob两人玩一种硬币游戏。游戏在一个的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一枚硬币，接着Bob可以选择将棋盘旋转90，180或者270度，也可以什么都不做。
游戏轮流进行直到棋盘上所有硬币都正面朝上或者反面朝上，Alice获得胜利。
如果Alice在游戏过程中无法看到棋盘上的银币，也不知道游戏刚开始的状...

珍爱生命，远离政治。今天我们讨论一个数学问题。
这个问题的一个基本版本是说，有N架完全相同的飞机停留在一个机场，每一架最多装的油可以支持飞机飞行1个单位距离，飞机能够瞬时转弯，同时可以瞬时在空中互相加油。问如果要求所有起飞的飞机都安全返回机场的话，最多可以把一架飞机送出去多远距离。
解答来自胖头王：

今天吃饭跟同学聊起来之...

Yao在课程《理论计算机II》的第一节课上提到的一个问题：
三个人如何平分一块蛋糕？
要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自己拿到的蛋糕价值不少于整块蛋糕的1/3，而每个人对于蛋糕的不同区域的价值认识可能不同（即并不完全等价于面积）。
方法最好可以推广到n个人的情形。

课上讲了一种方法：
任选一个人，在蛋糕上缓...

我很早之前就想过这个问题，但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想一想。
岛国上流行一种极易接触传染的病一旦染上该病1月后病发身亡但该病可通外科手术治愈
岛上每个人都有已被传染的可能国王怀疑自己得了该病在该岛上找到了医术最高名的3个医生并要求这3个医生在当天轮流...

这个题目听说是MSRA的面试题。
在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色，可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人，可以看到其他人的帽子颜色，但不知道自己的帽子颜色。每个游戏...

在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色，可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人，可以看到其他人的帽子颜色，但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。...

Theorem: Any protocol of date problem has success probability less than which is about . Here is the biggest number such that .
Proof: First, let's introduce some notation. is the set of permutations of .
For any two permutations and , we say if and fit with the first [...]

题外话：最近阅微堂发的都是网友转发的政治方面的文章，不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题，已经被研究了很多年，有许多不同形式的阐述方式和变种，应用范围也很广。下面应该是比较吸引人和简单的那种，来自姚期智教授的理论计算机（I）的授课内容——我是其助教之一。

现假设你在PIE上征友，或者以其它方式，选定了某些约会对...