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

回答の条件
  • 1人2回まで
  • 登録:2007/08/29 00:06:33
  • 終了:2007/09/02 12:28:44

ベストアンサー

id:yo-kun No.13

yo-kun回答回数220ベストアンサー獲得回数302007/09/01 12:56:30

ポイント30pt

では横棒の数nに関する数学的帰納法ではどうでしょう。


縦棒をm本とし、便宜的に入口・出口に左から番号を振り

入口の集合をA=\left{ a_1,a_2,\cdots,a_m \right}

出口の集合をB=\left{ b_1,b_2,\cdots,b_m \right}

とする。

またあみだくじTによって入口a_iが出口b_jに出ることをT(a_i)=b_jと表す。

つまりあみだくじとは写像T : A \to Bを定義することである。

従って、次の命題を証明することにほかならない。


命題:横棒の数がn本からなる任意のあみだくじで定義される写像は一対一対応(単射)である。


(i)初期段階

横棒がない(n=0)あみだくじをT_0とすると、

任意のi \left( i=1,\cdots,m \right)に関してT(a_i)=b_iなのでn=0の時、命題は成り立つ


(ii)帰納段階

横棒がk-1本のとき命題は成立すると仮定する。

横棒がk本(k>0)のあみだくじTが与えられた時、

このあみだくじから最下部の横棒を除いた、横棒がk-1本のあみだくじをT_{upper}、縦線と最後の横棒1本だけからなるあみだくじをT_{lower}とする。

まず仮定よりT_{upper}は単射である。

また、T_{lower}も1本の横棒を介しての入れ替えなので明らかに単射である。

従って、合成写像T_{lower} \circ T_{upper}=Tも単射である。


以上証明終わり。

id:heath_yam

完璧な証明ですね。おみごと。

2007/09/02 12:26:09

その他の回答(12件)

id:sukiyaki22 No.1

sukiyaki22回答回数299ベストアンサー獲得回数22007/08/29 00:24:24

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

id:BlackSabbath No.2

BlackSabbath回答回数53ベストアンサー獲得回数42007/08/29 00:33:42

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

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

A   B   C
│  │  │
├─┤  │
│  ├─┤
│  │  │
│  ├─┤
├─┤  │
│  │  │
A'  B'  C'
id:Z9M9Z No.3

Z9M9Z回答回数343ベストアンサー獲得回数112007/08/29 06:31:08

ポイント15pt

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

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

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

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

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

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

id:heath_yam

一番イメージに近いですね。

2007/08/29 21:22:49
id:akagi_paon No.4

akagi_paon回答回数143ベストアンサー獲得回数132007/08/29 18:51:52

ポイント12pt

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

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

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

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

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

id:heath_yam

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

2007/08/29 23:36:18
id:feenal No.5

feenal回答回数2ベストアンサー獲得回数02007/08/30 20:22:43

ポイント21pt

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

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

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

あみだの入り口と出口の数は当然同じ数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!とおりか。

id:heath_yam

おおお!

すごい力作が来ました。行列以外のアタックも募集中です!

2007/08/30 21:32:14
id:uunfo No.6

uunfo回答回数51ベストアンサー獲得回数52007/08/30 22:00:59

ポイント18pt

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

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. よってどのようなあみだくじでも、別の入り口からスタートすれば別の出口にたどり着きます。

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

id:heath_yam

数学的には、数列をn回だけ互換する、と考えるわけですね。

2007/08/30 22:41:22
id:akagi_paon No.7

akagi_paon回答回数143ベストアンサー獲得回数132007/08/31 01:24:50

ポイント18pt

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

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

「あみだくじ」とは、平行に並んだ有限個の同じ長さの縦棒の列 A=\(a_1, a_2, ..., a_n\) および有限個の横棒の集合 B=\{b_1, b_2, ..., b_m\} であるとします。横棒 b = (p,a)\in B は正規化された縦棒の位置 p \in \(0,1\)\subset {\cal R} および縦棒 a\in A からなります(横棒は隣り合った縦棒と縦棒をつなぎ、それぞれの縦棒と直交していると仮定)。ただし、任意の b_1=(p_1,a_i),b_2=(p_2,a_j)\in B に対して、j=i+1 \Rightarrow p_1\neq p_2 が成り立つとします(交点の重複回避)。

任意の「あみだくじ」(A,B) に対して、横棒の集合 B の中から、最小の p を持つ b=(p, a) を選びます。このときの pp_{min} とおきます。 p_{min} をもつ b\in B は複数考えられますから、それをすべて集めた集合を B_{min} とおきます。すなわち、B_{min}=\{b=(p_{min},a)\in B\mid \forall p\(p_{min}\leq p\)\} とおきます。このとき、 (A,B_{min}) および(A,B\setminus B_{min}) は両方とも「あみだくじ」の定義を満たしています。これは B の任意の部分集合 B^\prime\subset B に対して (A,B^\prime) が「あみだくじ」であることからすぐに帰結できます。

さて、「あみだくじ」(A,B) の入り口と出口を対応させる関数 a_y=f(a_x)(ただし、a_x,a_y\in A) を定義しましょう。

f(a_x)=a_x,   if((\forall b_1=(p_1,a_i),b_2=(p_2,a_j)\in B(p_1=p_2)) \wedge (\forall b=(p,a)\in B(a\neq a_x \wedge a\neq a_{x-1})))

f(a_x)=a_{x+1},   if((\forall b_1=(p_1,a_i),b_2=(p_2,a_j)\in B(p_1=p_2)) \wedge (\exist b=(p,a)\in B(a= a_x)))

f(a_x)=a_{x-1},   if((\forall b_1=(p_1,a_i),b_2=(p_2,a_j)\in B(p_1=p_2)) \wedge (\exist b=(p,a)\in B(a= a_{x-1})))

f(a_x)=f^\prime(f_{min}(a_x)),   if(\exist b_1=(p_1,a_i),b_2=(p_2,a_j)\in B(p_1\neq p_2))

ただし、f_{min} は、B_{min} に対する f であり、f^\prime は、B\setminus B_{min} に対する f である。

これが well-defind である(ちゃんと定義されている)ことは、B_{min}\forall b_1=(p_1,a_i),b_2=(p_2,a_j)\in B_{min}(p_1=p_2) を満たすことからわかります。


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

任意の「あみだくじ」(A,B) が与えられたとき、 \forall a_i,a_j\in A(i\neq j \Rightarrow f(a_i)\neq f(a_j)) であることを証明せよ。

それでは証明です。

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

id:heath_yam

ワッフルワッフル

functionが出てくる一番「数学っぽい」力作です

2007/08/31 22:41:53
id:todojun No.8

とどじゅん回答回数1ベストアンサー獲得回数02007/08/31 01:44:44

ポイント12pt

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

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


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

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

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


この対偶を取れば、

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

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


以上で証明完了です。

id:heath_yam

対偶はシンプルですが、上3つの方々と比べるとパワー不足に感じますね

2007/08/31 22:53:25
id:yachi010 No.9

yachi010回答回数7ベストアンサー獲得回数02007/08/31 03:10:45

ポイント12pt

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

あみだくじの前提条件

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

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

背理法登場。シンプルですね

2007/08/31 22:40:26
id:Naoki_M No.10

Naoki_M回答回数18ベストアンサー獲得回数02007/08/31 20:28:23

ポイント12pt

>行列以外のアタックも募集中です!

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

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

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

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

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

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

id:heath_yam

背理法、ですよね。

2007/08/31 22:42:36
id:black3 No.11

black3回答回数9ベストアンサー獲得回数12007/08/31 20:33:24

ポイント18pt

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は成り立たない。

id:heath_yam

シンプルですが分かりやすく、数学っぽい証明ですね!

2007/08/31 22:44:28
id:suikan No.12

酔漢回答回数20ベストアンサー獲得回数02007/08/31 21:47:49

ポイント12pt

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

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

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

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

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

id:heath_yam

背理法3票目(かな)

行列と背理法はもう出尽くした感じですね。

無理やりでもよいので、幾何でも微積分でもなんでも持ってきて証明してみてください(笑)

2007/08/31 22:49:45
id:yo-kun No.13

yo-kun回答回数220ベストアンサー獲得回数302007/09/01 12:56:30ここでベストアンサー

ポイント30pt

では横棒の数nに関する数学的帰納法ではどうでしょう。


縦棒をm本とし、便宜的に入口・出口に左から番号を振り

入口の集合をA=\left{ a_1,a_2,\cdots,a_m \right}

出口の集合をB=\left{ b_1,b_2,\cdots,b_m \right}

とする。

またあみだくじTによって入口a_iが出口b_jに出ることをT(a_i)=b_jと表す。

つまりあみだくじとは写像T : A \to Bを定義することである。

従って、次の命題を証明することにほかならない。


命題:横棒の数がn本からなる任意のあみだくじで定義される写像は一対一対応(単射)である。


(i)初期段階

横棒がない(n=0)あみだくじをT_0とすると、

任意のi \left( i=1,\cdots,m \right)に関してT(a_i)=b_iなのでn=0の時、命題は成り立つ


(ii)帰納段階

横棒がk-1本のとき命題は成立すると仮定する。

横棒がk本(k>0)のあみだくじTが与えられた時、

このあみだくじから最下部の横棒を除いた、横棒がk-1本のあみだくじをT_{upper}、縦線と最後の横棒1本だけからなるあみだくじをT_{lower}とする。

まず仮定よりT_{upper}は単射である。

また、T_{lower}も1本の横棒を介しての入れ替えなので明らかに単射である。

従って、合成写像T_{lower} \circ T_{upper}=Tも単射である。


以上証明終わり。

id:heath_yam

完璧な証明ですね。おみごと。

2007/09/02 12:26:09
  • id:uunfo
    対称性を利用したid:todojunの8の回答が一番シンプルでエレガントでそれゆえ数学的なのに、見かけ倒しの7が数学「っぽい」とみなされているのが面白い。

    13にあるように「必ず別のゴールに着くこと」は数学の言葉では単射という。あみだくじが単射であることを証明すればいい。なお、あみだくじでは入り口の数と出口の数が同じなので「単射⇔全単射」となる。

    4と7はあみだくじの定義と証明すべき命題を述べているだけで証明していない。

    3, 6, 13は帰納法を用いたもので本質的に同じ。

    5,8,9,10,11,12は背理法を用いたもので本質的に同じ(12はやや微妙)。5の行列を使っているのは「写像が全単射⇔写像の行列表現が正則」が背後にある。
  • id:WASSHOI
    ワッフルワッフル
  • id:webpya
    質問者は結局理解できていないまま。
    コピペ人生は後に響きますよ。
  • id:Beirii
    ワッフルワッフル
  • id:uunfo
    数学的帰納法を帰納法と書いてしまったのはちょっとまずかった。反省。

    数学的帰納法を使った証明はあみだくじをある程度構成しなくてはならずそこが個人的には不満で、背理法を使ったものだとあみだくじの詳細には触れずに対称性だけですむので好き。後者の方が一般性も高い。

    定義からほぼ自明なことを証明するのはややこしくなりがちだが、定義と証明すべきことを数式で表してしまえば見やすくなる。

    8を数式にしてみよう。

    Nは自然数の集合とする。
    n本(n∈N)の縦棒からなるあみだくじは
    σ∈S_n={N^n→N^n}
    と書ける.
    あみだくじの定義(省略)から、明らかに(!)
    σ-1∈S_n(σ-1はσの逆写像の意味).
    よって(*)σは単射.■

    *を詳しく書くと
    σ-1∈Sから逆写像σ-1も写像なので
    σ(a)=σ(b)⇒σ-1(σ(a))=σ-1(σ(b))⇒a=b.
    対偶をとると
    a≠b⇒σ(a)≠σ(b).
    すなわちσは単射。


この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません