趣题：寻找策略使得总有一人猜出他背上的数
正在上虚词研究课，好友Chain发来短信说，北大BBS化学学院版上发了一道很有趣的谜题(http://bdwm.net/bbs/bbstcon.php?board=CCME&threadid=2334788)，已经上十大热门话题第三了。我也是第一次看到这个题目，和大家分享一下。
话说周一某实验室有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时，只需其中一个人报和对方一样的数，另一个人报和对方不一样的数即可。
一些类似的趣题：
湘公网安备 43102202000103号