主题：来看看!

[转帖]100囚徒难题

有100个无期 叫 囚徒，被关在100个独立的小房间，互相无法通信。 每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。 放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每 个人除非出来防风，是看不到这个灯的。 一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表 示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未 被放过风，那么所有的囚徒一起处死！ 囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？ 这个问题是著名的谜题之一，如果大家认为自己找到了方法，再仔细想想，有没有效率 更高的？

有点意思哟

灯只有开和关。所以应该考虑一下二进制的方法吧

既然是随机放风，那么可以假设：时间足够长的话，每个囚徒都可以被放风多次。

Ti表示第 i 天被放风的人

囚徒们可以这样做：

第一天，T1将灯打开。

第二天，如果T2是第一次被放风，即T2，T1不是一个人，那么，T2仍使灯保持开的。

第三天，如果T3是第一次被放风，那么灯打开。

……………………………………………………………… ……

第101天，T101走进灯，看到灯亮着。所以，在1到100天，每个囚徒都被不重复的放风一次。他就可以宣布：所有囚徒都被放风过。100天中没有出现任何异常情况。

如果在某天，比如第45天，T45走来，他已经被放过风了。那么T45把灯关了。

并且我们以后一切行动都要以T45为准，因为只有他才知道，44个人被放过风了。我们把他称为首领。

第46天，囚徒看到灯关了，知道出现异常情况。按大会的指示，他要保持灯关着。

一直到101天，T101看到的是关的灯，所以不会做任何宣布，仍旧把灯关了。我们把所有人分两类：S1被放过风，并且首领也知道他被放过风；S2没被放过风，或者首领不确定他是不是被放过风。

由于T101没有宣布，大家都知道出现异常，而且在T1到T100所有人中，看到灯开的都知道首领已把他划到S1中，而看到灯关的，知道自己属于S2，没被放风的也属于S2。

T102如果属于S1，就保持灯关；如果属于S2，就把灯打开。关掉灯后，按大会指示，他把自己划到S1中。T103如果看到灯关，就要考虑自己：如果属于S1，就保持灯关，如果属于S2，就打开灯，并且把自己划到S1中。T103如果看到灯开，不管自己属于哪个集合，都保持灯开，自己仍属于原来的集合。

日子一天天过去，首领又被放风了。他如果看到灯开，知道又有一个属于S2的被放风，他就把这位划在S1中。S1又多了一个人。他要把灯关掉，等待另一个S2中人的到来。如果他看到灯关，他知道从45天到现在，来到灯前的人，都属于S1，自己已经记过数了，于是他保持灯关，希望下次来时灯开。

在比较理想的情况下，首领每被放风一次，S1加1，S1不断变大

终于有一天，首领看到灯开，此时S1已经达到99，而S1又要加1，变成100。于是，他可以宣布：所有人都被放风了。