どのような「あみだくじ」でも、必ず別のゴールに着くことを数学的に証明してください。

それは公理だから、証明の対象にはなりません。

別のゴールって直下には行かないということでしょうか。

そうはならないと思いますが……

A   B   C
│  │  │
├─┤  │
│  ├─┤
│  │  │
│  ├─┤
├─┤  │
│  │  │
A'  B'  C'

横線がまったくない場合をまず考えると、縦線は出発点と終点を結ぶものであって、１対１対応します。つまり、別のゴールに着きます。

つぎに、横線を１本ひいた場合を考えます。

もし、横線に一方通行を認めると、結んだ２つの縦線が１本に合流します。そうすると、１対１対応は乱れます。

横線を双方向通行にしている限り、結んだ２つの縦線は、互いに終点を交換しただけになります。よって、出発点と終点の１対１対応は乱れません。つまり、別のゴールにつきます。

横線をいくらひいても、この縦線の出発点・終点の対応の交換をしているだけになるので、１対１対応は乱れません。

以上、数学的帰納法っぽく書いてみました。

「あみだくじ」の定義にもよりますが、入り口の数と出口の数が同じであり、縦線と横線の交点がすべて異なる場合、違う入り口は違う出口に対応します。

つまり、別の入り口から入ったのに同じ出口から出るなんてことは起こりません。

証明は下記ページがわかりやすいかと。

http://homepage3.nifty.com/funahashi/suugaku/suu40.html

逆に言えば、入り口の数が出口の数より多いあみだくじを作れば、当然ながら違う入り口から入ったのに同じ出口から出るということが起こります。

> 無理やりでもよいので、数式で表せたりしないもんでしょうかｗ

というわけで考えてみる。

数学の行列をつかって示せるかな。

あみだの入り口と出口の数は当然同じ数nだとして、

行番号を入り口、列番号を出口と考えたn*nの単位行列を考える

(これは正則なので 行列式==1 )

横線のないn=5のあみだなら

E = 
出口＼入口   1  2  3  4  5 
             -------------
         1 | 1  0  0  0  0
         2 | 0  1  0  0  0
         3 | 0  0  1  0  0
         4 | 0  0  0  1  0
         5 | 0  0  0  0  1

あみだの横線はこの行列に行基本変形の行入れ替え行列をかけることに相当する。これは下記のように表す

P(i,j) = 単位行列のi行とj列を入れ替えた行列

i=3, j=2なら

P(3,2) = 
             1  2  3  4  5
             -------------
         1 | 1  0  0  0  0
         2 | 0  0  1  0  0
         3 | 0  1  0  0  0
         4 | 0  0  0  1  0
         5 | 0  0  0  0  1

この行列式はi,jの値によって(-1)^(i+j) となり、0にはならない

横線の出現する順にP1,P2とすれば

全てのあみだはEにPを複数回かけたものに相当するので

A = ...*P2*P3*P1*E

こうしてできた行列AはEの順番を様々な形に入れ替えたものだが、

PもEも行列式は0ではないので Aの行列式も0にはならない。

すなわちあみだAは正則である。

ここでおなじ出口にたどり着く行列を考えてみると例として

B = 
             1  2  3  4  5
             -------------
         1 | 1  0  0  0  0
         2 | 0  1  0  0  0
         3 | 0  0  0  1  0
         4 | 0  0  0  1  0
         5 | 0  0  0  0  1

のようになり、全く同じ行が出現することになる。

これは明らかに正則で"ない"のでBの行列式は=0となる

すべてのあみだはAの形式で表されるはずなので

行列式が0になるのはこれと矛盾する

よってあみだは別の入り口から同じ出口にたどり着くことはない。

(もちろんあみだのルールが地域によって違うかもしれないですが..)

あみだを

A = p*p*p*E

で表すことができるのは面白いかと。

よくよく考えるとこれは数学の『置換』の概念と全く同じですね。

組み合わせはn!とおりか。

一言で言えば、横棒で入れ替えが生じるだけなので、あみだくじの出口が同じになることはありません。

A   B   C
├─┤  │
B   A   C
│  ├─┤
B   C   A
│  ├─┤
B   A   C
├─┤  │
A   B   C

feenalさんも指摘していますが、よく知られているようにあみだくじと「置換」は同じものです。

n本のあみだくじの場合 1,2,3,4,...,n-1,n という数列に対して置換の操作を行うことと同じです。

一番単純なあみだくじは「恒等置換」idです。何もしません。

1 2 3 ... n-1 n
| | | ...  |  |
1 2 3 ... n-1 n

次に単純なあみだくじは横棒一つのあみだくじでこれは「互換」(k,k+1) (kとk+1の入れ替え)と同じです。

1 2 3 ...  k k+1 ... n-1 n
| | | ...  |  |  ...  |  |
| | | ...  |--|  ...  |  |
| | | ...  |  |  ...  |  |
1 2 3 ... k+1 k  ... n-1 n

1. 横棒一つのあみだくじ（互換）ではどの入り口からスタートしても別の出口にたどり着きます。
2. どのようなあみだくじも互換の繰り返しです（または恒等置換）。
3. よってどのようなあみだくじでも、別の入り口からスタートすれば別の出口にたどり着きます。

互換、置換、あみだくじで検索するといろいろ見つかると思います。

では、数学を使って小難しく説明してみましょう。

まずは「あみだくじ」の定義から。

「あみだくじ」とは、平行に並んだ有限個の同じ長さの縦棒の列 および有限個の横棒の集合 であるとします。横棒 は正規化された縦棒の位置 および縦棒 からなります（横棒は隣り合った縦棒と縦棒をつなぎ、それぞれの縦棒と直交していると仮定）。ただし、任意の に対して、 が成り立つとします（交点の重複回避）。

任意の「あみだくじ」 に対して、横棒の集合 の中から、最小の を持つ を選びます。このときの を とおきます。 をもつ は複数考えられますから、それをすべて集めた集合を とおきます。すなわち、 とおきます。このとき、 および は両方とも「あみだくじ」の定義を満たしています。これは の任意の部分集合 に対して が「あみだくじ」であることからすぐに帰結できます。

さて、「あみだくじ」 の入り口と出口を対応させる関数 （ただし、） を定義しましょう。

ただし、 は、 に対する であり、 は、 に対する である。

これが well-defind である（ちゃんと定義されている）ことは、 が を満たすことからわかります。

以上で準備完了です。今回の質問「どのような「あみだくじ」でも、必ず別のゴールに着くことを数学的に証明してください」は、数学的に次のように表されます。

任意の「あみだくじ」 が与えられたとき、 であることを証明せよ。

それでは証明です。

（省略されました。続きを読むにはワッフルワッフルと書き込んでください）

入口Aに対応する出口をA'、

入口Bに対応する出口をB'とします。

このとき、任意にA,Bを取った時、

　「A≠B ならば A'≠B'」（入口が異なれば出口は異なる）

を証明すればいいことになります。

この対偶を取れば、

　「A'=B' ならば A=B」（出口が一緒なら入口も一緒）

であり、これはあみだくじを逆に辿ることにより自明です。

以上で証明完了です。

なにかの本に書いてあった説明です。(何の本だったかは忘れました。)

あみだくじの前提条件

• それぞれのスタートはゴールのいずれかひとつにたどり着く。
• スタートとゴールの数は同じ。

1. 仮定:「同じゴールを持つスタートが複数ある」
2. この仮定に従うと、どのスタートからもたどり着けないゴールAが存在する。
3. ゴールAからあみだくじを逆にたどった場合、いずれかのスタートにたどり着く。ゴールAがどのスタートからもたどり着けないことに矛盾する。
4. 背理法により、仮定:「同じゴールを持つスタートが複数ある」が否定され、必ず別のゴールに着くと証明される。

＞行列以外のアタックも募集中です！

行列を使わずに考えてみました。

あるあみだくじについて、上下対称なあみだくじを作り、元のあみだくじの下に接続して新しいあみだくじを作成します（あみだくじの出口に鏡を置いて、実像と鏡像の全体を一つのあみだくじとみなす）。

このあみだくじでは、入口から中間地点までの経路と、中間地点から出口までの経路は線対称になっています。左からn番目の入口を出発すると左からn番目の出口に到着するので、別々の入口から同じ出口に到着することはありません。

ここで、別々の入口を出発して同じ出口に到着するようなあみだくじが存在すると仮定し、上の手順で新しいあみだくじを作成します。

元のあみだくじで同じ出口に到着するような入口を選ぶと、新しいあみだくじでは、途中で同じ地点を通過しているにもかかわらず別々の出口に到着していることになります。しかし、このようなことは起こり得ません。

したがって、別々の入口を出発して同じ出口に到着するようなあみだくじは存在しません。つまり、どのようなあみだくじでも、必ず別のゴールに着くことが示されました。

x 　：入口番号

y 　：出口番号

f()　：あみだくじの操作

f(x)=y

xの値を定めたときyの値が一意に定まる。

同じ出口に着くのは

f(a)=f(b)=c

と表される。

g()　：f()の逆関数

とすると、

g(c)=aおよびb

とならなければならない。

g()はあみだを下から辿ることであり、上下を引っ繰り返せばあみだそのものである。故に f()と同様「xの値を定めたときyの値が一意に定まる」を満たさなければならない。よって f(a)=f(b)=cは成り立たない。

もう、置換で答えが出ていますが、面白そうなので背理法で挑戦してみましょう。以下のあみだくじを考えます。絵は先に回答された型から拝借しました。

A   B   C
│α│  │
├─┤β│
│  ├─┤
│  │γ│
│δ├─┤
├─┤  │
│  │  │
 a  b   c

ここで、上から下にたどるとき、出口aにたどり着く入り口が二つあると仮定します。

すると、その二つの入り口の経路は、横棒δを必ずたどります。そして、その経路二つの経路は必ず横棒γをたどります。このようにバックトラックしていくと、二つの経路はすべての横棒を共有し、つまり、同じ入り口から入ってきています。これは最初の仮定に矛盾します。

しがたって、仮定が成立することはありません。つまり、異なる入り口が違う出口を共有することはありません。