可用基本相同的方法。只要稍做变动即可 -------
首先,定义两个开关的4个状态依次为(比如):开开、开关、 关关、 关开;且周而
复始。这一点很重要,必须所有的囚徒在开会时记清楚这一点(状态顺序)。
新问题与老问题的关键差别在于:老问题中,明天被叫到的人清楚地知道自己是第
1人、充当自然的leader;新问题中,谁都不清楚自己是不是第1人。但这没关系,
这里不需要leader。
具体做法如下:www.ddhw.com
1) 不管是谁,第一次被叫去时,不管他见到的两个开关原来状态如何,他都把它们
变动到下一个状态;
2) 每个人都牢牢记住自己放的状态;
3) 每个人只是第一次被叫去时变动开关状态,之后再去就再也不能动了。
现举例说明,最后谁能“肯定地说所有的人都来过这个开关室了”:
假设两个开关初始状态是“ 关关”;第1个囚徒被叫去时,他把它们动到下一个状
态“关开”,(但当时他并不知道他是第1个被叫去的人!!);然后第2个,第3个,。。。。。
最后,当23人都去过至少一次后,变化过程如下:
关关(初始);
关开(1); 开开(2);开关(3); 关关(4);
关开(5); 开开(6);开关(7); 关关(8);
关开(9); 开开(10);开关(11); 关关(12);
关开(13); 开开(14);开关(15); 关关(16);
关开(17); 开开(18);开关(19); 关关(20);
关开(21); 开开(22);开关(23)www.ddhw.com
最后,两个开关就永远停留在“开关”状态上了。再等足够长的时间,当初被第1个
叫去的囚徒就可以figure out 所有的23人都被叫遍了。(只有到此时,他才知道他
当初是第1个被叫的)。他的根据是以下三点:
1) 监狱长说过:“虽然我叫人的方法是随机的,但任何人被叫到的机会均等,也
就是说,给定任何一个N,一定时间以后每个人都会被叫到N次以上” (这一点非
常重要,是关键);
2) 两个开关停留在一个状态上不再变了,且等了足够长的时间了(只要不怕老死在
监狱里,为保险起见,尽量多等一点时间);
3) 所停留的这个状态(“开关”)离他当初所置的状态(“关开”)从理论上恰好相
差23个变化(当然,他必须记住他当初放的状态是什么)。
其实,稍为冒险一点,其他囚徒也可宣布取胜(凭1、2两个根据)。但第1个囚徒宣布
更保险,因为他有1、2、3三个根据。
我觉得此法能work。不知有漏同否?请大家指教。等看fzy的标准答案。