この問題は私が高校生の時に「発見」したものですが、いまだに解けなくて困っています。どなたか数学に強い方解いて下さい。できれば、中・高校生にも分かる解法でお願いします。
○偶数(2n)枚のトランプがある。これを前半と後半の2つに分け、1枚ずつ互い違いになるように何回かシャッフルすると、最初にトランプのカードが並んでいた状態に戻るようである。 必ず戻るのか、証明せよ。 もしそうなら、トランプの枚数2nと、戻るのに要するシャッフルの回数mとの関係はどうなるか。
○少し説明します。
・トランプ6枚のとき
 ABCDEF>ADBECF>AEDCBF>ACEBDF>ABCDEF で、4回で元に戻ります。最初のカード(A)と最後のカード(この場合はF)はその位置が変わりません。2回シャッフルしたときにアンコの部分がちょうど逆転していて、4回で元に戻ることが予想できます。
・トランプ8枚のとき
 ABCDEFGH>AEBFCGDH>ACEGBDFH>ABCDEFGH で、3回で元に戻ります。回数は6枚のときより少なくなりました。
・トランプ10枚のとき
 ABCDEFGHIJ>AFBGCHDIEJ>AHFDBIGECJ>AIHGFEDCBJ>AEIDHCGBFJ>ACEGIBDFHJ>ABCDEFGHIJ  で、6回で元に戻ります。このときも、3回シャッフルしたときに中身の部分が逆転しています。
・いろいろやってみると、(1)おおよそ、枚数2nが増えるほど、元に戻るまでのシャッフルの回数mは増加する傾向がある。(2)しかし、2nが2の累乗(4,8,16・・・)のときには回数が減るようである。 ということは分かっているのですが・・・・。どなたかよろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (12件中11~12件)

中高校生向けではありませんが。


これは置換という群に関する問題だと思います。
2n枚のトランプの最初の状態を上から順に
1,2,3,4,......,2n
と表現すると、これを
1,n+1,2,n+2,3,n+3,4,......,n,2n
と置換しているのだと考えるのです。
すなわち、
左から2k-1番目の数字をkに置き換え、
左から2k番目の数字をn+kに置き換える、
という置換です。
この置換を何回か繰り返して、元の状態
1,2,3,4,......,2n
に戻るかということですが、うれしいことに
絶対に戻ってくれます。
置換群のことを知っていれば
置換群の要素の個数は有限個であることから、
このことは、さもありなん、まあ当然かな、と思えてしまえます。
もしも置換とか群のことをご存知でないなら
代数学の本の最初のほうを見てみてくださいね。

また、この現象はトランプの枚数が偶数である必要はありません。
2n+1枚のときでも、上からn+1枚を前半、のこりn枚を後半として
同じように何回かシャッフルすると元に戻ります。
さらにさらにすごいことに、どんなシャッフルの仕方でも
何回かやると元に戻るんです!
つまり、たとえば「後ろの2枚を1枚目と2枚目の間に入れる」
という変則的なシャッフルでも元に戻ります。
6枚でやってみましょう。
123456→156234→134562→162345→145623→123456
という風に。(7枚だと元に戻るのははっきり言って当たり前。)
以上のことは、全て置換群の考えで説明できます(多分)。

シャッフルの回数については、よく分かりません。
左から2k-1番目の数字をkに置き換え、
左から2k番目の数字をn+kに置き換える、
という置換が生成する部分群の要素の個数をしらべればいいのでしょうが・・・。

この回答への補足

回答ありがとうございます。
 やはり群が出てきてしまいましたか。私は大学時代理系だったのですが、数学は苦手で、群とか置換の勉強もしていません。もし、群でしか方針が立たないとすれば泣きながら(へたをすると退職後にでも)勉強してみたいと思います。
 むかし、ルービックキューブが流行していたときに、友人と
 「数学科の友達に聞いたんだけれどさ、ルービックキューブは群で解けるそうだぜ」「ふーん(?)」という会話をしたことを思い出しました。ちなみに、キューブはまだわたし全面きれいにはなりません。
 有限回のシャッフルで、有限枚数のトランプが元に戻りそうなのは何となく分かります。が、初歩的な質問で恐縮ですが、「無限ループ」(元の状態には戻らず、いくつかの状態を千日手してしまう)には入りこまないのですか。これも群では常識でしょうか。
 回数については、すみませんが、まさにこの問題の核心なので、
f(2n)=m のfを見つけなさいということなので、よろしくお願いします。
 他力本願ですみません。受験生はみならっちゃダメだよ。

補足日時:2001/07/29 09:08
    • good
    • 0

枚数が2^jの場合だけ、しかも指針だけですが。



シャッフルを関数と捉えます。即ちk番目のカードがfj(k)に移されるとします。即ち
    fj(k) = { 2k-1  (k≦j)
        { 2(k-j) (k>j)        (*)
です。こうすると示すべき問題は
    fj^j(k) = fj(fj(...fj(k)...)) = k    (**)
という式に帰着できます。

1)j=1のとき
    f1(k) = { 1 (k=1)
        { 2 (k=2)
よってj=1の時(**)は成立する。

後は数学的帰納法により任意のjについて(**)が成り立つ事を示せば良いです。

この回答への補足

回答ありがとうございます。
申しわけありませんが、
> fj(k) = { 2k-1  (k≦j)
      { 2(k-j) (k>j) 
というところが、よく分かりません。たとえば、2^3=8ですが、
12345678 → 15263748 で、5番目の5はシャッフルによって2番目の位置にきています。
 f3(5)= 2 というわけですが、上の式では 5>3 ですから
2(5-3)= 4 となりそうなんですが。
私の理解が間違っているとは思いますが、よろしくお願いします。
       

補足日時:2001/07/29 08:59
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qipod shuffleシャッフルは好きな順序でも再生できますか?

はじめまして。
最近、愛用していたipod nanoを紛失してしまったため、
新しくnanoを買おうと思ったのですが、
金銭的にも余裕が無く、
また毎年この時期に新製品が発表されるという噂があるので
もう少しお手ごろなipod shuffleを買ってみようかと思っています。

ただシャッフルがどういったものなのかが良く分からず、
入っている曲がランダムに再生されるものというしか認識がなかった
のですが
「今時のシャッフルは自分の好きな順序でだって聴けるよ」
という意見をネットで一度見たことがあります。

もしそれが本当なら、購入を決定したいのですが、
本当に曲がランダムに再生されるだけだったら…と思うと躊躇してしまいます。
アルバムを通しで聴きたいときなど、不便ではないかと不安です。

もしご存知の方、また実際にお持ちの方がいらっしゃいましたら
教えていただけると助かります。
使ってみた感想などもよろしければお聞きしたいです。

それではご回答お待ちしております。
よろしくお願いいたします。

Aベストアンサー

よく勘違いされる事ですが、Sfuffleも初代から好きな曲順で再生する事可能です。
モニタ無いから曲選ぶのは早送りするしかないけど。

iTunesでプレイリスト作って、それを手動で同期させるだけ。
あとはShuffle本体のスイッチを曲順再生に切り替え下さい。
http://arena.nikkeibp.co.jp/article/col/20050208/110973/?P=2

> また毎年この時期に新製品が発表
尚、9/5頃に新モデルが発表になるという噂です。

Q3/(n+2)(n+5)= 1/3 {<1/(n+2)>-<1/(n+5)>} ???

{1/(n+2)}-{1/(n+5)}=3/(n+2)(n+5)…(1)です。更に
1/3 {<1/(n+2)>-<1/(n+5)>}…(2)
にと変形できるそうです。
読んでいる本に、(1)の分子の3を1にする為に上の変形が紹介されていたのですが、

(1)と(2)は同じ数値、大きさになるのでしょうか? 
分子と分母で数字が同じでも、分子を1にして元々の数字で割ってしまっては(分母に元の数字を)、違う大きさになると思うのですが…
2/1と1/2は違いますし…

Aベストアンサー

A-B=3Cだから、C=(1/3)(A-B)だ、といっているのです。

1/(n+2)-1/(n+5)=3{1/(n+2)(n+5)}だから
1/(n+2)(n+5)=(1/3){1/(n+2)-1/(n+5)}になりますよということ。
(2)の方の式に等号がありませんが、左辺(あるいは右辺)に
くるべきものをいっしょに考えてください。

QNW-E507のシャッフル機能について

NW-E507のシャッフル機能は全曲対象で可能でしょか?
グループ内でのシャッフルか、グループ自体のシャッフル(グループ内の曲は順どうり再生)しかないように思うのですが。あと、もし、その場合はHDDプレイヤーのように全曲シャッフルできるシリコンプレイヤーはIPOD shuffleくらいしか出ていないのでしょうか?
よろしくおねがいします。

Aベストアンサー

こんばんは。

私はNW-E405を使っていますが、シャッフル機能は全曲対象ですので、NW-E507も同様だと思いますよ。

Qa>0、b>0のとき a^n=b^nや

a^n≦b^nのnは実数の範囲で言えるんですか?複素数の範囲で言えるんですか?

Aベストアンサー

実数の世界では確実に言えます。

複素数の世界については、「大小関係」の定義が鍵になります。
実数では数直線によって大小関係を表すことができますが、複素数で同じことを行おうとすると複素平面によって表すことになります。
二次元ユークリッド空間の二点にそのまま大小関係をつけることはできませんよね?
そこで、複素数の世界において「大小関係」を新しく定義しなおすことが必要になります。
つまり、その定義の仕方によって成り立つかどうかは変わってしまいます。

参考
 http://www004.upp.so-net.ne.jp/s_honma/number/complexnumber.htm

参考URL:http://www004.upp.so-net.ne.jp/s_honma/number/complexnumber.htm

QiPod nanoは曲をシャッフル再生できますか?

iPod shuffleのように曲をランダムに再生してくれる機能はありますか?

Aベストアンサー

あります。

メニューの中に「曲をシャッフル」という項目があるので、
それを選択すれば、シャッフルできます。

http://www.apple.com/jp/ipodnano/features.html

Qa枚のカードから1枚をひっくり返す作業をn回繰り返

a枚のカードがあり、それぞれの表面には1、2、3、…、aの数字が書かれています。
裏面には、表面のマイナスの数字が書かれています。
今、すべてのカードは表が上になっています。

a枚のカードの中から自由に1枚を選び、ひっくり返します。
さらに、a枚のカードの中から自由に1枚を選び、ひっくり返します。
同じカードであっても、別のカードであってもかまいません。
このひっくり返すという作業をn回繰り返したとき、a枚のカードの上の数字の合計の期待値はどのようになるのでしょうか?

Aベストアンサー

「自由に1枚を選び」という表現がちょっと気になるけど、どのカードも同じ確率で選ばれるものとします。

1枚のカードだけに注目すれば、
1回の操作で、反転する確率は1/a、反転しない確率は(a-1)/aなので、
n回の操作で、k回反転する確率P(k)は、
P(k)=nCk*(1/a)^k*((a-1)/a)^(n-k)

よって、mの数字が書かれたカードの上の数字の期待値は、
m{P(0)-P(1)+P(2)-P(3)+・・・・+(-1)^n*P(n)}
=mΣ[k=0・・・n](-1)^k*nCk*(1/a)^k*((a-1)/a)^(n-k)
=mΣ[k=0・・・n]nCk*(-1/a)^k*((a-1)/a)^(n-k)
=m(-1/a+(a-1)/a)^n
=m(1-2/a)^n

すべてのカードの上の数字の合計の期待値は、
Σ[m=1・・・a]m(1-2/a)^n
=a(a+1)(1-2/a)^n/2

QPODの配列用ランダムシャッフル(C++)

・C言語のプログラミング初心者です。
http://oshiete.goo.ne.jp/qa/7304935.html
をみて
そういえば前トランプのゲームを作ろうとしてた時
シャッフルの事を考えたなと思って

今後使うかもしれないと思ったので調べてたら


・整数型の配列をランダムに並べ替える方法
http://oshiete.goo.ne.jp/qa/2438745.html
及び、ベストアンサーの方の回答の紹介ページを見つけついで


http://www.cplusplus.com/reference/algorithm/random_shuffle/
のページを見つけました。


で、実際に自分で
std::random_shaffleのベンチマークをやってみたのですが
やっぱSTLは汎用なので、少なくとも要素数増えると遅い(?)感じがありました。


そこで、基本的な考え方をそのままに
単純なPOD(というか基本的な整数や浮動小数やポインタだけでも十分)の配列でサクサクと使える
RandomShuffle関数を作って(ほとんどそのままですが)みました。

template <class T> inline void Swap( T& a, T& b ){ //POD割り切り用
T t( a );
a = b;
b = t;
}

template <class T, class F>
void RandomShuffle( T* const data, int num, F& randfunc ){
while ( --num ) Swap( data[num], data[randfunc(num+1)] );
}

randfuncの指定は必須になっていますが、ここからなしでいいやつ作るのは簡単なことなので割愛します。

このコードでもやはり、randfuncの結果に偏りがない限り
N個の要素のうちどれについても
特定の場所に行く確率は1/Nになっているはずです。

使い方の例としては

enum { NUM =10000 };
int* data = new int[NUM];
for ( int i = NUM; i--; ) data[i] = i; //初期値をセット

srand( unsigned int( time( NULL ) ) ); 
struct RAND_FUNCTOR {
int operator()( int i ){ return rand()%i; } //0以上i未満の乱数を返す任意の関数
};

//配列の先頭アドレス、要素数、乱数制御の関数を指定して呼び出し
RandomShuffle( data, NUM, RAND_FUNCTOR() );


for ( int i= 0; i<NUM; ++i ) printf( "%d\r\n", data[i] ); //確認とか
delete [] data;


こんな感じになります。

何度かやって平均をとってみて
10000要素では


std::vector<int>

std::random_shaffle
を使った場合

0.00651秒程度~(なぜかなかなか安定しませんでしたが)に対し

上記RandomShuffleでは
0.00153秒程度と、4分の1以下程の時間で出来るっぽいですが

乱数発生アルゴリズム(この場合だと srand( unsigned int( time( NULL ) ) ); → rand()%i; )
を除く

RandomShuffle自体のアルゴリズムに関しては

標準(STL)がこういう手法をとってるって事もありますし
これ以上にすんなりいく方法はさすがにない、てことなのでしょうかね?

また、その他突っ込みどころがあれば教えてください。

・C言語のプログラミング初心者です。
http://oshiete.goo.ne.jp/qa/7304935.html
をみて
そういえば前トランプのゲームを作ろうとしてた時
シャッフルの事を考えたなと思って

今後使うかもしれないと思ったので調べてたら


・整数型の配列をランダムに並べ替える方法
http://oshiete.goo.ne.jp/qa/2438745.html
及び、ベストアンサーの方の回答の紹介ページを見つけついで


http://www.cplusplus.com/reference/algorithm/random_shuffle/
のページを見つけました。


で、実際に自分で
std::random_shaffleの...続きを読む

Aベストアンサー

関数形式のキャストは「1単語」で表せる型じゃないとアウトです. 今の場合 unsigned int が (そのままでは) 1単語にならないから, 関数形式のキャストではなく C的に
(unsigned int)time(NULL)
じゃないとダメですね.

typedef unsigned int uint;
とあれば
uint(time(NULL))
でいいんですが.

あとちょっと気になったのは
int main()
{
int data[10000];
for (int i = 0; i < 10000; ++i) data[i] = i;
std::random_shuffle(data, data+10000, なんか);
// 以下全部略
}
で時間がどうなるか, ですね.

QΣ[n=1..∞]a_n (a_n>0)は収束する。Σ[n=1..∞]a_n/n^pが収束するようにpの全ての値を求めよ

[問]Σ[n=1..∞]a_n (a_n>0)は収束する。Σ[n=1..∞]a_n/n^pが収束するようにpの全ての値を求めよ。
[解]
(i) p>0の時,
1/1^p≧1/2^p≧…≧0且つlim[n→∞]1/n^p=0
よって定理「Σ[n=1..∞]a_n∈Rで{b_k}は単調且つlim[n→∞]b_n=0⇒Σ[n=1..∞]a_kb_kも収束」より
Σ[n=1..∞]a_n/n^p∈R
(ii) p=1の時
Σ[n=1..∞]a_n/n^p=Σ[n=1..∞]a_nで収束(∵仮定)
(iii) p<0の時
が分かりません。
どのようにして判定すればいいのでしょうか?

Aベストアンサー

簡単な判定方法はありません。
Σ[n=1..∞]a_n/n^p
のタイプの級数をディリクレ級数といいます。冪級数の収束半径のようなものがあり、pの実部がσより大きいと収束し、pの実部がσより小さいと発散するような実数σが存在します。pの実部がσのときは収束することもあれば発散することもあります。
この問題の場合σが負または0であること以上のことはわかりません。a_nによってσは異ります。

Qjava シャッフルについて

こんいちは。

今、カードゲームを作っているのですが、
リストに格納された先頭の8件に3件以上、重複したものがあったら、
再シャッフルし続けると言うロジックを組んでいるのですが、
ログを見ると、3件以上なのに終了したり、最初の8件に3件以上無いのに
シャッフルしてます。

このロジックに間違いないと思っているんですが、
どこか間違っていますでしょうか?

boolean flg = true;
do {
Collections.shuffle(list, new Random());
flg = true;
for (int i = 0; i < 8; i++) {
int cnt = 0;
for (int j = 0; j < 8; j++) {
if (list.get(i).id.equals(list.get(j).id))
cnt++;
}
if (cnt > 2) {
flg = false;
break;
}
}
} while (flg);

こんいちは。

今、カードゲームを作っているのですが、
リストに格納された先頭の8件に3件以上、重複したものがあったら、
再シャッフルし続けると言うロジックを組んでいるのですが、
ログを見ると、3件以上なのに終了したり、最初の8件に3件以上無いのに
シャッフルしてます。

このロジックに間違いないと思っているんですが、
どこか間違っていますでしょうか?

boolean flg = true;
do {
Collections.shuffle(list, new Random());
flg = true;
for (int i = 0; i < 8; i+...続きを読む

Aベストアンサー

#3 ですが、これは do while 文に対する理解不足が原因の気がしました。
なので、無限ループの break 終了でロジックを組んでは如何でしょうか。

while (true) {
シャッフル();
int 重複枚数 = 重複を勘定();
if ( 重複枚数 < 3 ) break; // 条件を満たしたのでループ終了
}

この無限ループ記法は、人によっては嫌われることもあります。
その場合は以下の様に誤魔化せば大丈夫でしょう。

for (int i = 0; i < Integer.MAX_VALUE; i++)

Q数学的帰納法の不等式についてです。 nを5以上の整数とするとき不等式2^n>4n+1を証明せよ、につ

数学的帰納法の不等式についてです。
nを5以上の整数とするとき不等式2^n>4n+1を証明せよ、についてなのですが、>2(4k+1)-(4k+5)ってのがよく分かりません。
だれか教えてください!

Aベストアンサー

2^k>4k+1 が成り立つとして仮定していますので、 2^kは4k+1よりは大きいので

2✕2^k-(4k+5) を、kの一次式として解き、正負を確かめるために、2^kに(4k+1)を代入・置換したと考えてください。
正負が分かれば良いので、近似値の中の最小値(等号があるとして)を入れても問題ないということです。

後は、解説通りの計算で >0が成立するので、となります。

参考までに。


人気Q&Aランキング