當前位置: 華文星空 > 財經

魔鬼如何在最短時間內抓住天使?

2021-09-09財經

估算一個上界。思路是每一輪都尋求一條最短線段,將當前包含天使的多邊形,按面積等分成兩個新的子多邊形。再假設天使的運氣足夠好,每次都瞬移到等分效率較低的子多邊形。

直觀看出,取平行於正三角形一條邊的線段來等分其面積,等分效率最高。令此線段長度 x ,三角形邊長 a ,則:

\frac{x}{a}=\sqrt{\frac{1}{2}}\Rightarrow x=\frac{\sqrt{2}}{2}a=pa

這樣,初始正三角形被分成一個新的小正三角形和一個等腰梯形,易見等腰梯形的等分效率遠高於新的小正三角形,於是根據假設,天使將瞬移到新的小正三角形當中。如此迴圈,至於無窮,天使將被釘選在初始正三角形的一個頂點。計算魔鬼走過的耗時路程:

D=a\sum_{n=1}^{\infty}p^n=\frac{pa}{1-p}=(\sqrt{2}+1)a

記魔鬼速度 v ,則捉住天使的時間:

t<T=\frac{D}{v}=(\sqrt{2}+1)\frac{a}{v}=\sqrt{2}+1

這個題目如此離散,不借助於數值離散最佳化不易得到全域最優解,建議大家來改進這個上界吧。

按照 @yyx 說的圓弧線等分正三角形以及後續的扇形,上界可以改進為:

T=(\sqrt{2}+1)\sqrt{\frac{\pi\sqrt{3}}{6}}\frac{a}{v}=(\sqrt{2}+1)\sqrt{\frac{\pi\sqrt{3}}{6}}