生肖迷宫吧 关注:826贴子:12,983
  • 6回复贴,共1

鸟屎问题的最初版本是有解的(附解法)

只看楼主收藏回复

鸟屎问题原始版:
有6个学生骑车郊游,天上飞过若干只大雁,在同学们头上留下若干滩鸟粪,他们可以看到别人头上的鸟粪,看不到自己头上的。
他们来到西瓜摊,卖西瓜的说:你们每个人头上有1到9滩鸟粪,【并且有两人粪数相同】,你们每个人猜你们头上总共多少滩鸟粪,分别悄悄告诉我,有一个猜对了我就请你们吃西瓜。幸好这些同学以前曾经商量过对策,你说他们应该如何猜呢?
http://tieba.baidu.com/p/557183584?pn=1 1楼)
作者在2009-07-02说这个问题无解(参见同贴 37楼)。但是之前32楼的吧友已经给出了这个问题的对策。经检查他的方法并没有错误。下面我给出一个比较完整的解答。


IP属地:湖北1楼2012-10-08 19:34回复
    关键在于构造一个从5数字组合到4数字组合的一一对应F,使每个4数组合包含在相应的5数组合之中。这种映射已经有人作出了(如 http://tieba.baidu.com/p/557183584?pn=1 32楼),这里不讨论了。
    策略:
    6个人中的每个人,都使用相同的策略,根据其他的5个数猜自己头上的数。这个策略是:
    1、如果他看到的5个数没有重复,则通过F产生其中4个数,然后报出剩下的那个数。
    2、如果他看到的5个数中有两个相同,则找到4个不同的数,通过F的逆映射F’产生5个数,和原来4个数比较,报出多出来的那个数。
    证明:
    设6个人为A1,A2,B,C,D,E,A1和A2头上的数相同。共有5个不同的数abcde,通过F映射为4个不同的数,可能出现下面几种情况:
    1)F(abcde)=bcde。A1看到5个数为abcde,根据策略1,生成bcde,猜剩下的数a。因此A1猜对。同理A2也将猜对。
    2)F(abcde)=abcd. E看到的数是aabcd,他会选策略2,猜e,因此E猜对。
    3)其他3种情况下,与情况2同理,分别是B、C、D猜对。
    即任何情况下,都至少有一人猜对。因此这个策略符合题目要求。


    IP属地:湖北2楼2012-10-08 20:23
    回复
      2026-01-26 03:15:12
      广告
      不感兴趣
      开通SVIP免广告
      这题其实是把“不可重复的组合”推广为“可以重复的组合”。从【有一对重复的6-组合的全体】一一对应到【无重复或有一对重复的5-组合的全体】,每对对应必须满足包含关系。


      IP属地:湖北3楼2012-10-08 20:36
      回复
        吧友118.249.184.* 在2009-04-20 就想到并且明白了这个策略。参见
        http://tieba.baidu.com/p/557183584?pn=2 第32楼。


        IP属地:湖北4楼2012-10-08 20:39
        回复
          确实有解、以前解出过、我是利用图形理解


          来自手机贴吧5楼2012-10-09 06:38
          回复
            这个题目生肖大哥早就知道有解了,只是他没有继续更新旧帖而已。
            <第一题>
            九个连续的数字分给五个人,每人分到一个不同的数字,剩下四个数字不用。
            所有人看得见其他四个人的数字、但看不见自己的数字。
            在分配数字之前,五个人可以商讨一个策略,保证至少有一个人能够猜对自己的数字。
            分配数字之后,所有人就不可以再交流了,就连猜自己数字的时候也是一起公布答案--不能参考别人的答案。
            请问这五个人应该用甚麼策略?
            <第一答>
            每一个人都看到四个不同的数字、而同时每一个人都有五个未知的数字要猜。
            每一个人把自己看到的四个数字相加之后,还需要再加上x才能被五整除。。。每个人的x值未必相同,x∈{0,1,2,3,4}。
            每一个人在未知的五个数字当中,猜第x+1个数,就成了。
            第一题结束。
            <第二题>
            承第一题,仍是九个数字,但有六个人,其中有两个人(不确定是谁)会被分配到同一个数字,其余条件与第一题完全相同,请问要怎麼猜?
            <第一答>
            有四个人会看到重复的数字,请忽略重复的数字,直接套用第一题的”五人猜九数”,这一边不用解释。
            有两个人会看到五个已知数。。。此时这两个人先不要管自己的数字是甚麼,而是将看到五个已知数逐一带入”五人猜九数”的系统中去运算,这样就会知道”哪一个数字会被猜对、而哪四个数字会被猜错”--最后再假设自己头上的数字就是”会被猜对的那一个数字”即可。
            如此一来,如果”会被猜对的数字”在前四个人的头上,那麼前四个人可以用”五人猜九数”的方法猜对;如果”会被猜对的数字”在重复的两人头上,那麼那两个人也会猜对。
            第二题结束。


            6楼2012-10-12 06:41
            回复
              楼上比我证明里说得清楚。其实取余数法是建立4和5两种组合之间的映射的一种方法,但也有其他方法能建立这个映射(和余数法一样适用任何2n+1,但不用到整数的运算)。


              IP属地:湖北7楼2012-10-12 11:15
              回复