趣题:寻找策略使得总有一人猜出他背上的数

正在上虚词研究课,好友Chain发来短信说,北大BBS化学学院版上发了一道很有趣的谜题,已经上十大热门话题第三了。我也是第一次看到这个题目,和大家分享一下。

话说周一某实验室有16名同学,有一天*老师把大家叫到一起说:下周来做实验的时候,我会给你们每个人背后贴一张纸,纸上的数字从1到16都有可能,不同同学背后的数字可以重复。你们每个人可以看到别人背上的数字,但不能看到自己的数字。贴纸之后你们之间不允许进行任何形式的沟通交流。之后你们排队依次来D***,告诉我你自己背后的数字是多少;由于D***室隔音效果很好,室外的人不能听到室内的同学的说话声(更好的说法是,每个人独自在一张小纸条上写下猜测结果,这就避免了可能由排队猜数的时间和顺序带来的“交流”)。等到16名同学都猜完之后公布结果。只要你们16个人中间能有一个人猜对自己背后的数字,我会让大家都得满分;但如果你们都没有猜对自己背后的数字的话,则你们全部都要重修有机实验。那么你要怎样做才能避免挂科的命运呢?

这道题目很有意思,看答案之前不妨自己先想一下。
提示:先从两个人的情况开始想起。

答案:为了下面叙述的简便,我们把数字1到16简单地替换为0到15。游戏前,大家按某种顺序给所有人从0到15依次编号。游戏开始后,每个人把自己能看到的15个数与自己的编号一起异或起来(按位异或),在猜数时报出这个异或的结果。这个方案能保证总有一个人恰好报出自己的数。假设这16个数异或起来的结果为X(显然0 ≤ X ≤ 15),第i个人身上的数记为A_i,那么他猜的数其实就是X xor A_i xor i。那么,编号为X的人(此时i=X)报出的数恰好就是他背上的那个数。对于数字1到16的情况,只需要在计算前后减一加一即可。
这个问题可以从n=2的情形很快入手。当n=2时,只需其中一个人报和对方一样的数,另一个人报和对方不一样的数即可。

一些类似的趣题:
http://www.matrix67.com/blog/archives/456
http://www.matrix67.com/blog/archives/511

35 条评论

  • 风不流

    sf,不过这个题……
    好像只有蒙了。

  • 风不流

    几率都是1/16,身为一个厚道人,我还是祝福这帮孩子们吧。

  • J

    应该是大家进去前先想好一个策略吧,可究竟是什么策略呢~~~~

  • 猛犸也钻地

    蒙一个
    16 – 和 mod 16

  • jayhaizeizai

    从1说到16
    按顺序来

  • danaan

    说出自己看到最多的数吧

  • NULL

    说实话答案没看懂……

  • menie

    xor果然是个神奇的东西。。我感觉关键在于X xor A_i这个值可以自己得到,而X为定值且是1到16之间的整数,那么大家每人都试一个数就有一个出结果的了。。
    不过想两个人的情况对一般性的情况没有太大帮助啊,对于两个人的情况很好解释:如果我猜对方的数字结果不对的话(我的数字不是对方的那个数字),对方不猜我的数字就一定对了。

  • Fox

    是不是排队顺序上做文章?

  • Fox

    答案太强了……看了你的几篇日志发现2进制才是王道阿!

  • 风不流

    你这个说法好像复杂了。
    这么理解起来,还是要大家制定一个规则,共同遵守。如果可以共同遵守一个规则,何不每个人都报自己的编号,总有一个可以答对。
    当然,你研究的是数学,我研究的是……是什么呢,我也不知道。

  • yy

    xor不是作用于二进制吗,如果作用于十进制,运算规则是如何的?
    如果转化为二进制的话,1 xor 2就是3了。

  • 严酷的魔王

    To LS:“每个人都报自己的编号,总有一个可以答对。”

    这个怎么实现啊……号码是可以重复的,而且如果都已经知道自己背后是什么数了那么……

  • K.F.Storm

    To 12楼
    0到15之间不论怎么异或都是4位二进制之间的运算,不可能算出5位二进制数的。这道题的人数只能是2的整数次幂。

  • Chain

    那门课的助教给了一个很简洁的解法,在ccme版。你的帖好像被删了。

  • 风不流

    to 14楼,是我一时冲动,理解失误。
    无知了,你别跟着错下去,啊哈哈。

  • Mgccl

    似乎还有一个方法…
    自己看到的其他人背上的号码加起来,mod 16,然后告诉老师

  • skkd

    把人按0到15编号,然后每个人把其他人背后的号码加起来模16得到x,然后每个人报数字y使得x+y模16等于他自己的编号。这样假设所有号码加起来模16等于a,那么对于编号为a背后号码为b的人,她的x是一个和16+a-b对16同模的数,这样我们已知y+16+a-b和a对16同模,则y和b对16同模。也就是说这个编号为a的人必然可以答对。

    事实上有如下结论:如果有N个人参与游戏,有X个数字,那么至少可以保证有floor(N/X)个人猜对,而且不可能再更多。

  • kdboy

    不同同学背后的数字可以重复。
    这样,1-16可能有部分数字是丢掉了。
    重复的数字+丢失的数字,异或结果肯定有偏差的吧。

  • horieyui

    《算法艺术与信息学竞赛》P20,【例题3】聪明的学生……

  • gnaggnoyil

    to 12L:显然是位运算…

  • 仙雾

    18l说的好

  • Shadow_Swirl

    想起了sawII还是III里有个密室。。。on the back of your mind

  • ykzls

    我重装电脑后就失去了你的一切消息,百度和谷歌上都找不到.
    今天,我又回来了.

  • 6V

    不太理解异或的意思……我是无知阶级的,望赐教……

  • 6V

    麻烦举个例子吧,比如说三个人的时候,编号0,1,2,那么这个1号的怎么跟那两个贴纸一起异或起来?加起来求余数?
    PS:我没接触过奥数,只是为应付高考而学,但是对于数学我是有一点点兴趣的,望赐教~

  • Ernest

    没有必要用XOR。
    假设n个同学,0~(n-1),数字也是0~(n-1)。
    设U=A0+A1+…+A(n-1)。(mod n,下同)
    每个人看到其余所有人的数字和就分别是:
    U-A0,U-A1,U-A2,…,U-A(n-1)。
    各自分别用0,1,2,…,(n-1)减去那个数,分别得到:
    B0=A0+(0-U),B1=A1+(1-U),…,B(n-1)=A(n-1)+(n-1-U)
    由于U mod n肯定在0,1,…,n-1当中的某一个,
    所以B(U mod n)=A(U mod n)。

    不用XOR。不用考虑人数限制。计算起来也方便。

  • 排队就行了,插队的人以为自己最大,插队的总是让自己前面的人重新排队。
    A和B先排好队,C来插队(C已看到B>A),插队的只看B不是16,就排在B后面,B重新排队,如果C不是16,就排在C后面,这一步时,B和C都知道自己不是16了。
    因为B站在了C前面,C再排队,已知B和C都不是16,B不是15,就排B后面,B又被重新排队。。。。。。直到ABC正确排好队,然后D来排队。。。。

  • rmy

    不需要这么麻烦,只要让第i个人假设(所有人背后的数码和) 和 i mod16 同余 即可 ,那么就可以推出自己的数码 ,然而显然有一个是对的

发表评论




Enter Captcha Here :