趣题:阿里巴巴开洞门

其实就是上一篇的四开关问题。昨天师院老师来讲课时又提了一下,只要5步就可以解出来了。

题目:在一个门上,有一个圆形的转盘,上面有四个开关(上下左右),每次可以抓住两个开关,分别对它进行操作(设置成开或关)。但是圆盘会飞速转动,也就是说,当你的手伸入圆盘时,你可以并且尽可以抓到两个开关;而当你手伸出来后,你无法知道你下一次抓的是什么。当四个开关同为开或同为关,门就会打开。问能否在有限次的操作内打开这扇门?

解法:

跟上一篇一样,将无限状态转化为有限状态。但上一篇我的解法是不确定的,因此多了许多状态,所以就慢了些。

这个解法只要5步:

1.抓一条对角线并置0

2.抓一条边并置0

注意,此时我们固定抓到了三个点,并且有三个0。若另一个为0,则门打开,否则另一个为1,继续讨论。

3.抓一条对角线,若为两个0则将其中一个置1,否则将两个都置1。

此时将可以产生2种状态:

4.抓一条边,若两个同为1或0则取反,否则不变。

此时上面左边状态已经完成,右边的将不变。

5.抓一条对角线。

此时所有状态都已经完成。

Comments