音楽シャッフル・クイズ
結城浩さんの日記（http://www.hyuki.com/d/200510.html#i20051020）から。
ミルカさん風に書いてみようか。
void shuffle(int music[], int size) { int i; for (i = 0; i < size; i++) { int r = random(0, size); int m = music[i]; music[i] = music[r]; music[r] = m; } }
このコードで配列を正しくシャッフルできるか、というのが今回の問題だね。配列の長さを示す変数sizeには条件があって、size>=3だね。
一般的な例を考える前に、簡単な例として配列の大きさが3の場合で考えてみようか。長さが3の配列の並び方は何通りあるんだろう？ 最初の要素は3つの中から選ぶから3通り、2個目の要素は1個へって2通りから選べるね。3個目はもう1個しか残っていないから1通りしかありえない。つまり3*2*1=6通りあるよね。
(A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A)
具体的には、この6通りが全て均一に出現するなら、配列を正しくシャッフルできていると言えるね。
じゃあ、上のコードを使ってシャッフルした場合はどうなるだろう。今回は配列の長さが3だから、配列の要素をi番目とr番目の2つを選んで入れ替える操作を3回行うわけだね。長さ3の配列から選ぶ組み合わせは、上のコードだとi=jとなる場合があるから、重複を許して3通りよね。この操作を3回行うから、交換の仕方は3^3=27通り。
だけど、長さ3の配列の組み合わせは6通りしかなかったよね。27を6で割ると3余ってしまう。この3通りのぶん、どれかの組み合わせは他の組み合わせよりも出る確率が大きいよね。つまり、最初のコードではきちんとシャッフルできていないのよ。
一般的に長さNの配列で考えてみようか。もちろん、条件よりN>=3ね。長さがNの配列は、N!通りの並び方を持つよね。次に、長さNの配列からi番目とr番目を入れ替える操作をN回繰り返したときの交換の仕方は何通りあるんだろう？ まず、i番目とr番目を入れ替える操作について考えよう。コードから、i=rとなる重複は許されるので、N通り。これは1回の操作で、この操作をN回行うんだから、全部でN^N通りの組み合わせになるね。
それならN^N/N!の答えはどうなるんだろう？ これが常に割り切れないなら、上のコードでは正しくシャッフルできていないことになるね。
実は、N^N/N!が割り切れるかどうか、というのは、N/(N-1)が割り切れるかどうか、ということになるの。だから、N/(N-1)が割り切れるかどうかを考えてみればいい。
N>=3のときに、N/(N-1)が割り切れると仮定してみようか。割り切れるならNとN-1は共通の素因数、pとしようか、このpを持つことになる*1。すると、NとN-1の差はpの整数倍したものでなければいけないよね。だけど、N-(N-1)=1だから、p>=2の整数倍ではない。どうしてこうなったかというと、最初の仮定が誤っているからだね。つまり、N/(N-1)は、割り切れない。
上のことから、N^N/N!が割り切れないことが言えた。だから、上のコードでは正しいシャッフルが出来ないと証明できたね。
補足(2): n^nがn!で割り切れないのは、n≧3のとき、nがn-1で割り切れないことから明らか。
補足(3): n≧3のとき、nがn-1で割り切れないのは、nとn-1はn≧3のとき共通の素因数を持たないから。もしnとn-1が共通の素因数p≧2を持ったとすると、nとn-1の差はpの整数倍でなければならない。しかしnとn-1の差(1)はp≧2の整数倍にはならない（n=ap, n-1=bp を n-(n-1)=(a-b)p にする）。
N>=3のときにN^N/N!が割り切れないことを言えれば、一般の場合の証明になるんだけど…。どうやれば証明できるのかわからない… Nが奇数のとき*2、N^Nは奇数、N!は偶数だから、N^N/N!は割り切れないと言えるんだけど、Nが偶数のときはどうやればいいんだろう。
結城さんの証明を見て、書き足しました。証明を見れば納得ー、自力で書けなかったのは残念ですが。書き足している途中で、間違えて更新部分を全部消しちゃったorz 書き直すのは大変ですのだ。
