- 締切済み
同じパターンのシャフルの固有多項式（q=110706の続き）
http://oshiete1.goo.ne.jp/kotaeru.php3?q=110706 の回答に感動して、ネタを続けるための質問なので、あんまり良い質問ではありませんがよろしくお願いします。 N枚のトランプに同じパターンのシャフル操作Sをk回繰り返したとき(S^kと表す)、そのうち元に戻ります(トランプの並べ方のパターンがN! しかないから）。そこで、順番を入れ換えないシャフル(=1=S^n)を与える回数nを求めたいと思います。 まず、カードの軌道のようなものを考えて分類します。１つのカードに着目して、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の場合はx^n-1= g(x)f(x)となる多項式があるということだと思うのですが、そうすると、f(x)ってそうとう形が限られると思うのですが、どうなると思われますか？・・・力不足で質問がつまんない・・・ですが、質問とは関係なく一般のシャフルについて計算するための良い方法があれば教えてください。
- motsuan
- お礼率94% (52/55)
- 数学・算数
- 回答数2
- ありがとう数5
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- jun1038
- ベストアンサー率49% (138/278)
こんばんは。junです。今日は２０回くらいのログインで、やっと回答のところに来ました。ＩＥ４との相性は最悪みたいですね。新しくなったｇｏｏのコンテンツでもこのことについて書いてありましたが、２回でログインできるというのは少なくとも私の場合あてはまりません。本題と関係ない話を長々とすみません。 motsuanさんの質問のしかたが悪いのではなく、やはりこの問題が難しすぎるのでは？一枚ずつ交互にという比較的単純な場合でも多くの人が悩みましたよね。離散対数問題なんて言葉も出てきたし。一般化した場合なんてさらに難しくなるのでしょう？ あるいはこの問題は、「群」に関する典型的な問題になる可能性があり、こんな匿名の掲示板よりも、きちんとした一本の論文に仕上げた方が得だと皆さん思っているのかしら。大学の数学の先生のような、「プロ」の方の意見を聞きたいものです。 私の個人的な意見を少し。motsuanさんの補足の内容は少しは分かりましたが、１２・３４５の場合というのは、何というか周期が２と周期が３の「独立」したシャッフルが同調するのはどういうタイミングか、という、いわば単純な最小公倍数の問題になっているのではありませんか。 私が考えていたのは、むしろ１つ１つの独立したシャッフルが何回で元に戻るかという議論です。各「細胞」の周期が分かればあとは最小公倍数でしょうから。 １つのまとまりのカードの列が、どんな操作（置換）をするときに何回の操作で元に戻るか、ということのほうがより問題の本質だと思うのです。 またまた生意気なことを言ってしまって大変申しわけありません。私は本当に数学に弱いので、motsuanさん始め多くの皆さんのお力が無いとどう考えて行ったらよいかすらよく分からないのです。よろしくお願いします。
- jun1038
- ベストアンサー率49% (138/278)
こんばんは。jun1038です。質問を受け継いで頂き、大変ありがとうございます。もっと早くお礼を言いたかったのですが、なぜがなかなかきちんとログインできませんでした。（今日はなぜかすんなりログインできた） 私、数学にはほとんど素人なので、行列とか固有多項式についての話にはあまりコメントできません。すみません。 素人の強み（？）で、q=110706 のときの様子からの「カン」をいくつか書かせていただきます。 ・すべてのカードは一斉に元に戻るのでは。もし反する例があれば撤回します。 ・ｎ＞Ｎとなる場合はなく、すべてｎ＜Ｎとなるのでは。（これもあくまでq=110706 のときがもとですが） ・任意の操作（例えば最後の２枚を１枚目と２枚目の間に入れる）をいかに数学的に表現するか、そしてその操作の結果カードがどのように置換されるか、といった考え方の方が良いのでは。 生意気なことを言ってすみませんが、皆さまどうぞよろしくお願いします。
お礼
どうもありがとうございます。110706の回答がとてもよかったので質問をあげさせていただきました。 質問がちょっとわかりにくくなってしまったのはよくなかったかなとちょっとお詫びいたします。
補足
どうも変な質問にして、かえって回答が付き難くなってしまったかも知れません。 シャフルのイメージなのですが私のイメージとしては以下のようなものもシャフルと考えています。 たとえば、置換の周期が二つある場合、簡単な例として １２・３４５ を並べ換えて ２１・５４３ というシャフルを考えます（点は見やすいように入れました。１，２枚目の入れ換えと３，４，５枚目の循環の二つの周期を考えます）。これを繰り返すと １２・３４５ ２１・５４３ １２・４５３ ２１・３４５ １２・５４３ ２１・４５３ １２・３４５ となって、６回でもとに戻ります。 こういうシャフルを考えていたのですが、ちょっとイメージが違うのかな？
関連するQ&A
- 偶数枚のトランプのシャッフル
この問題は私が高校生の時に「発見」したものですが、いまだに解けなくて困っています。どなたか数学に強い方解いて下さい。できれば、中・高校生にも分かる解法でお願いします。 ○偶数（２ｎ）枚のトランプがある。これを前半と後半の２つに分け、１枚ずつ互い違いになるように何回かシャッフルすると、最初にトランプのカードが並んでいた状態に戻るようである。 必ず戻るのか、証明せよ。 もしそうなら、トランプの枚数２ｎと、戻るのに要するシャッフルの回数ｍとの関係はどうなるか。 ○少し説明します。 ・トランプ６枚のとき ＡＢＣＤＥＦ＞ＡＤＢＥＣＦ＞ＡＥＤＣＢＦ＞ＡＣＥＢＤＦ＞ＡＢＣＤＥＦ で、４回で元に戻ります。最初のカード（Ａ）と最後のカード（この場合はＦ）はその位置が変わりません。２回シャッフルしたときにアンコの部分がちょうど逆転していて、４回で元に戻ることが予想できます。 ・トランプ８枚のとき ＡＢＣＤＥＦＧＨ＞ＡＥＢＦＣＧＤＨ＞ＡＣＥＧＢＤＦＨ＞ＡＢＣＤＥＦＧＨ で、３回で元に戻ります。回数は６枚のときより少なくなりました。 ・トランプ１０枚のとき ＡＢＣＤＥＦＧＨＩＪ＞ＡＦＢＧＣＨＤＩＥＪ＞ＡＨＦＤＢＩＧＥＣＪ＞ＡＩＨＧＦＥＤＣＢＪ＞ＡＥＩＤＨＣＧＢＦＪ＞ＡＣＥＧＩＢＤＦＨＪ＞ＡＢＣＤＥＦＧＨＩＪ で、６回で元に戻ります。このときも、３回シャッフルしたときに中身の部分が逆転しています。 ・いろいろやってみると、（１）おおよそ、枚数２ｎが増えるほど、元に戻るまでのシャッフルの回数ｍは増加する傾向がある。（２）しかし、２ｎが２の累乗（４，８，１６・・・）のときには回数が減るようである。 ということは分かっているのですが・・・・。どなたかよろしくお願いします。
- ベストアンサー
- 数学・算数
- M系列の生成多項式と原始多項式について
生成多項式や原始多項式に関する様々な投稿を見ましたが、 いまいち知りたいことがわからなかったので質問いたします。 周期 2^n - 1 のM系列を生成するには、{0,1}を体とする n次の原始多項式を生成多項式として用いるということまでは わかったのですが、このn次の原始多項式の求め方について、 いまいち理解できません。 例えば、周期 2^4 - 1 = 15のM系列を生成するには原始多項式 x^4 + x^1 + 1 ー (1) を用いるということですが、 x^4 + x^2 + 1 ー (2) ではM系列を生成できませんでした。 この２式の違いを理解していないことが原始多項式の求め方を 理解できない原因だと思うのですが、どなたかお詳しい方がいましたら、 ご教授お願いいたします。
- ベストアンサー
- 数学・算数
- 数学II 多項式の割り算
数学II 多項式の割り算 nを自然数とし、多項式fn(x)=Σ[k=0→n-1]x^kと定める。 x^2010をfn(x)で割るとき、余りが1となるnはいくつあるか。 という問題があります。 どうやって解いていいかわかりません。 とりあえず、自分の考えを載せておきます。これでできませんか? ～～～～～～～～～～～～～～～～～～～ mod fn(x)において、 (x-1)fn(x)=x^n-1より、x^n≡1 ゆえに、x^2010=(x^n)^m(mは自然数)とすると、 x^2010≡1となればよい。 2010=2*3*5*67なので、2010の約数の数は、2*2*2*2=16個 nも2010の約数の時、x^2010≡1となる。（ただし、f1(x)は定数のため、余りは0） したがって、題意をみたすnは、16-1=15個 となりました。 解答がなく、しかも正解の値が分からないので、このやり方でやっていけるのかどうかすらわかりません。 nに適当な値を代入していくと、なんだか矛盾してくる気がしてなりません。 特に、mが自然数と決めつけてしまったところもやや怪しい気がします。 誰か教えてください！
- ベストアンサー
- 数学・算数
- 行列の固有値問題
以下の証明はどのように行えばいいのでしょうか。 ｎ次多項式f(s)=ａ(n)ｓ^n ＋ ａ(n-1)ｓ^(n-1) ＋ ・・・・ ＋ａ(1)ｓ ＋ ａ(0)とする。 行列Ａ(ｎ×ｎの正方行列)の固有値がλ１、λ２、・・・、λｎであるとき、行列多項式f(A)の固有値はf(λ1)、f(λ2)、・・・、f(λn)であることを、任意のｎ次正方行列は適当な正則行列ＱによってＱ^(-1)ＡＱが下三角行列になるようにできることと、下三角行列の固有値は対角成分になることを用いて示せ。 という問題です。分かりにくくてすいません。 行列多項式というものが初めて目にする言葉ですし、方針が立ちません。 よろしくお願いします。
- 締切済み
- 数学・算数
- 補間多項式
「相異なる点、x_0,x_1,・・・・,x_nに対して、任意の実数y_0,y_1,・・・,y_nがある。そのときp_n+1(x_i)=y_i(i=0,1,・・・,n)を満たす高々n+1次の補間多項式p_n+1がただ一つ存在する。」は真か偽を判定する問題です。考えたのですが偽でしょうか？定義は「与えられた関数y=f(x)に対して、相異なる点x_0,・・・,x_n-1（この点を標本点という）について、y_k=f(x_k),k=0,1,・・・,n-1とおく。このとき高々n-1次多項式p(x)としてp(x_k)=y_k,k=0,1,・・・,n-1となるものがある」理由はやはり高々n+1次というところが定義からづれているからです。しかし根拠が示せないので、アドバイスありましたら嬉しいです・・・
- 締切済み
- 数学・算数
- 超高次の多項式の原始関数を求めたいのですが
f(x) = (n-x)(n-1-x)(n-2-x).....(n-m-x) n: 大きな自然数(例えば1000000など) m: n>mの大きな自然数(例えば100000など) という多項式 f(x)の原始関数を高速に求めるアルゴリズムを考えて います． f(x)を具体的に展開してから原始関数を求めれば簡単だと思い，上記 の式を展開するプログラムを書いたのですが，組み合わせの計算を する必要が生じて，mの値が大きな時に高速に計算できませんでした． 原始関数を直接導出しようと，いろいろ場合分けして考えてみたので すが挫折しました． アドバイス頂けませんでしょうか？ よろしくお願いします．
- ベストアンサー
- 数学・算数
- 急減少関数に多項式をかけても急減少関数？
f∈S(R)であることを fが無限回微分可能なR上の関数でかつ 任意の非負整数m、nに対して | (1+|x|)^m * f^(n) (x) |≦c_{m,n} x∈R を満たす正数c_{m,n}が存在する と定義すると、 f∈S(R)かつp(x)が多項式ならばp(x)f(x)∈S(R)であることを示せ っていう問題で、 ヒントとしてLeibnizの公式を使うとあるのですが どのようにすればよいのかわかりません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
どうもありがとうございます。 補足の表記が間違っていて趣旨を汲んでいただけるか心配だったのですが、その心配はなかったようで、ありがとうございました。 ところで、 >「群」に関する典型的な問題になる可能性があり、 についてですが、 質問の部分的な周期の最大公約数になるという部分については ごく普通の有限アーベル群は巡回部分群の直積に分解されるという事情を表しているのだと思います。 あちこち漫然と書き散らして申し訳ありませんがよろしくお願いします。
補足
ごめんなさいややこしくしてしまって。 例示が間違っていて真に恐縮なのですが （自分で自分の質問に答えられない＝訂正できないのです）、 本質的に、こういう周期列のあつまりに分けられるという主張です。 >最小公倍数の問題になっているのではありませんか。 というより、そういう具合い必ず分けることができるという主張です。 １２・３４５ ２１・５３４（と書こうとおもっていました） というふうに単純にみえなくっても １２３４５ ５４２３１、 あるいは １２３４５ ４５２１３ でもおなじですよね。なんでおなじかというと同じ周期でかつその入れ換えの集合見たいのが同じだからです。そういう意味です。 実際の場合は１つのカードを追い掛けてn1回でもとにもどれば、N-n1枚のカードから更に１枚選んで、その軌跡を追い掛けてn2回でもとにもどるとするとN-n1-n2枚のカードから一つ選んでそのカードの軌跡を追い掛けるという方法なので、効率としては現実的な範囲かなと思ったわけです。 １２３４５ １４２５３ でつづけて １５４３２ １３５２４ １２３４５ でもいいのですが、そのときは １枚目が周期１ ２枚目が軌道として ２、３、５、４、繰り返し ３枚目が軌道として ５，４、２，３、繰り返し という具合にすべてのカードが同じ周期で同じ軌道上にありますよね。 こういう状態を使えば少し計算が楽になりますが、もっと良い方法はないかと考えています。 シャフルのイメージが違うのでしょうか？ というわけでみなさまアドバイスなどよろしくお願いいたします。