轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 找头盔 [打印本页]

作者: 鸟窠道人 时间: 2011-4-19 19:50 标题: 找头盔

看到一道智力题，蛮有意思的。

有5个洞窟，排成一排，前一天晚上有人会在其中一个洞窟放一个头盔，次日白天你可以去找头盔，但是只能找一个洞窟，如果没有找到，那么那人会在晚上移动一次头盔，但是只能向右或者向左移动一格，必须移动，请给出一个方案，必定能够找到头盔。

大家想想吧，O(∩_∩)O哈哈~。

作者: Mitchell 时间: 2011-4-19 21:17 标题: 楼主的题目是原创的吧……网上根本搜不到。

洞窟号：1、2、3、4、5

答案：从第二天早上开始，依次找2、2、4、2、2、3、4、2、3、4号洞窟。

【注】答案不唯一，此为其中之一种。

分析
这种题目，我们应该掌握一个解题的技巧，即第一天找的洞窟尽量为2、4号洞窟，我就以2号为例。
若头盔被藏在2号洞窟，那么第二天早上我们就可以找到

。（2）
如果头盔被藏在1号洞窟，则第二天晚上只能被移动到2号洞窟，所以第三天我们继续找2号洞

。（2、2）

后面的略复杂些……
若头盔被藏在3号洞窟，第二天晚上被移动到2号洞，则第三天就可以找到头盔；
若第二天晚上被移动到4号洞，则第四天我们就应该去4号洞找。（2、2、4）

后面的更复杂，越来越复杂了……
若头盔被藏在4号洞，则要分多种情况讨论。

一、第二天、第三天都向左移动，第四天头盔就在2号洞，所以第四天晚上，头盔可能会被移动到1号或3号洞。
假设被移动到1号洞。
——我们就到2号去守株待兔

，第五天晚上只能被移动到2号洞，所以我们要连续两天都去2号洞找。（2、2、4、2、2）
假设被移动到3号洞。
——我们已经选择了去2号洞两天，就得去！在这两天里，若头盔从3号洞向左移动……

——但是，若头盔向右移动

就到了4号洞，但谁也不知道头盔第六天晚上会被移动到3号洞还是5号洞……
聪明点的朋友会选择第七天早上去3号洞找，原因嘛……如果头盔在第六天晚上被移动到3号洞，正好到手！
如果头盔在第六天晚上被移动到5号洞，它在第七天晚上只能往4号洞转移

。（2、2、4、2、2、3、4）
如果第七天早上选择去5号洞找，万一头盔在第六天晚上被移动到3号洞，后面就麻烦了……

二、第二天、第三天先向左移动，后向右移动（先向右，后向左一样的），第四天早上到了4号洞。我们在上一种的情况下，第四天就是去4号洞找滴，所以……

，楼主题目出得不错……（2、2、4）

综合上面四种情况，当头盔被藏在1、2、3、4号洞时，我们按照2、2、4、2、2、3、4的顺序找，肯定能找到！
就下来，我们要想想，当头盔一开始被藏在5号洞时，我们应该怎么去找……
首先，我们要清楚一点，已经确定下来的不能再改了……（2、2、4、2、2、3、4）
在这八天里，头盔可以怎么移动？移动的方法有很多种，但我们最重要的是看两点：
一是在这八天里，头盔会不会被我们碰巧找到；二是若前八天里没有被我们找到，八天之后会在什么位置。
在这七天内被我们找到的情况不要考虑了，关键是八天后的位置。

八天内不被找到的情况下，头盔可能有12种移动顺序：
一 4、3、4、3、4、3
二 4、3、4、3、4、5
三 4、3、4、3、2、1
四 4、3、4、3、2、3
五 4、3、4、5、4、5
六 4、3、4、5、4、3
七 4、5、4、3、4、3
八 4、5、4、3、4、5
九 4、5、4、3、2、1
十 4、5、4、3、2、3
十一 4、5、4、5、4、5
十二 4、5、4、5、4、3

我们关键是看第八天晚上移动前的位置，可能是1、3、5号洞。接下来我们要分情况讨论。

一、第八天晚上移动前的位置为1号洞。
第八天晚上只能往2号洞转移，第九天早上我们就瞄准2号洞！

（2、2、4、2、2、3、4、2）

二、第八天晚上移动前的位置为3号洞。
第八天晚上可以往2、4号洞转移，要在分情况的基础上再分情况。
——第八天晚上往2号洞移动…………貌似……与1号洞的情况相同~~（2、2、4、2、2、3、4、2）
——第八天晚上往4号洞转移。通过前面积累的经验，这里我们应该缓慢进军，逐步逼近~~（2、3、4），
（2、2、4、2、2、3、4、2、3、4）

。

三、第八天晚上移动前的位置为5号洞。
我们可以先将之前的步骤带入试试看，没准正好……
第八天晚上，头盔只能往4号洞转移，我们第九天早上是去的2号洞。
第九天晚上，它可以被转移到3、5号洞，嗯~~如果是转移到3号洞，正好被擒住

，
如果是转移到5号洞，那么，第十天晚上就只能被转移到4号洞了~~哈哈！正好符合（2、2、4、2、2、3、4、2、3、4）

以上是本人的做法，希望是最简单的，最容易被理解的~~！

[ 本帖最后由 Mitchell 于 2011-4-20 22:36 编辑 ]

作者: 鸟窠道人 时间: 2011-4-20 08:33

不是，我只是翻译了一下而已，原版的是英文的，呵呵

作者: 鸟窠道人 时间: 2011-4-20 08:41 标题: 回复 #2 Mitchell 的帖子

我觉得只要在2、4两个位置找就行了，2,2,4,2,2,2,4

作者: KYOKO 时间: 2011-4-20 10:16

到底是哪个？

4L答案如果对的最好的地方就在于7天之内就能找到。。

作者: Mitchell 时间: 2011-4-20 11:58 标题: 回复 #4 鸟窠道人的帖子

假设头盔被藏在5号洞，如果移动顺序为4、3、4、5、4、3或4、3、4、3、4、5，

用你的方法是找不到的。

作者: Mitchell 时间: 2011-4-20 12:00

这种问题，我们必须把所有可能的情况都考虑一下，才能确定最终的方法。

用我在#2提供的方法，无论头盔一开始被藏在哪个洞窟，无论头盔被怎样转移，最终都可以找到！

[ 本帖最后由 Mitchell 于 2011-4-20 12:02 编辑 ]

作者: KYOKO 时间: 2011-4-20 12:00

第三天都是4，不是找到了吗？

作者: Mitchell 时间: 2011-4-20 12:07 标题: 回复 #8 KYOKO 的帖子

请想清楚，我说的4是第三天晚上被转移到的洞窟号，而楼主的4是第三天早上去找的洞窟号。

作者: KYOKO 时间: 2011-4-20 14:14

依样葫芦，不知对不对

如果只有4个洞，怎么选择呢？2 2 3 。。第一天是1,2,3号洞都解决了，这简单

如果第一天是4号洞呢

4 3 2 1
4 3 2 3
4 3 4 3

那第四天我该找3号洞，如果不在，那第4天必然是在1号洞，因此第五天必然是在2号洞。因此，整体是2 2 3 3 2

作者: Mitchell 时间: 2011-4-20 18:02 标题: 回复 #10 KYOKO 的帖子

你说得不错，但如果是5个洞，则会复杂很多……

作者: 托塔李天王 时间: 2011-4-20 21:38

2楼分析得很详细，加分奖励。

如证明是最佳答案，另行奖励。

作者: zhouhuan 时间: 2011-4-21 16:07

更好的答案么……只要把2楼的前三天去掉就行了
▲▲▲▲▲
▲△▲▲▲
△△▲▲▲
△▲△▲▲
▲△▲△▲
△△△▲△
△△△△▲
△△△▲△

作者: Mitchell 时间: 2011-4-21 17:48 标题: 回复 #13 zhouhuan 的帖子

楼上强人！

我还是第一次做这种题目，看到楼上直观的图解，我终于知道解决此类题目的基本方法了……

Thanks a lot !

作者: KYOKO 时间: 2011-4-21 19:38

没看明白13L，都代表啥意思？

作者: Mitchell 时间: 2011-4-21 20:28 标题: 回复 #15 KYOKO 的帖子

红色的空心三角形代表去找而没有找到的洞窟，
红色的实心三角形代表去找并且找到了的洞窟，

黑色的空心三角形代表不可能有头盔的洞窟（已经找过的洞窟），
黑色的实心三角形代表头盔可能在的洞窟（尚未找过的洞窟）。

作者: zhouhuan 时间: 2011-4-21 21:53 标题: 回复 #14 Mitchell 的帖子

惭愧
我只是想到了这个模型，不过到第三天白天找完后（2，2），接下来就没思路了，看了你的答案才明白其中的关键，倒推回来自然会简单一些。
现在想想，其实还可以再化简，答案是234234

作者: Mitchell 时间: 2011-4-21 22:42 标题: 回复 #17 zhouhuan 的帖子

所谓“当局者迷，旁观者清”，可能就是这个道理吧……

我刚刚发出#2的帖子时，反复检查了若干遍，没有发现任何问题~~现在又读了一遍，感觉漏洞百出……

我发#2的帖子时，只有到最后才提到要先将前面的代入，正因为如此，前面的2、3号洞连去了N天，而最后的2、3、4，无法再删减……

此外，本题答案并不唯一，（4、3、2、4、3、2）也是最佳答案。

作者: zhouhuan 时间: 2011-4-21 23:08

嗯，不过所有答案应该都可以归为同一类，其本质是相同的

这种题目可以推广到N个洞窟，推测
当N为奇数时，答案为2，3，……，N-1，2，3，……，N-1
当N为偶数时，答案为2，3，……，N-1，1，2，……，N-1

[ 本帖最后由 zhouhuan 于 2011-4-22 22:23 编辑 ]

作者: zhouhuan 时间: 2011-4-22 14:44

突然又想到一个推广，从一维到二维
有9个洞窟排成三行三列，前一天晚上有人会在其中一个洞窟放一个头盔，次日白天你可以去找头盔，但是只能找两个洞窟，如果没有找到，那么那人会在晚上移动一次头盔，但是只能向“前后左右”移动一格，必须移动，请给出一个方案，必定能够找到头盔。

作者: Mitchell 时间: 2011-4-22 17:32 标题: 回复 #20 zhouhuan 的帖子

如果有自己原创的题目，建议开新帖发表，这样比较容易被人发现……

跟帖发表很可能被无视的。

作者: zhouhuan 时间: 2011-4-22 20:20

好吧，我去重开一个，不过这里实在太冷清了

作者: 金圭子 时间: 2011-6-18 18:37

原创的？我记得年初在哪里看到过的，一本类似于智力题集的书，不过答案倒是不记得了。

作者: zhumeng 时间: 2011-6-25 19:18

囧

[ 本帖最后由 zhumeng 于 2011-6-25 19:22 编辑 ]

作者: dasha1989 时间: 2011-10-13 11:19

感觉吧！前4天按22434找，最多第5天一定能找到了！

[ 本帖最后由 dasha1989 于 2011-10-13 12:36 编辑 ]

作者: 墨叶 时间: 2011-12-20 23:26

和19楼答案完全一样。
表达方式略有不同。

解：●表示该回合此位置不可能有头盔，○表示当天查看该位置。
当某个洞的临近位置前一回合均为●或者○时，该回合必定为●。

对应过程。

空心三角等于空心圆。

作者: 26595117 时间: 2012-1-7 15:57

我觉得只要在2、4两个位置找就行了

作者: toushion 时间: 2012-7-14 16:16

QUOTE:

原帖由 zhouhuan 于 2011-4-21 23:08 发表
嗯，不过所有答案应该都可以归为同一类，其本质是相同的

这种题目可以推广到N个洞窟，推测
当N为奇数时，答案为2，3，……，N-1，2， ...

用墨叶提供的方法试了一下5洞，6洞的情况，猜测N个洞的情况下，无论奇数偶数
采用如下方法可以找出，但不知道是不是最优解。
2，3，……，N-1，N-1,N-2,……，3,2..

作者: 墨叶 时间: 2012-7-14 16:18 标题: 回复 #28 toushion 的帖子

是的。我是这样认为的。

作者: 布e 时间: 2013-2-2 11:47

QUOTE:

原帖由 toushion 于 2012-7-14 04:16 发表 

 
用墨叶提供的方法试了一下5洞，6洞的情况，猜测N个洞的情况下，无论奇数偶数 
采用如下方法可以找出，但不知道是不是最优解。 
2，3，……，N-1，N-1,N-2,……，3,2..

原先我想的是从1开始用逼退法，看完之后我确定自己逊了一筹

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)