原题
这又是某度的一条面试题，我觉得这是我面该司的最有意思、最考思维的题目了，大意如下：
山上有五个山洞排成一行，编号从1到5。有个狐狸，它第一天藏在某个山洞中，从第二天开始，每天可以逃到前一天所在山洞相邻的山洞中，但逃到哪一个是随机的（当然如果狐狸当前在1号山洞那么它第二天只能去2号洞了，5号也类似）。有个猎人，他每天只能搜寻一个山洞（因为山洞太复杂了。。。。），如果狐狸当天在他搜寻的山洞中就被逮到了。问猎人是否有必定能抓住狐狸的策略？
这个题看起来像IQ题，不过考的仍然是数学思维。从题目的提问方式就知道这题必定有解的，可惜我当时没完全做出来，思路倒是给对了。以下先来考虑一些简单的变种。假设只有3个山洞，易知最坏情况下在第二个山洞连续呆两天必定能抓到狐狸。如果有4个山洞呢？通过某种暴力枚举策略的方法容易得到如下策略：首先在2号洞呆两天，如果没抓着说明狐狸当前在3或4号洞，于是第3天去3号洞再呆两天，如果还没抓住说明当前狐狸在1号洞，于是第5天去2号洞就逮到了。
但是，一旦上升到5个山洞，暴力枚举就很难了，数手指都会数到头晕。必须抓住问题的本质才能得到简洁的方法。上述解法的本质是什么呢？答：奇偶性！通过前3天的搜寻，我们可以得出结论：狐狸在第一天的时候必然不在奇数号洞中，否则一定可以在前3天内逮到！接下来，用类似的方法把偶数的可能性搜寻一次，便找到狐狸了。
于是我们有如下解法：猎人第一天在1号洞，第二天在2号洞，……，直到第四天在4号洞，如果经过这4天还没逮到狐狸，说明狐狸第一天在偶数号洞中，即第四天在奇数号洞中。这是为什么呢？这是因为，假设狐狸第一天在奇数号洞中，由于猎人第一天也在奇数号（1号）洞中，每经过一天，他们俩的距离要么不变，要么减2。由于一开始时的距离是大于0的偶数（假设第一天没逮到），在整个过程中距离必定在某一天变成0。这样，如果前4天都没抓到的话，狐狸第一天一定在偶数号洞中。于是从第5天开始，用类似的方法反向扫描一次（第五天再在4号洞中呆一天，然后第六天去3号洞，第七天去2号洞），必能逮到狐狸。
我个人认为这是相当美妙的解答，有些元素我至今仍未琢磨透。当有n个山洞时的解法是一样的：正向扫描一次到第n−1个洞，然后在该洞中呆多一天，紧接着反向扫描到第2个洞即可。最坏情况下只需2n−3就能逮到狐狸。
如果问题改为求最坏情况下能抓住狐狸需要的最少天数，该怎么解呢？易知当n=3时为2，n=4时为5，那么当n比较大的时候呢？由上面的解答中我们可以得到一个上界是2n−3，但是这个是最少天数吗？我不知道，也没法证明。哪位网友如果证明了请告诉我一声:)。
[2012/10/12补充]
今天又想到一个更好的解，不管n多大，最坏情况下只需2n−4天就能逮到狐狸，策略是这样的：
若n为奇数，则从第一天开始搜寻的山洞编号为：2, 3, 4, …, n-1, 2, 3, 4, …, n-1 若n为偶数，则从第一天开始搜寻的山洞编号为：2, 3, 4, …, n-1, n-1, n-2, …, 3, 2 不管哪种情况，只需2n−4步即可逮到狐狸。
证明也是很容易的，这里只证n为奇数的情况：前面n-2天的搜寻可以排除狐狸第一天在偶数号洞的所有case，后面n-2天的搜寻可以排除狐狸第一天在奇数号洞的所有case。当n为偶数时，后n-2天的搜寻是反序的，这样才能排除掉狐狸第一天在奇数号洞的所有case（奇偶性不同）。
环形山洞
如果山洞不是排成一排而是连成一个环，是否又有必胜策略呢？
这个我目测是没有的。我也没空去想如何证明，如果哪位网友想到了证明或者证明我是错的，都欢迎留下解答过程！:)
二维扩展
如果是二维的山洞，狐狸每天只能逃到和前一天所在山洞相邻的山洞，问猎人是否还有必胜策略？
上述环形山洞问题是这个扩展问题以及更高维的扩展问题的一个特例。所以如果上述问题的答案是“否”，此题也一样。
受限的猎人
[2016/11/18补充]
受限的猎人：猎人能看到狐狸，但只能像狐狸那样每次移动到相邻山洞
这个问题的二维版本出自《算法谜题》（Algorithmic Puzzles）题73。
未完待续。