No.3ベストアンサー
- 回答日時:
過去にも同じような質問があるようです。
過去の質問では・当りが必ずあること、ダブらないこと
を証明するものでしたが、今回は加えて
・あみだくじの横線を追加すればどんな置換でも必ず表せる
の証明なので、余分な手間がかかって少し難しくなってい
るかも知れません。しかし、同じようなレベルの問題が2つになった
のと同じようなものかも知れません。一応残り(2つのうちの後半)
部分も含めて書きますが、詳しい証明は省略します。
先ず、あみだくじを厳密に定義する必要があります。
あみだくじには道筋(行き先を決定する過程)を複雑にするために
a.隣り合う横の線をある位置で水平に結ぶ
b.バイパスさせて隣り合わない任意の2つの線をある位置で水平に
結ぶ
c.上の2つの操作を水平でない線によって行う
またはこれと同等な操作ですが、2つの線を選んでその各々のある
位置で小さい分岐路を作りその先にまるばつさんかくなどの共通の
記号をふっておいて道筋をたどるときにその共通記号までジャンプ
させる
などがありますが、どこまで採用するかは本問題を証明する観点からは
大きな影響は与えないようです。しかし、その範囲ははっきりさせて
おく必要はあります。(今回はたまたま操作c無しで可能ですが、場合
によっては操作cが無いと実はある置換は表現できないと言うこともあ
り得ますから。)
その上で以下のような点を証明すればよいと思います。
1)1:1でかつ漏れがないこと
何人もが同時に当たりにならないことを示すにはこれを証明しなけ
ればなりません。また、あみだくじが置換を表すためにはこの条件
を満たしている必要があります。
n本の線を考えて、上で示した操作を施した後、線をたどるとき、
どの線上端の点を選んでも必ずいずれかの線の下端にたどり着く
こととどの線の下端を選んでも必ずいずれかの線の上端からたどる
道筋があること。それからそのようなたどる道筋がそれぞれ1本の
みである事を、あみだくじの定義に基づいて成立することを示すこ
とが必要です。
2)置換の場合はその定義から置き換える全てのケースを含んでいます
が、あみだくじの場合はそれは保証されていませんので、定義(規
約)から出発してそれを示す必要があります。これは次のように考
えて証明できるのではないかと思います。
・任意の置換は互換の積で表される。
・任意の互換に対応するあみだくじを作ることが出来る
・ある置換に対応するあみだくじが存在する場合、
その置換と任意の互換の積によって出来る新しい置換に対し、
既存のあみだくじに、上に述べた筋道の複雑化の操作を適当に
追加して新しい置換に対応するような新しいあみだくじを作る
ことが出来る
・以上を組み合わせて任意の置換に対応するあみだくじを作ること
が出来る
1)、2)を示せば目的は達成できたことになると思いますが、
これはいずれも比較的容易だと思います。
2本の線を結ぶ場合に操作a、bまでを許し、かつ同一高さで結ぶこと
を許さないなら、上からある高さまで下った時点で最初の出発点がどの線
に入れ替わっているかによりその時点の入れ替えの状態を定義する事が出
来るのと、次にどの入れ替えが行われるかが規定できるので(上の条件を
満たす)任意のあみだくじに対して対応する置換を互換の積で表す時に積
の表現形式(冗長さも含めて)も一意に決められますが、操作cを許す場
合はこれは成り立たず、積の表現形式を対応させること自体が不可能にな
ると思います。しかし、このことは上の証明には影響を与えません。上の
証明では表現形式の対応付けは要求しておらず(表現形式の対応付けが出
来る出来ないに拘わらず)、任意の互換を付け足して出来る新しい置換に
対して適当なあみだくじ側の追加操作により新しい置換に対応するあみだ
くじを作れると言っているだけです。更に言うなら、「あみだくじには
いろいろな操作が用意されているが、置換を表すなら操作aだけで十分」
と言うことが証明できます。(互換を表す操作、新しい置換を表すための
追加操作が操作aで出来ることを示せばOKだが、上の証明2)を具体的
に行うときはそのようになります。)
とても丁寧な回答をありがとうございます
急いでいたもので過去の質問をきっちり把握しておりませんでしたスミマセン
助かりました
本当にありがとうございました
No.2
- 回答日時:
前に同じような質問があって
その中で僕が置換とあみだくじの同値性について証明しているので
参考にしてください
参考URL:http://oshiete1.goo.ne.jp/kotaeru.php3?q=180014
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
あみだくじ
数学
-
固有値は幾何的にはどういう意味がある?
数学
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
素数の性質
-
数学の証明問題で、「証明終了」...
-
兄弟の子どもの養子縁組は可能...
-
(4^n)-1が3の倍数であることの...
-
一様連続の証明
-
婿養子に入ったのに出て行けと...
-
3,4,7,8を使って10を作る
-
証明終了の記号。
-
「証明証」と「証明書」はどう...
-
2のn乗根で、 nを無限大に持っ...
-
実息とは?
-
コラッツ予想の証明してみました。
-
ゴールドバッハ予想はナンセン...
-
数学的帰納法を使えないとき
-
よって・ゆえに・したがって・∴...
-
婿養子です、妻と離婚して妻の...
-
なぜ独身だと養子が持てないの...
-
有理数と無理数が無限個あること
-
ブール環
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
素数の性質
-
数学の「証明」のときなどの接...
-
3,4,7,8を使って10を作る
-
数学の証明問題で、「証明終了」...
-
夫が亡くなった後の義理家族と...
-
「証明証」と「証明書」はどう...
-
素数の積に1を加算すると素数で...
-
婿養子です、妻と離婚して妻の...
-
親の再婚相手との問題です。私...
-
証明終了の記号。
-
(4^n)-1が3の倍数であることの...
-
婿養子に入ったのに出て行けと...
-
実息とは?
-
よって・ゆえに・したがって・∴...
-
無理数って二乗しても有理数に...
-
47歳、母親の再婚を子供の立場...
-
再婚、奨学金
-
ゴールドバッハ予想について考...
-
正解が一つとは限らない数学の...
-
再婚を考えてますが、養子縁組...
おすすめ情報