我想這個可看作對角線方法(diagonal method)的一個有趣應用了！
不過matrix大牛可能高估了某些讀者的智商，我覺得非常有趣，嘗試用自己的話再elaborate一下。
---------------------------------------------------
大概意思是一樣的，就是有兩個參數a,b，分別是速度和初始位置。
而時刻為t，可取0,1,2,...
那么，當a,b 固定后，船的位置就是 遞歸可枚舉的(recursive enumerable)。
其勢(cardinality)是可數的(countable), 也即 card(status)=card(Z)，其中status是所有可能的位置，Z是整數集。
status里面每個元素與Z里的元素有一個*一一對應*的關系。
假設我們每次炸的是B點, 且船的位置是A點，則相當于每次從這兩個集合里刪去對應的兩個元素。
再形象一點，每過一秒，船就到一個新的位置，則二維平面上的點(a,b)就少一個，同時我們也會炸一個點——。
因此，在*有限的時間*內（這里的有限是可數，$\aleph 0$），我們可以枚舉所有的點直到命中目標。
因為(a,b)也是可列的，所以對所有的(a,b)都來一次上述過程，必能命中。
Sent to you by Iveney via Google Reader:
via Matrix67: My Blog by Matrix67 on 1/28/10
说有一个潜水艇，初始时位于数轴上的某个整数点，并沿着数轴以每秒整数个单位的速度做匀速运动（但你不知道具体的初始位置和移动速度是多少，移动方向也是未知的）。每一秒你都可以在某个整数点投放深水炸弹，如果此时潜艇正好在你放炸弹的位置，这个潜艇就被炸掉了。你是否有办法可以保证炸毁潜艇？
这是可以办到的。不管初始时潜水艇在哪儿，它的速度有多大，我总能在有限的时间里炸毁潜艇。假设潜艇的速度为 a ，初始位置为 b ，则在第 t 秒时它的位置就在 a*t + b 。把所有可能的有序数对 (a,b) 看作是平面直角坐标系上的整格点，每次考虑其中的一个点；假设第 i 秒考虑的点是 (a_i, b_i) ，那就在 a_i * i + b_i 处放一个炸弹。如此重复做下去，每次排除一种情况，直到击中目标为止。现在的问题就是，用怎样的顺序遍历平面上的所有格点才能保证每个 (a,b) 都会在有限的时间里访问到。这个方法就多了，比如从原点开始以一条螺旋线为路径一圈一圈地遍历周围越来越远的点。
这个问题展示了一些典型的数学思维在传统智力题方面的应用，它背后的数学方法非常深刻。
来源：http://www.reddit.com/r/math/comments/as2d5/sinking_the_submarine_a_puzzle/
Things you can do from here:
- Subscribe to Matrix67: My Blog using Google Reader
- Get started using Google Reader to easily keep up with all your favorite sites
No comments:
Post a Comment