2009-04-21 17:15| 
32 Comments | 本文内容遵从正在上虚词研究课，好友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
sf，不过这个题……
好像只有蒙了。
几率都是1/16，身为一个厚道人，我还是祝福这帮孩子们吧。
应该是大家进去前先想好一个策略吧，可究竟是什么策略呢~~~~
蒙一个
16 - 和 mod 16
从1说到16
按顺序来
说出自己看到最多的数吧
说实话答案没看懂……
xor果然是个神奇的东西。。我感觉关键在于X xor A_i这个值可以自己得到，而X为定值且是1到16之间的整数，那么大家每人都试一个数就有一个出结果的了。。
不过想两个人的情况对一般性的情况没有太大帮助啊，对于两个人的情况很好解释：如果我猜对方的数字结果不对的话（我的数字不是对方的那个数字），对方不猜我的数字就一定对了。
是不是排队顺序上做文章？
答案太强了……看了你的几篇日志发现2进制才是王道阿！
你这个说法好像复杂了。
这么理解起来，还是要大家制定一个规则，共同遵守。如果可以共同遵守一个规则，何不每个人都报自己的编号，总有一个可以答对。
当然，你研究的是数学，我研究的是……是什么呢，我也不知道。
xor不是作用于二进制吗，如果作用于十进制，运算规则是如何的？
如果转化为二进制的话，1 xor 2就是3了。
To LS：“每个人都报自己的编号，总有一个可以答对。”
这个怎么实现啊……号码是可以重复的，而且如果都已经知道自己背后是什么数了那么……
To 12楼
0到15之间不论怎么异或都是4位二进制之间的运算，不可能算出5位二进制数的。这道题的人数只能是2的整数次幂。
那门课的助教给了一个很简洁的解法，在ccme版。你的帖好像被删了。
to 14楼,是我一时冲动，理解失误。
无知了，你别跟着错下去，啊哈哈。
似乎还有一个方法...
自己看到的其他人背上的号码加起来,mod 16,然后告诉老师
把人按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)个人猜对，而且不可能再更多。
不同同学背后的数字可以重复。
这样，1-16可能有部分数字是丢掉了。
重复的数字+丢失的数字，异或结果肯定有偏差的吧。
《算法艺术与信息学竞赛》P20，【例题3】聪明的学生……
to 12L:显然是位运算...
18l说的好
HEY!SEE!~~~~U MAY LIKE IT~~~GA
http://hi.baidu.com/madesign/blog/item/ba20b899f0c437006e068cb6.html
Orz XOR运算...
想起了sawII还是III里有个密室。。。on the back of your mind
我重装电脑后就失去了你的一切消息,百度和谷歌上都找不到.
今天,我又回来了.
quote:
http://flyink.ycool.com/post.3309220.html
不太理解异或的意思……我是无知阶级的，望赐教……
麻烦举个例子吧，比如说三个人的时候，编号0，1，2，那么这个1号的怎么跟那两个贴纸一起异或起来？加起来求余数？
PS：我没接触过奥数，只是为应付高考而学，但是对于数学我是有一点点兴趣的，望赐教~
[...] 看完题我马上想到了M67上的一篇类似的问题，题目的文法基本相同，不同是的他那是16个人的情形。当时研究了半天，加上当时急于求成的心理，楞没想出来。。后来研究了半天，查了些资料，以一种更容易理解的方式把这道题的解法说一遍吧。 [...]
[...] 看完题我马上想到了M67上的一篇类似的问题，题目的文法基本相同，不同是的他那是16个人的情形。当时研究了半天，加上当时急于求成的心理，楞没想出来。。后来研究了半天，查了些资料，以一种更容易理解的方式把这道题的解法说一遍吧。 [...]
[...] 看完题我马上想到了M67上的一篇类似的问题，题目的文法基本相同，不同是的他那是16个人的情形。当时研究了半天，加上当时急于求成的心理，楞没想出来。。后来研究了半天，查了些资料，以一种更容易理解的方式把这道题的解法说一遍吧。 [...]