前几天在博客堂(http://blog.joycode.com)的主页上看到一道非常有意思的题目。题目如下：
话说某个小岛上的居民有两个部落，一个部落的人只说真话，另一个的人有时候说真话，有时候说假话。（听上去很熟吧？）岛上的每个人都知道其他人的真实身份（怎么知道的？别问我，呵呵）
现在知道岛上共有2005人，真话部落比不一定部落的人多。如果你是岛上的新任总督，想搞清楚他们的身份，所以你需要从真话部落挑一个助手。于是你召开了第X届全体岛民大会，在会上你可以向任何人提问。请问你能不能在不超过4000次提问里找到一个助手？注意，一次提问是指问一个人，如果你问三个人同样的问题，算是三次提问，而且任何问题不得涉及1群人，比如你不能问“这100个人里最小的真话部落的人是谁”这类问题。
当时粗略思考了一下，这道题目的条件有个地方很不好把握，即有时说谎的人会不会在总督提问时故意全都说真话来混淆总督。如果真是这样，别说4000次提问，就是40000次都不一定能找到一个只讲真话的助手。而且，整道题目唯一可以确认的条件就是讲真话的人比有时说谎的人的数目多。
为了求解，只能把有时说谎的人设为随机状态，即有时说谎的人说谎的几率始终保持在1/2附近。Go on then……
先不考虑4000次提问的条件，我想了一个办法：每轮先从所有人中随机挑一个出来，然后向剩下的所有人提问，问本轮选中的人是讲真话还是讲假话，对答案进行统计。答案相同，人数少的一方肯定全都是有时讲假话的人。如果答案相同，人数多的一方回答本轮选中的人讲真话，则本轮选中的人必定是讲真话的人，助手找到，Bingo！！！否则，筛去本轮选中的人和人数少的一方，剩下的人进入下轮，循环继续……
按照这种方法，新任总督最后肯定能找到一个讲真话的助手。不过，这个方法花费的提问次数很可能超过4000次。那么，有没有优化这个苯算法的方法呢？仔细思考后，我找到了一个入手点，设每轮开始时的总人数是M，提问结束后，答案相同，人数少的一方的人数为N。则筛完本轮选中的人和人数少的一方后，再从剩下的人中随机去掉（N+1）人。此时，筛过２次剩下的人中，还是能确保讲真话的人数最多。这样，每轮结束后，提问范围都可以缩小为（M-2*N-2）。
下面算算优化后的有时说谎的人数较多(假设为最大1002人)，且每次选中的人都是有时讲真话有时讲假话的情况下，能不能满足最多4000次提问的题设。
第一轮：2005人中，除开中选者，有时说谎的人数是1001。结果2004次提问中有500人由于讲假话被筛，最后一共筛去1002人。取最坏情况，第二次筛去的501人全都讲真话；
第二轮：1003人中，除开中选者，有时说谎的人数是500。结果1002次提问中有250人由于讲假话被筛，最后一共筛去502人。取最坏情况，第二次筛去的251人全都讲真话；
第三轮：501人中，除开中选者，有时说谎的人数是249。结果500次提问中有124人由于讲假话被筛，最后一共筛去250人。取最坏情况，第二次筛去的125人全都讲真话；
第四轮：251人中，除开中选者，有时说谎的人数是124。结果250次提问中有62人由于讲假话被筛，最后一共筛去126人。取最坏情况，第二次筛去的63人全都讲真话；
第五轮：125人中，除开中选者，有时说谎的人数是61。结果124次提问中有30人由于讲假话被筛，最后一共筛去62人。取最坏情况，第二次筛去的31人全都讲真话；
第六轮：63人中，除开中选者，有时说谎的人数是30。结果62次提问中有15人由于讲假话被筛，最后一共筛去32人。取最坏情况，第二次筛去的16人全都讲真话；
第七轮：31人中，除开中选者，有时说谎的人数是14。结果30次提问中有7人由于讲假话被筛，最后一共筛去16人。取最坏情况，第二次筛去的8人全都讲真话；
第八轮：15人中，除开中选者，有时说谎的人数是6。结果14次提问中有3人由于讲假话被筛，最后一共筛去8人。取最坏情况，第二次筛去的4人全都讲真话；
第九轮：7人中，除开中选者，有时说谎的人数是2。结果6次提问中有1人由于讲假话被筛，最后一共筛去4人。取最坏情况，第二次筛去的2人全都讲真话；
第十轮：最后3人，其中一人有时讲真话有时讲假话，此时我们共耗去(2004+1002+500+250+124+62+30+14+6)3992次提问机会。最后的8次机会足够大家找出讲真话的助手吧^-^
上述方法在有时说谎的人数较多的情况下可行，那么是不是意味着在有时讲真话有时讲假话的人数较少时同样奏效呢？下面看看2005人中只有11人有时讲真话有时讲假话的极端情况(同样的，每次选中的人都是有时讲真话有时讲假话)：
第一轮：2005人中，除开中选者，有时说谎的人数是10。结果2004次提问中只有5人由于讲假话被筛，最后一共筛去12人。取最坏情况，第二次筛去的6人全都讲真话；
第二轮：1993人中，除开中选者，有时说谎的人数是4。结果1992次提问中只有2人由于讲假话被筛；
此时已花去4002次提问，超出题设要求。看来上述方法在这种情况下行不通。且慢，让我们留意一下每轮由于讲假话被删的人数和提问次数之间的比值先。
有时说谎的人数是1002人时，2004次提问中有500人露馅，而当这个人数下降到11人时，同样的2004次提问中只有5人露馅，这就是突破口。我们可以根据这个比值的范围来确定所有人当中，有时说谎的人数的大致范围，如果比值在1/4附近，则在保证讲真话的人数最多时，双方人数大致相当。那么，我们是不是根据这个比值设定一个系数x，让第二次筛掉(N+1)*x人呢？
请等一下，让我们逆转一下思维先。
由于先前假设的有时说谎的人说谎的几率始终保持在1/2附近，如果从露馅的人数N入手，可以肯定，隐藏在(M-N-1)的人群中，有时说谎的人数大致是N。那么，我们只要从剩下的(M-N-1)的人群中，随机抽出(2*N+1)人来。则在这个新抽选的人群中，一定可以保证讲真话的人比有时说谎的人多！！！
现在我们再看看2005人中只有11人有时说谎的情况下，采用抽选(2*N+1)的办法有没有效。
第一轮：2005人中，除开中选者，有时说谎的人数是10。结果2004次提问中只有5人由于讲假话被筛，我们从第一次筛选后的1999人中随机抽选11人；
第二轮：11人中，除开中选者，有时说谎的人数最多是4，此时只需10次提问即可。后面就不用分析了。
而有时说谎的人的人数最多的情况下和上面分析的结果完全相同，最坏情况下在九轮筛选后，花去3992次提问，可得到最终3选2的结果。至此，分析结束。最后总结一下，给出的最终解决方案如下：
在假定有时说谎的人说谎的几率始终保持在1/2附近的情况下，先从2005人中随机选1人，向剩下的2004人询问，选中的人是否有时说谎。如问完2004人后，回答“不是”的人过半，则选中者总是讲真话，助手找到。否则，设回答“不是”（即在本轮提问中说谎露馅）的人数为N，从回答“是”的人群中随机抽选出2*N+1人来。重复上面的操作，直至抽选出最后3人，或回答“不是”的人过半。
本文地址：http://com.8s8s.com/it/it32265.htm