对于所有的 n=2^k ,解法如下
将所有孔用二进制按顺序编号,构造一棵完全二叉树
称根节点为第0层
第一层两颗子树分别按编号最低位为0和为1分开孔在左右子树
第二层层按第二低位0和1分开
...
直到最下层按最高位0和1分开
初始状态所有孔随机为0或者1
* 我们的目标是把所有叶子节点全设为0或全设为1
现在如果我们摸所有编号从低往高数第a位相同的孔,就会摸到第a层的一半子树,
且每个子树和其兄弟子树只会摸到一棵,不能确定摸到的是左子树还是右子树
记这种摸法为Ma
首先把所有最高位为1的孔全设0,把所有次高位为1的孔全设0,...,直到把所有最低位为1的孔全设0
现在要么所有孔为0,要么只有1个孔为1其他全0
摸M1,摸到1就设为0,摸不到就随便设置一个孔为1
现在第1层的两颗子树要么都是全0,要么各有一个1的孔
递归证明如果能通过某种操作 F 使得第 m 层所有子树各有一个1的孔,我们能够操作使得第 m+1 层每颗子树各有一个1的孔,或者所有孔为0
摸M(m+1),摸到 2^(m+1)棵子树,有1的子树就全设为0,没1的子树就随便设一个孔为1
现在第m层的所有子树,只有2种情况,两个子树各有一个1,或者全是0
通过摸M1,M2...Mm全设0,如果不是全0,那就是除了一棵m层的子树有左右子树各一个1,其他全是0的状态
按之前的操作 F 再操作一次,只是这次设1的时候改为设第 m+1 层的两子树各一个1
可得到所有第m层的树都是两个子树各1个1,
也就是第 m+1 层每颗子树各有一个1的孔
于是我们可以操作得到最底层所有孔都是1,或者都是0
【 在 GGGGDDDDK 的大作中提到: 】
: 标 题: 阿里巴巴山洞问题
: 发信站: 水木社区 (Tue Aug 24 02:11:03 2021), 站内
:
: 阿里巴巴试图潜入山洞。在山洞入口处有一面鼓。鼓的侧面有2n个一模一样的小孔,组成正2n边形的2n个顶点。在每个孔的里面各装有一个开关。开关有“上”“下”两种状态。(注意:眼睛看不见!)如果2n个开关的状态全都一致,洞门即可打开。现允许将手指伸入任意n个孔,触摸开关以
: 了解其状态,并可随自己的意改变或不改变其状态。但每当这样做了之后,鼓就要飞快地旋转整数格,以至在停转之后无法确认刚才触动了哪些开关。求所有的正整数n,使得阿里巴巴能够在有上界的步数之内进入山洞。
:
:
: ※ 来源:·水木社区 mysmth.net·[FROM: 111.26.240.211]
--
FROM 111.193.197.*