Author Topic: 每周一题: 阿里巴巴开山门 (7/5/04-7/11/04)  (Read 5699 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 阿里巴巴开山门 (7/5/04-7/11/04)
« on: 七月 05, 2004, 10:37:03 am »
上周题目讨论

上周的题到现在还没人给出答案。其实这问题不难。我想关键是大家都去想具体操作去了,没有想到我们的题只要求存在性证明,并不要求具体操作。我们要求证明给一个矩形巧克力,先掰的人总能有最佳办法把最后一块留给对手。因为只有有限块巧克力,各种掰的组合也有限,所以最佳办法总是存在的。只是不知道这最佳办法属于先掰的还是后掰的。如果属于后掰的,也就是说不管先掰的第一次掰什么,后掰的都能从那开始取得胜利。现假设先掰的人第一步只掰右上角的一块小巧克力,如果存在一种掰法使后掰的人可以胜利的话,那么先掰的人完全可以第一步就直接掰到后掰的人的最佳第一步那里,这样这个最佳办法就属于先掰的人了。证毕。

像这种不给具体操作方法,只证明其存在性的证明是近代数学的东西,以前的人是不接受这种证明的。甚至于到希尔伯特的时候都还有人以此攻击他的一些证明。对于我们这道题,不同的初始大小,最佳解法就不同,要给出一个统一的可操作办法大概不是一件很容易的事。

一般来说,每次出了一个难题以后(没人解出),我想应该出一个比较容易一点的。这周的题应该比较容易。但如果你想不对思路的话,你会觉得简直无解。这样的题目我觉得是最好的趣味问题。

本周题目:

阿里巴巴来到一个山门前,念了一阵芝麻开门居然没有任何动静。仔细关查了一下,发现门旁边有一个方形柱子。柱子四面每面都有一个洞。每个洞内都有一个按纽式的开关。这种开关从外面看不出是开是关,但每按一下就会改变状态(由开到关,或由关到开)。柱子顶上有文字说如果四个开关都处于开的状态或者都处于关的状态,山门就会打开。他可以把两只手伸进任何两个洞里,并操作开关。问题是每当他的手一离开洞口,柱子就快速转动,停下来的时候他已经搞不清楚他刚才伸进的是哪两个洞了,事先也没办法做任何记号。我们的问题是,在不知道开关的初始状态的情况下,你如何能帮助阿里巴巴在有限步内把开关打开。

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 阿里巴巴开山门 (7/5/04-7/11/04)
« Reply #1 on: 七月 06, 2004, 06:11:04 am »
这个嘛,只要一只手放在一个洞里不拿出来,另外一只手把另三个按钮的2^3=8个状态都试一遍,就可以了。

这样做比较流氓 :oops:

不流氓的解法(也就是每操作一次都要把手拿开)是:

开关的状态要么是3:1(三开一关或三关一开),要么是2:2。

A)如果是2:2,则1)要么对面(东西或南北)的两个开关状态相同,2)要么相邻(东南,西北等等)的两个开关相同。

所以首先把手伸到对面的两个洞里按一下,如果不开,说明不是1),那么就是2),然后把手伸到相邻的两个洞里按一下,要是恰好按对了,门就开了,如果没按对,那就把相邻的情况2)变成对面的情况1)了,那就再把手伸到对面的两个洞里按一下。

什么?还没开?那就一定是
B)3:1的情况。把手伸到无论哪个洞里按一下,那就要么门开了,要么变成2:2的情况,那就再照A)做一遍。