あみだクジの証明

あみだクジですが、上のある場所を選んで、線をたどりながら
一番最後に到達します。
曲がり角では必ず曲がりますが、その途中で、他の線を選んだの
と同じ線をたどる（ぶつかる）ことがあります。
しかし、最終点では決して他の物と鉢合わせすることがありません。
当たり前のようですが、これを数学的に証明できないでしょうか？

No.5 ベストアンサー 回答者： good777 回答日時： 2006/10/18 22:44

あみだくじの横棒は縦棒の交差と考えるとよいのです。

　

│　│
│　│
├─┤
│　│
│　│

は

│　│
│　│
　Х
│　│
│　│

です。

No.4 回答者： santye 回答日時： 2006/10/17 22:43

証明は数学的に出来ますよ。

数学的帰納法を使ってみてください。一応略解みたいなもの↓

n=0（つまり横線がないとき）はいうまでもなく一通りに終着点までいきます。
n=kのときに、行き先が重ならないと仮定する。
そのアミダに線を新たに一本引いたとき、その引いた線でつながった
二本の縦棒について置換がなされるだけで、行き先は新たに定まった
一通りになる。
故にn=k+1のときも成り立つので帰納的に示される。

No.3 回答者： incd 回答日時： 2006/10/17 22:34

自分は大体こんな説明で納得しています。

１.選択肢をＮ個にするならば、Ｎ本の線分を縦に引き、仮に上端をスタート、下端をゴールとする。これはアミダくじの原型になっている。
各線分間をつなぐ道は１つもないから、スタートが違えば必ずゴールは異なる。
２.次に、好きな２つの線分をつなぐ道を１本引く。すると、選んだ２本の線分のスタートとゴールが入れ替わる。したがって、これでも別のスタートから同じゴールへ行くことはない。
３.アミダくじがどんなに複雑になるとしても、２番のステップの繰り返しに過ぎないから、結局別のスタートから同じゴールへ行くことはない。

ちなみに
>他の線を選んだのと同じ線をたどる（ぶつかる）
というのは、つまり同じ道を逆向きに動く場合ですよね。その可能性を除いて、同じ道を通ることは原理的にありえない話です。

No.2 回答者： noname#24129 回答日時： 2006/10/17 22:33

横の線をたどる方向は、右から左の場合と、左から右の場合の2通りあります。

同じ横の線をたどったとしても、横の線にたどり着く前の縦の線が別であれば、次にたどる縦の線は別のものです。

したがって、横の線をたどって、同じ縦の線をたどるためには、その前に、同じ縦の線をたどっていなければなりません。

ところが、もともと、別のスタート位置から、縦の線をたどるわけですから、そのようなことはまったく生じないのです。したがって、同じゴールに着くことはありません。

「数学的に」ということは、「論理的に」ということだととらえ、数学記号を用いていません。その必要はないし、その記法の説明で、かえって煩雑になると考えたからです。

No.1 回答者： Quattro99 回答日時： 2006/10/17 22:29

別の出発点からスタートしてゴールが同じになったとすると、ゴールから戻ることを考えると矛盾が生じます。