//此题出处为2007年日本数学奥林匹克预选赛压轴题。本人手译,可能有翻译瑕疵存在还望指正,这题觉得蛮有意思,但没太看明白并且鬼子没给附答案,故分享给高手前辈们给予解答。//
题目:
一个没有名字的村庄中住着2007位村民。你作为守护这个村庄的神,想要让村民们为自己的村庄起一个名字。于是每位村民都想好了一个村庄名称的提案。
每位村民每天都可以给村里面的其他任何人(也可以给自己)写任意封信。所有信件在每天傍晚集中收取,第二天早上再集中发给收件人。在送达信件的同时,邮递员会向收件人口头转达所有发信人的名字。每位村民只有一次机会给神(也就是你)写信提交村庄名字的提案。当然,提交的提案不必与自己最初设想或是其他村民的最初设想一致。村民们除了写信,不做任何能够交换信息的行为。
全部村民可以分为“老实人”和“大骗子”两类。村民们和你自己都不知道整个村民群体中谁是哪一类人,你只知道“大骗子”的人数在某个整数T以下(包括该数),并且村庄里至少有一个“老实人”。
你在某一天中午可以对村民下一次指示。“老实人”会听从你的指示,“大骗子”不一定听从你的指示。
问:求使得满足以下条件的指示存在的T的最大值。
·最后所有的“老实人”都给你写了信,并且所有的“老实人”的提案都是一致的。
·如果一开始所有的“老实人”的提案都一致的话,那么这个提案会被作为提交给你的提案。