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

同じパターンのシャフルの固有多項式(q=110706の続き)

  • 暇なときにでも
  • 質問No.112150
  • 閲覧数39
  • ありがとう数5
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 94% (52/55)

http://oshiete1.goo.ne.jp/kotaeru.php3?q=110706
の回答に感動して、ネタを続けるための質問なので、あんまり良い質問ではありませんがよろしくお願いします。

N枚のトランプに同じパターンのシャフル操作Sをk回繰り返したとき(S^kと表す)、そのうち元に戻ります(トランプの並べ方のパターンがN! しかないから)。そこで、順番を入れ換えないシャフル(=1=S^n)を与える回数nを求めたいと思います。

まず、カードの軌道のようなものを考えて分類します。1つのカードに着目して、S^n1でもとの位置に戻るとします。そのときできる軌道上にはn1個のカードの位置があり、それらはすべてS^n1でもとの位置に戻るのが分かります。こうやって、カードの位置を、n1のグループ、n2のグループ、・・・で分けて、それらの最小公倍数 n でS^n=1となるはずです。(実際の計算ではこれで済むと思うのですが、q=110706のように一般的な式で表すとするとこれじゃだめなんでしょうね。)すると、n>Nとなる場合が多々ある気がします。一方、 行列Aの (m, n) 成分 (m,n = 0,1,2,...,N-1) を、シャフル前に n 番目にあったカードがシャフルで m 番目に移されるとき:1 、それ以外:0 として表現して固有多項式f(x)を求めると、N次式になります。さてさて、n>Nの場合はx^n-1= g(x)f(x)となる多項式があるということだと思うのですが、そうすると、f(x)ってそうとう形が限られると思うのですが、どうなると思われますか?・・・力不足で質問がつまんない・・・ですが、質問とは関係なく一般のシャフルについて計算するための良い方法があれば教えてください。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全2件)

  • 回答No.1
レベル11

ベストアンサー率 49% (138/278)

 こんばんは。jun1038です。質問を受け継いで頂き、大変ありがとうございます。もっと早くお礼を言いたかったのですが、なぜがなかなかきちんとログインできませんでした。(今日はなぜかすんなりログインできた)  私、数学にはほとんど素人なので、行列とか固有多項式についての話にはあまりコメントできません。すみません。  素人の強み(?)で、q=110706 のときの様子からの「カン」をいくつか書かせていた ...続きを読む
 こんばんは。jun1038です。質問を受け継いで頂き、大変ありがとうございます。もっと早くお礼を言いたかったのですが、なぜがなかなかきちんとログインできませんでした。(今日はなぜかすんなりログインできた)
 私、数学にはほとんど素人なので、行列とか固有多項式についての話にはあまりコメントできません。すみません。
 素人の強み(?)で、q=110706 のときの様子からの「カン」をいくつか書かせていただきます。
 ・すべてのカードは一斉に元に戻るのでは。もし反する例があれば撤回します。
 ・n>Nとなる場合はなく、すべてn<Nとなるのでは。(これもあくまでq=110706 のときがもとですが)
 ・任意の操作(例えば最後の2枚を1枚目と2枚目の間に入れる)をいかに数学的に表現するか、そしてその操作の結果カードがどのように置換されるか、といった考え方の方が良いのでは。

 生意気なことを言ってすみませんが、皆さまどうぞよろしくお願いします。
補足コメント
motsuan

お礼率 94% (52/55)

どうも変な質問にして、かえって回答が付き難くなってしまったかも知れません。
シャフルのイメージなのですが私のイメージとしては以下のようなものもシャフルと考えています。
たとえば、置換の周期が二つある場合、簡単な例として
12・345
を並べ換えて
21・543
というシャフルを考えます(点は見やすいように入れました。1,2枚目の入れ換えと3,4,5枚目の循環の二つの周期を考えます)。これを繰り返すと
12・345
21・543
12・453
21・345
12・543
21・453
12・345
となって、6回でもとに戻ります。
こういうシャフルを考えていたのですが、ちょっとイメージが違うのかな?
投稿日時 - 2001-08-03 07:35:45
お礼コメント
motsuan

お礼率 94% (52/55)

どうもありがとうございます。110706の回答がとてもよかったので質問をあげさせていただきました。
質問がちょっとわかりにくくなってしまったのはよくなかったかなとちょっとお詫びいたします。
投稿日時 - 2001-08-03 07:42:02


  • 回答No.2
レベル11

ベストアンサー率 49% (138/278)

 こんばんは。junです。今日は20回くらいのログインで、やっと回答のところに来ました。IE4との相性は最悪みたいですね。新しくなったgooのコンテンツでもこのことについて書いてありましたが、2回でログインできるというのは少なくとも私の場合あてはまりません。本題と関係ない話を長々とすみません。  motsuanさんの質問のしかたが悪いのではなく、やはりこの問題が難しすぎるのでは?一枚ずつ交互にという比較 ...続きを読む
 こんばんは。junです。今日は20回くらいのログインで、やっと回答のところに来ました。IE4との相性は最悪みたいですね。新しくなったgooのコンテンツでもこのことについて書いてありましたが、2回でログインできるというのは少なくとも私の場合あてはまりません。本題と関係ない話を長々とすみません。
 motsuanさんの質問のしかたが悪いのではなく、やはりこの問題が難しすぎるのでは?一枚ずつ交互にという比較的単純な場合でも多くの人が悩みましたよね。離散対数問題なんて言葉も出てきたし。一般化した場合なんてさらに難しくなるのでしょう?
 あるいはこの問題は、「群」に関する典型的な問題になる可能性があり、こんな匿名の掲示板よりも、きちんとした一本の論文に仕上げた方が得だと皆さん思っているのかしら。大学の数学の先生のような、「プロ」の方の意見を聞きたいものです。
 私の個人的な意見を少し。motsuanさんの補足の内容は少しは分かりましたが、12・345の場合というのは、何というか周期が2と周期が3の「独立」したシャッフルが同調するのはどういうタイミングか、という、いわば単純な最小公倍数の問題になっているのではありませんか。
 私が考えていたのは、むしろ1つ1つの独立したシャッフルが何回で元に戻るかという議論です。各「細胞」の周期が分かればあとは最小公倍数でしょうから。
 1つのまとまりのカードの列が、どんな操作(置換)をするときに何回の操作で元に戻るか、ということのほうがより問題の本質だと思うのです。
 またまた生意気なことを言ってしまって大変申しわけありません。私は本当に数学に弱いので、motsuanさん始め多くの皆さんのお力が無いとどう考えて行ったらよいかすらよく分からないのです。よろしくお願いします。
補足コメント
motsuan

お礼率 94% (52/55)

ごめんなさいややこしくしてしまって。

例示が間違っていて真に恐縮なのですが
(自分で自分の質問に答えられない=訂正できないのです)、
本質的に、こういう周期列のあつまりに分けられるという主張です。
>最小公倍数の問題になっているのではありませんか。
というより、そういう具合い必ず分けることができるという主張です。
12・345
21・534(と書こうとおもっていました)
というふうに単純にみえなくっても
12345
54231、
あるいは
12345
45213
でもおなじですよね。なんでおなじかというと同じ周期でかつその入れ換えの集合見たいのが同じだからです。そういう意味です。
実際の場合は1つのカードを追い掛けてn1回でもとにもどれば、N-n1枚のカードから更に1枚選んで、その軌跡を追い掛けてn2回でもとにもどるとするとN-n1-n2枚のカードから一つ選んでそのカードの軌跡を追い掛けるという方法なので、効率としては現実的な範囲かなと思ったわけです。
12345
14253
でつづけて
15432
13524
12345
でもいいのですが、そのときは
1枚目が周期1
2枚目が軌道として
2、3、5、4、繰り返し
3枚目が軌道として
5,4、2,3、繰り返し
という具合にすべてのカードが同じ周期で同じ軌道上にありますよね。
こういう状態を使えば少し計算が楽になりますが、もっと良い方法はないかと考えています。
シャフルのイメージが違うのでしょうか?

というわけでみなさまアドバイスなどよろしくお願いいたします。
投稿日時 - 2001-08-04 01:43:04
お礼コメント
motsuan

お礼率 94% (52/55)

どうもありがとうございます。
補足の表記が間違っていて趣旨を汲んでいただけるか心配だったのですが、その心配はなかったようで、ありがとうございました。

ところで、
>「群」に関する典型的な問題になる可能性があり、
についてですが、
質問の部分的な周期の最大公約数になるという部分については
ごく普通の有限アーベル群は巡回部分群の直積に分解されるという事情を表しているのだと思います。
あちこち漫然と書き散らして申し訳ありませんがよろしくお願いします。
投稿日時 - 2001-08-04 02:10:37
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

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

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

特集


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

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ