おねがいします！！！！！

線形の問題です
すべての置換があみだくじで表せることを示せ
なんとなくはわかるのですが、うまく言葉にできません

No.3 ベストアンサー 回答者： tgb 回答日時： 2002/02/07 19:51

　過去にも同じような質問があるようです。

過去の質問では
・当りが必ずあること、ダブらないこと
を証明するものでしたが、今回は加えて
・あみだくじの横線を追加すればどんな置換でも必ず表せる
の証明なので、余分な手間がかかって少し難しくなってい
るかも知れません。しかし、同じようなレベルの問題が２つになった
のと同じようなものかも知れません。一応残り（２つのうちの後半）
部分も含めて書きますが、詳しい証明は省略します。

　先ず、あみだくじを厳密に定義する必要があります。
あみだくじには道筋（行き先を決定する過程）を複雑にするために
ａ．隣り合う横の線をある位置で水平に結ぶ
ｂ．バイパスさせて隣り合わない任意の２つの線をある位置で水平に
　　結ぶ
ｃ．上の２つの操作を水平でない線によって行う
　またはこれと同等な操作ですが、２つの線を選んでその各々のある
　位置で小さい分岐路を作りその先にまるばつさんかくなどの共通の
　記号をふっておいて道筋をたどるときにその共通記号までジャンプ
　させる
などがありますが、どこまで採用するかは本問題を証明する観点からは
大きな影響は与えないようです。しかし、その範囲ははっきりさせて
おく必要はあります。（今回はたまたま操作ｃ無しで可能ですが、場合
によっては操作ｃが無いと実はある置換は表現できないと言うこともあ
り得ますから。）

　その上で以下のような点を証明すればよいと思います。
１）１：１でかつ漏れがないこと
　　何人もが同時に当たりにならないことを示すにはこれを証明しなけ
　　ればなりません。また、あみだくじが置換を表すためにはこの条件
　　を満たしている必要があります。
　　ｎ本の線を考えて、上で示した操作を施した後、線をたどるとき、
　　どの線上端の点を選んでも必ずいずれかの線の下端にたどり着く
　　こととどの線の下端を選んでも必ずいずれかの線の上端からたどる
　　道筋があること。それからそのようなたどる道筋がそれぞれ１本の
　　みである事を、あみだくじの定義に基づいて成立することを示すこ
　　とが必要です。
２）置換の場合はその定義から置き換える全てのケースを含んでいます
　　が、あみだくじの場合はそれは保証されていませんので、定義（規
　　約）から出発してそれを示す必要があります。これは次のように考
　　えて証明できるのではないかと思います。
　　・任意の置換は互換の積で表される。
　　・任意の互換に対応するあみだくじを作ることが出来る
　　・ある置換に対応するあみだくじが存在する場合、
　　　　その置換と任意の互換の積によって出来る新しい置換に対し、
　　　　既存のあみだくじに、上に述べた筋道の複雑化の操作を適当に
　　　　追加して新しい置換に対応するような新しいあみだくじを作る
　　　　ことが出来る
　　・以上を組み合わせて任意の置換に対応するあみだくじを作ること
　　　が出来る

　１）、２）を示せば目的は達成できたことになると思いますが、
これはいずれも比較的容易だと思います。

　２本の線を結ぶ場合に操作ａ、ｂまでを許し、かつ同一高さで結ぶこと
を許さないなら、上からある高さまで下った時点で最初の出発点がどの線
に入れ替わっているかによりその時点の入れ替えの状態を定義する事が出
来るのと、次にどの入れ替えが行われるかが規定できるので（上の条件を
満たす）任意のあみだくじに対して対応する置換を互換の積で表す時に積
の表現形式（冗長さも含めて）も一意に決められますが、操作ｃを許す場
合はこれは成り立たず、積の表現形式を対応させること自体が不可能にな
ると思います。しかし、このことは上の証明には影響を与えません。上の
証明では表現形式の対応付けは要求しておらず（表現形式の対応付けが出
来る出来ないに拘わらず）、任意の互換を付け足して出来る新しい置換に
対して適当なあみだくじ側の追加操作により新しい置換に対応するあみだ
くじを作れると言っているだけです。更に言うなら、「あみだくじには
いろいろな操作が用意されているが、置換を表すなら操作ａだけで十分」
と言うことが証明できます。（互換を表す操作、新しい置換を表すための
追加操作が操作ａで出来ることを示せばＯＫだが、上の証明２）を具体的
に行うときはそのようになります。）

この回答へのお礼

とても丁寧な回答をありがとうございます
急いでいたもので過去の質問をきっちり把握しておりませんでしたスミマセン
助かりました
本当にありがとうございました

お礼日時：2002/02/07 23:20

No.2 回答者： hismix 回答日時： 2002/02/07 17:06

前に同じような質問があって

その中で僕が置換とあみだくじの同値性について証明しているので
参考にしてください

参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?q=180014

この回答へのお礼

ごめんなさい過去の質問をきっちり見てませんでした
非常に助かりました
ありがとうございました

お礼日時：2002/02/07 23:24

No.1 回答者： hiromuy 回答日時： 2002/02/07 12:04

変換（線形）前後の点は１対１に対応する、ということではないでしょうか？

例えば、１つの点を変換したときに２つ以上の点に移ることはないし、また２つ以上の点が変換後に１点に集まることはありません。
あみだくじも、スタートとゴールで１対１に対応しているということで、そのような意味で同じことだということだと思います。

この回答へのお礼

簡単に言うとそうなんですね！
うんうん納得！！
わかりやすく教えていただいてありがとうございました！

お礼日時：2002/02/07 23:26