m*********y
发帖数: 127 | 1 莫斯科竞赛中有这样一道题：阿里巴巴试图潜入山洞。在山洞入口处有一面鼓。鼓的侧
面有四个一模一样的小孔，组成正方形的四个顶点。在每个孔的里面各装有一个开关。
开关有“上”“下”两种状态。(注意：眼睛看不见！)如果四个开关的状态全都一致，
洞门即可打开。现允许将手指伸入任意两个孔，触摸开关以了解其状态，并可随自己的
意改变或不改变其状态。但每当这样做了之后，鼓就要飞快地旋转，以至在停转之后无
法确认刚才触动了哪些开关。证明：阿里巴巴至多需将手指伸入五次，就可以进入山洞。
容易知道，两次操作(一次靠边的两小孔，一次对角线上的两小孔)把不少于3个开
关扳为状态“上”，如果大门没有打开，这就意味着第四个开关处于状态“下”，这时
阿里巴巴应将手指伸入对角线上的两个孔，如果碰到向下的开关，把它扳为“上”，从
而进入山洞；如果这一对开关均向上，则把其中之一扳为下。这样，显然两个靠边相邻
的开关“上”，另两个相邻开关“下”。然后阿里巴巴沿着正方形边入手；如果两个开
关处于同一状态，他就改变它们状态从而进入山洞；如果两个开关状态不同，他应该都
改变状态，最后一次沿对角线找到开关，改变里面的状态，这样最多五 |
c****e
发帖数: 2097 | 2 赞“好题”，让偶回到高考年代。
洞。
【在 m*********y 的大作中提到】
: 莫斯科竞赛中有这样一道题：阿里巴巴试图潜入山洞。在山洞入口处有一面鼓。鼓的侧
: 面有四个一模一样的小孔，组成正方形的四个顶点。在每个孔的里面各装有一个开关。
: 开关有“上”“下”两种状态。(注意：眼睛看不见！)如果四个开关的状态全都一致，
: 洞门即可打开。现允许将手指伸入任意两个孔，触摸开关以了解其状态，并可随自己的
: 意改变或不改变其状态。但每当这样做了之后，鼓就要飞快地旋转，以至在停转之后无
: 法确认刚才触动了哪些开关。证明：阿里巴巴至多需将手指伸入五次，就可以进入山洞。
: 容易知道，两次操作(一次靠边的两小孔，一次对角线上的两小孔)把不少于3个开
: 关扳为状态“上”，如果大门没有打开，这就意味着第四个开关处于状态“下”，这时
: 阿里巴巴应将手指伸入对角线上的两个孔，如果碰到向下的开关，把它扳为“上”，从
: 而进入山洞；如果这一对开关均向上，则把其中之一扳为下。这样，显然两个靠边相邻
|
S*******s
发帖数: 13043 | 3 自己想了一下，这道题的难度在于怎么把题叙述清楚。解决起来一点不难。
0, 开始状态 ????
1，连续两个变成0，状态00??
2, 如果1，变成0，下一个变成0；如果0，对角变成0， 状态0001
3, 如果1，结束；否则对角变成0。 状态0011
4，连续两个反转 状态1010
5，对角反转 |
