スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

元に戻る?

クラスメートが面白い問題を出してきたので。


【問題】
ルービックキューブに、一回または複数回の回転を組み合わせた試行を与えるとする。
このとき、同じ試行を連続で有限回行えば、必ず元の色の配列に戻ることを示せ。

※注意
回転させるときは、回転させる行または列以外は固定したままとし、
同じ回転とは、回転させる行または列の位置が、ルービックキューブの色の配列に関係なく、
空間的に等しい場所であり、回転方向が同じであるものとする。



解答は、つづきで。

【解答】
ルービックキューブの始めの状態をAとする。
さて、ルービックキューブの色の配列は有限通りしかない。よって、試行を有限回繰り返すなかで、「以前に出現したのと同じ状態が現れる」…①のは明らかである。ここで、①が始めて起こったときの状態をXとする。

以下、帰納法で示す。
問題文の題意が成立しないような、Aと試行が存在したとして、以下この元で考える。
このとき、二回目にXが現れるまでのルービックキューブの状態は、試行を→で表すとすれば、
A→…→X→…→Xとなり、ここで現れる全状態は、仮定より初めのAを除き、すべてAでない。

しかし、試行に対して、回転の仕方を全く逆にした逆試行が存在することに注意すると、
一回目のXに対して逆試行を与えてAに戻すのに必要な回数と、二回目のXに対して逆試行を与えて
Aに戻すのに必要な回数が異なることになり、これは同じ状態に対して同じ試行をすれば同じ状態を得る、
ということに矛盾する。

よって、題意は成立する。



面白いのは、このように
ありうる状態が有限個であり、写像にたいして逆写像が存在すれば(全単射)、
同じことがおこるということです。

だから、例えば
積まれたトランプに対して、1番目に上のカードは下から8番目に、2番目に上のカードは下から13番目に、
3番目に上のカードは下から20番目にする。といったような、複雑そうな変換でも結局は元に戻るのです。

(どちらかが欠けていてもダメです。
①前者が満たされてない場合
たとえば、整数の中で、ある整数に1を足すという写像を何回かけても元の整数には戻りません。
逆写像は、「-1を足す」として存在します。

②後者が満たされてない場合
たとえば、1~10の有限個の整数のなかで、ある整数に対して
「10未満なら1を足して、10ならそのまま」という写像を何回かけても、最初の整数が10でなければ元に戻りません。)

結局、結論としては数学的に抽象的に言えば、

同じ置換を有限回合成することで、恒等置換にすることができる。
【6/12 修正】
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

SHUN

Author:SHUN

アクセス数
最近の記事とコメント
カレンダー
08 | 2017/09 | 10
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
月別アーカイブ
カテゴリ
Vocaloid Ranking Watcher
全記事表示リンク

全ての記事を表示する

Evangelion
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

個人的 神曲
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。