OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

おねがいします!!!!!

  • すぐに回答を!
  • 質問No.213312
  • 閲覧数89
  • ありがとう数5
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 100% (7/7)

線形の問題です
すべての置換があみだくじで表せることを示せ
なんとなくはわかるのですが、うまく言葉にできません
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.3
レベル9

ベストアンサー率 75% (28/37)

 過去にも同じような質問があるようです。過去の質問では
・当りが必ずあること、ダブらないこと
を証明するものでしたが、今回は加えて
・あみだくじの横線を追加すればどんな置換でも必ず表せる
の証明なので、余分な手間がかかって少し難しくなってい
るかも知れません。しかし、同じようなレベルの問題が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)を具体的
に行うときはそのようになります。)
お礼コメント
risayan

お礼率 100% (7/7)

とても丁寧な回答をありがとうございます
急いでいたもので過去の質問をきっちり把握しておりませんでしたスミマセン
助かりました
本当にありがとうございました
投稿日時 - 2002-02-07 23:20:55
-PR-
-PR-

その他の回答 (全2件)

  • 回答No.1
レベル11

ベストアンサー率 27% (103/370)

変換(線形)前後の点は1対1に対応する、ということではないでしょうか? 例えば、1つの点を変換したときに2つ以上の点に移ることはないし、また2つ以上の点が変換後に1点に集まることはありません。 あみだくじも、スタートとゴールで1対1に対応しているということで、そのような意味で同じことだということだと思います。 ...続きを読む
変換(線形)前後の点は1対1に対応する、ということではないでしょうか?
例えば、1つの点を変換したときに2つ以上の点に移ることはないし、また2つ以上の点が変換後に1点に集まることはありません。
あみだくじも、スタートとゴールで1対1に対応しているということで、そのような意味で同じことだということだと思います。
お礼コメント
risayan

お礼率 100% (7/7)

簡単に言うとそうなんですね!
うんうん納得!!
わかりやすく教えていただいてありがとうございました!
投稿日時 - 2002-02-07 23:26:24

  • 回答No.2
レベル9

ベストアンサー率 64% (11/17)

前に同じような質問があって その中で僕が置換とあみだくじの同値性について証明しているので 参考にしてください ...続きを読む
前に同じような質問があって
その中で僕が置換とあみだくじの同値性について証明しているので
参考にしてください
お礼コメント
risayan

お礼率 100% (7/7)

ごめんなさい過去の質問をきっちり見てませんでした
非常に助かりました
ありがとうございました
投稿日時 - 2002-02-07 23:24:12
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ