- (1)其实很简单, 只要指定一个“counter”就可以了。只有这个“counter”可以关灯。对于其余的囚犯,他们把灯打开当且仅当灯是关的,并且自己之前没有打开过灯。这样每一次counter关灯,他就知道有一个囚犯被审讯过了。
这种情况下expected days till freedom=n(n-1)+n*H_(n-1)=O(n^2),此处H_i是第i个Harmonic number.
(2)只要对(1)稍加改进就可以了。
如果你是counter:如果灯是开着的,把灯关掉。
如果你不是counter:如果灯开着,什么也不做。如果灯关着,开灯当且仅当你之前开过0-1次灯。
这样当counter数到200次的时候,他就可以说所有人都已经被审讯过了。因为当灯本身是开着的,这200次里有199次是犯人们打开的,能够保证所有人都已经被审讯过。如果灯本身是关着的,这200次都是犯人打开的。
(3)我认为这一问比较奇怪,在我看来唯一影响的factor就是if prisoners will be able to tell days。目前我所知最好的algorithm是 with complexity O(n*(logn)^2),与审讯的模式无关。
2.这是一个很经典的问题。这个问题其实是一个counting问题。
Def:A permutation of a set X is a bijection p:X->X.
Prop:For a finite set X with cardinality n,the collection of permutations S_X form a group under ordinary function composition. Moreover, S_X is isomorphic to the symmetric group S_n.
我们只需考虑箱子的编号构成的排列。注意到每一个这样的排列都是S_n的一个元素。
策略:对于每一个囚犯,他进入后首先打开写有自己编号的箱子,而后每次他都打开编号为自己之前打开箱子中数字的箱子,知道他成功找到自己的箱子或50次用完。
这个策略是基于一个trivial的定理:
Thm:each permutation p in S_n can be written as a product of disjoint cycles.
每个人要做的,就是找到自己的cycle然后走下去,这个方法能成功当且仅当最长的cycle的长度<=50,因为如此他就可以完成cycle,找到自己的编号。所以要计算这种方法的成功率,我们只需count满足条件的permutation即可。
counting很简单,对于每一个k>=51,如果有一个cycle of length k,那么这个cycle必须是最大的,而且各个case之间是exclusive的。
For each k,P(contains cycle of length k)=Binomial(100,k) *(k-1)! *(100-k)!/100!=1/k.
Hence P=1-sum(i=51,100)1/k which is approximately 0.3.
0.3应该是目前所知最好的结果。
3.这是一个非常tedious的问题,我无法找到efficient algorithm,在此贴上solution by Chris Lomont,Gene Foulk &Casey Hart.
这种策略在只有100人的情况下,极有可能第一部分就要花掉远超宇宙寿命的时间。并且要假设这些mathematicians记忆力惊人(比如能准确地记住十亿天前发生了什么)。
第一部分:bounding n
这一部分分为k轮,第i轮(1<=i<=k)将花掉2^i+1天,k将在过程中决定。
一开始,只有chosen拥有“标记”,在每轮的第一天,所有拥有标记的人打开开关,所有看到亮光的人也拥有标记,标记一旦拥有就一直持续(自己记住)。注意如果有未被标记的人,这一天一定至少有一个新的人被标记,并且被标记者最多变成原来的2倍(根据warden分配牢房的情况)。在此轮剩下的天数中,未被标记者即使看到灯光也不标记自己,而被标记者坚持每晚开灯,直到某晚他自己房间的灯未开。根据以上讨论,第i轮中,最多2^i人被标记,并且如果有人未被标记,第二天开始每天开灯的人将会减少,因此经过2^i天后,如果有人未被标记,所有人都不会接受到灯光。
每一轮被标记的人数都会增加。因此经过有限轮后(不妨设为k轮),2^k晚经过,所有人仍接受到灯光,这说明在第一天的标记阶段,所有人都被标记,从这轮中所有人都会知道人数n在区间[k+1,2^k]中。
(还有很长很长,有时间补上,or not)
4.这是一个代数背景较深的问题,但是只描述解法的话中学生也能理解。
要想确定一个entry在8*8matrix中的位置,我们需要row index和coloum index。在这里只给出row index的寻找方法,column同理,并且两者相互独立。
我们来看1*8case。注意在二进制下,我们只需3个word就能确定1-8中任意一个数(写成二进制,只有3位)。对棋盘进行如下独立的3次染色:
AAAABBBB,AABBAABB,ABABABAB。
对于要猜“魔法方格”的人,他要做的是数3次数:第一次,染色棋盘AAAABBBB,数B色方格上heads的个数,奇数记4,偶数记0.
第二次,染色AABBAABB,同样数B中heads的个数,奇数记2,偶数记0.
第三次,染色ABABABAB,数B中heads的个数,奇数记1,偶数记0.
只要将3次所得数字加起来,就是魔法方格的row index(0=8)。
为了说明可行性,我们必须证明第一个囚犯一定能够在只翻转一枚硬币的情况下,让正确的组合在3种颜色中都出现。
但这是trivial的,因为初始状态只有8种可能:全部正确,第一种染色错误,第二种染色错误,第三种染色错误,第一二种染色错误,第一三种染色错误,第二三种染色错误,全部错误。
对于这八种情况,第一个人只需翻动如下列数的硬币即可:1,5,3,2,7,6,4,8.
所以翻动一枚硬币可以帮助第二个人确定行数,而这枚硬币拥有degree of freedom 1(即可以在一列上随便移动),所以同样的我们可以让这枚硬币来确定列数。
这个问题的背景可以追溯到non-free module on a commutative ring的性质。