找头盔

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

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

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

楼主的题目是原创的吧……网上根本搜不到。

[size=6]洞窟号：1、2、3、4、5[/size]

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

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


[color=Green]分析
这种题目，我们应该掌握一个解题的技巧，即第一天找的洞窟尽量为2、4号洞窟，我就以2号为例。
若头盔被藏在2号洞窟，那么第二天早上我们就可以找到:hz1023:。（2）
如果头盔被藏在1号洞窟，则第二天晚上只能被移动到2号洞窟，所以第三天我们继续找2号洞:hz1019:。（2、2）


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


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

一、第二天、第三天都向左移动，第四天头盔就在2号洞，所以第四天晚上，头盔可能会被移动到1号或3号洞。
假设被移动到1号洞。
      ——我们就到2号去守株待兔:hz1019:，第五天晚上只能被移动到2号洞，所以我们要连续两天都去2号洞找。（2、2、4、2、2）
假设被移动到3号洞。
      ——我们已经选择了去2号洞两天，就得去！在这两天里，若头盔从3号洞向左移动……:hz1023:
         ——但是，若头盔向右移动:hz1025:就到了4号洞，但谁也不知道头盔第六天晚上会被移动到3号洞还是5号洞……
         聪明点的朋友会选择第七天早上去3号洞找，原因嘛……如果头盔在第六天晚上被移动到3号洞，正好到手！
         如果头盔在第六天晚上被移动到5号洞，它在第七天晚上只能往4号洞转移:hz1023:。（2、2、4、2、2、3、4）
         如果第七天早上选择去5号洞找，万一头盔在第六天晚上被移动到3号洞，后面就麻烦了……

二、第二天、第三天先向左移动，后向右移动（先向右，后向左一样的），第四天早上到了4号洞。我们在上一种的情况下，第四天就是去4号洞找滴，所以……:hz1019:，楼主题目出得不错……（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号洞！:hz1023:（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）:hz1009:。

三、第八天晚上移动前的位置为5号洞。
我们可以先将之前的步骤带入试试看，没准正好……
第八天晚上，头盔只能往4号洞转移，我们第九天早上是去的2号洞。
第九天晚上，它可以被转移到3、5号洞，嗯~~如果是转移到3号洞，正好被擒住:hz1016:，
如果是转移到5号洞，那么，第十天晚上就只能被转移到4号洞了~~哈哈！正好符合（2、2、4、2、2、3、4、2、3、4）[/color]

[color=Black][size=3]以上是本人的做法，希望是最简单的，最容易被理解的~~！[/size][/color]

[color=Silver][[i] 本帖最后由 Mitchell 于 2011-4-20 22:36 编辑 [/i]][/color]

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

回复 #2 Mitchell 的帖子

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

到底是哪个？

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

回复 #4 鸟窠道人 的帖子

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

用你的方法是找不到的。

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

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

[color=Silver][[i] 本帖最后由 Mitchell 于 2011-4-20 12:02 编辑 [/i]][/color]

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

回复 #8 KYOKO 的帖子

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

依样葫芦，不知对不对

如果只有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

回复 #10 KYOKO 的帖子

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

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

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

更好的答案么……只要把2楼的前三天去掉就行了
▲▲▲▲▲
▲[color=red]△[/color]▲▲▲
△[color=red]△[/color]▲▲▲
△▲[color=red]△[/color]▲▲
▲△▲[color=red]△[/color]▲
△[color=red]△[/color]△▲△
△△[color=red]△[/color]△▲
△△△[color=red]▲[/color]△

回复 #13 zhouhuan 的帖子

楼上强人！:hz1026:

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

Thanks a lot !

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

回复 #15 KYOKO 的帖子

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

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

回复 #14 Mitchell 的帖子

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

回复 #17 zhouhuan 的帖子

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

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

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

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

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

[img]http://i.6.cn/cvbnm/07/31/6d/305e61027330b97efd2fbda5164d30db.jpg[/img]
这种题目可以推广到N个洞窟，推测
当N为奇数时，答案为2，3，……，N-1，2，3，……，N-1
当N为偶数时，答案为2，3，……，N-1，1，2，……，N-1

[color=Silver][[i] 本帖最后由 zhouhuan 于 2011-4-22 22:23 编辑 [/i]][/color]

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

回复 #20 zhouhuan 的帖子

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

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

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

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

囧

[color=Silver][[i] 本帖最后由 zhumeng 于 2011-6-25 19:22 编辑 [/i]][/color]

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

[color=Silver][[i] 本帖最后由 dasha1989 于 2011-10-13 12:36 编辑 [/i]][/color]

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

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

对应过程。
[img]http://www.xycq.net/attachments/2011/12/97330_201112202313321.jpg[/img]

空心三角等于空心圆。

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

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

[img]http://i.6.cn/cvbnm/07/31/6d/305e61027330b97efd2fbda5164d30db.jpg[/img]
这种题目可以推广到N个洞窟，推测
当N为奇数时，答案为2，3，……，N-1，2， ... [/quote]
用墨叶提供的方法试了一下5洞，6洞的情况，猜测N个洞的情况下，无论奇数偶数
采用如下方法可以找出，但不知道是不是最优解。
2，3，……，N-1，N-1,N-2,……，3,2..

回复 #28 toushion 的帖子

是的。我是这样认为的。

[quote]原帖由 <i>toushion</i> 于 2012-7-14 04:16 发表<br />

<br />
用墨叶提供的方法试了一下5洞，6洞的情况，猜测N个洞的情况下，无论奇数偶数<br />
采用如下方法可以找出，但不知道是不是最优解。<br />
2，3，……，N-1，N-1,N-2,……，3,2.. [/quote]<br />
原先我想的是从1开始用逼退法，看完之后我确定自己逊了一筹