/ / 最新

swk's log - 音楽シャッフルクイズ

2005-10-21

* 音楽シャッフルクイズ [misc]

こう立て続けに出題されると睡眠時間が…(ぉ.

んーと,答え自体はわりとすぐ出るのですが,どうもきれいに説明できません.というわけであまりきれいでない説明を書いてみます.自分でも微妙かなと思ってるので送ってません.

(解答編が発表になったので,ネタバレ反転処理をやめました)


答え: 正しくシャッフルはされません.

理由: どんなものでもいいから反例を一つ示せばよいわけで,だから,どれだけきれいにまとめられるかが勝負の分かれ目なわけですね (何の勝負だ).あまりきれいなものが思いつかなかったけど,とりあえずこんな感じで:

3 曲の場合を考えます.3 曲の順列は 3×2×1 = 6 通りなので,あらゆる順列がすべて等確率で得られるためには,どの順列が生成される確率も 1/6 でなくてはなりません.

さて,関数 shuffle による配列の並び方の遷移を考えると 3×3×3 = 27 通りに分岐する樹系図がかけて,その葉のそれぞれが等しく確からしいといえます.よって任意の順列を考えると,それが生成される確率は m/27 (m は 0 以上の整数) と書けなくてはなりません.

よって m/27 = 1/6 を満たす必要がありますが,これを満たす m = 27/6 は整数ではありません.証明終.


うーん,いまいち.

(2005-10-25 追記) というわけで他の皆さんの解答を読んでみたけど,方向性はほとんど同じみたい.そうか,「n は n-1 では割り切れない」を使えば配列サイズ n = 3 に限らず議論できたわけだ.なるほど. (と思ったら,実はそれではちょっとまずいみたい → [2005-10-26-2])

しかし,もっといろんなアプローチの証明が出て来るかと思っていたけど,皆行き着くところは同じなんだな.ちょっと意外だった.

関連記事:
[2005-10-26-2] n^n が n! で割り切れない理由
[2005-10-21-3] ネタバレ反転と RSS

最終更新時間: 2009-01-04 15:31


Shingo W. Kagami - swk(at)kagami.org