離散数学的な解
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/16 23:21 UTC 版)
「ゴムロープの上のアリ」の記事における「離散数学的な解」の解説
この問題を解くには解析学的な手法が要るように見えるが、ロープが(連続的にではなく)1秒ごとに瞬間的に伸びるような問題の変種を考えることで、実は離散的な議論が通用する。実際、以下の議論はマーティン・ガードナーがサイエンティフィック・アメリカン誌上で元々行い、後に再版されたものを一般化したものである。 問題を若干修正して、各単位時間(1秒)の開始の瞬間にロープが伸びるものとする。よって、時刻 t = 0 {\displaystyle t=0} で目標地点は x = c {\displaystyle x=c} から x = c + v {\displaystyle x=c+v} にジャンプし、時刻 t = 1 {\displaystyle t=1} で目標地点は x = c + v {\displaystyle x=c+v} から x = c + 2 v {\displaystyle x=c+2v} にジャンプする、といった具合である。問題の変種では各単位時間(1秒)の終了の瞬間にロープが伸びると仮定されることが多いが、もしこのような条件(開始時刻に伸びる)でアリが目標地点に到達することが分かったなら、元々の問題のロープが時間連続的に伸びる設定であっても、ロープが終了の瞬間に伸びる設定であっても到達すると結論できる。 θ ( t ) {\displaystyle \theta (t)} を原点から目標地点までのうち、アリが進んだ部分の割合とする( t {\displaystyle t} は時刻)。よって θ ( 0 ) = 0 {\displaystyle \theta (0)=0} である。最初の1秒でアリは α {\displaystyle \alpha } だけ進み、これは原点から目標地点(最初の1秒の間、ずっと位置 c + v {\displaystyle c+v} にある)までの距離の α c + v {\displaystyle {\frac {\alpha }{c+v}}} である。ロープが瞬間的に伸びると、アリも一緒になって動くから θ ( t ) {\displaystyle \theta (t)} は変わらない。よって θ ( 1 ) = α c + v {\displaystyle \theta (1)={\frac {\alpha }{c+v}}} 。次の1秒間にアリは再び α {\displaystyle \alpha } だけ進み、これは原点から目標地点までの α c + 2 v {\displaystyle {\frac {\alpha }{c+2v}}} である。よって θ ( 2 ) = α c + v + α c + 2 v {\displaystyle \theta (2)={\frac {\alpha }{c+v}}+{\frac {\alpha }{c+2v}}} 。同様にして任意の n ∈ N {\displaystyle n\in \mathbb {N} } に対し θ ( n ) = α c + v + α c + 2 v + ⋯ + α c + n v {\displaystyle \theta (n)={\frac {\alpha }{c+v}}+{\frac {\alpha }{c+2v}}+\cdots +{\frac {\alpha }{c+nv}}} が得られる。 任意の k ∈ N {\displaystyle k\in \mathbb {N} } について α c + k v ≥ α k c + k v = ( α c + v ) ( 1 k ) {\displaystyle {\frac {\alpha }{c+kv}}\geq {\frac {\alpha }{kc+kv}}=\left({\frac {\alpha }{c+v}}\right)\left({\frac {1}{k}}\right)} であることに注意すると、 θ ( n ) ≥ ( α c + v ) ( 1 + 1 2 + ⋯ + 1 n ) {\displaystyle \theta (n)\geq \left({\frac {\alpha }{c+v}}\right)\left(1+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)} 因子 ( 1 + 1 2 + ⋯ + 1 n ) {\displaystyle \left(1+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)} は調和級数の部分和なので、発散する。よって 1 + 1 2 + ⋯ + 1 N ≥ c + v α {\displaystyle 1+{\frac {1}{2}}+\cdots +{\frac {1}{N}}\geq {\frac {c+v}{\alpha }}} となるような N ∈ N {\displaystyle N\in \mathbb {N} } をとることができ、これは θ ( N ) ≥ 1 {\displaystyle \theta (N)\geq 1} 、つまり十分な時間を経た後には、アリは目標地点までの旅を完遂することを意味する。この解法では所要時間の上限も同時に得られるが、正確な時間までは分からない。
※この「離散数学的な解」の解説は、「ゴムロープの上のアリ」の解説の一部です。
「離散数学的な解」を含む「ゴムロープの上のアリ」の記事については、「ゴムロープの上のアリ」の概要を参照ください。
- 離散数学的な解のページへのリンク