猜帽子难题
有n个人，2n-1个不同编号的帽子(号1至2n-1)，随机取n个帽子戴到n个人头上，每个人只能看到其他人的帽子编号，看不见自己编号和未分配帽子编号，现在要求每人独立猜自己帽子编号，整个猜过程中不得交流，所有人都不会知道别人猜的是什么编号，问是否存在一种策略保证至少有一个人能猜对？ 我们先看最简单的甲乙两人场景，假设红绿蓝三色帽子。我们用红绿代表甲红帽，乙绿帽的情况。
由于策略事先固定，双方都只能根据观察到对方的帽子颜色做出固定的选择。
于是对于红绿和蓝绿两个情况，甲必须做出统一的选择，
不妨设甲看到对方绿帽总是选择自己红帽，
于是为了覆盖蓝绿场景，那么乙看到对方带蓝帽必须猜测自己带绿帽；
由此蓝红场景，甲看到对方带红帽需要猜自己带蓝帽；
由此对于绿红场景，乙看到对方带绿帽必须猜自己红帽；
由此对于绿蓝场景，甲看到对方带蓝帽必须猜自己带绿帽；
由此对于红蓝场景，乙看到对方带红帽必须猜自己带蓝帽；
由此对于红绿场景，甲看到对方带绿帽猜自己戴红帽，达成双人方案。
这应该是一个图论问题 2n-1个数取n个数形成排列有P(2n-1,n).
题目相当于需要将这些排列平均分成n组，其中第k组所有排列去掉第k个元素正好形成2n-1个数取n-1个数的所有排列
页:
[1]