「カード合わせの問題」の編集履歴（バックアップ）一覧に戻る
カード合わせの問題 - (2008/08/13 (水) 23:15:23) のソース
#contents()
これは次のような問題です。
+1～nまでの番号が書いてあるカードのセットがある(各番号はひとつのセットに1枚ずつしか入っていない)
+2人の人間がこのセットをそれぞれ1つずつ持つ
+それぞれセットの中から適当に選び出した1枚のカードを見せ合う
+カードはセットに戻さず、再び1枚のカードを選び出し、見せ合う
+最後の一枚まで3～4の試行を繰り返したとき、2人が一度も同じカードを引かない確率というのはカードのセットの総数にかかわらずおよそ1/3程度である
ぱっと考えたくらいでは「カードが全て合わない確率が1/3」というのが納得しにくいですね。カードの総数が増えれば、一度くらい同じカードを引く確率が大きくなるのではないか、いやいや、カードが多くなれば同じカードを引く確率はものすごく小さくなるのではないか、そんな風に考えてしまいがちです。
この問題の具体的な回答は本文中では省略されています。「1700年代から研究されている」問題とのことで、ものすごく難しいのかもしれませんが可能な範囲で食いついていって見ましょう。
**問題を解くにあたっての仮定
まず、カードはランダムに引くのですから、それぞれのカードを引く確率は同様であるとします。これは納得いくと思います。
次に、カードをランダムに引くのは1人だけとします。もう一人の引き方は固定します。つまり、一人の引き方は1から順に(1, 2, 3, 4, 5, ... ,n)であるとして、それに対してもう一人の引き方のあらゆるパターンを調べ、全てのカードが異なる確率を計算してしまうのです。もしもう一人のパターンを調べつくすことができたなら、一人目の並びをどのように変えたとしても、まったく同じ手順をそのパターンに適用すれば、まったく同じ確率が計算されるはずです。この問題では1人目の引き方は重要ではないのです。
**確率の定義
では、「全てのカードが異なる確率」というもののカタチを確認しましょう。カードを引く確率は同様であるとしました。ですから、あらゆるカードの引き方も同様の確率で出現するわけです。こういった状況の下では「場合の数」の比がそのまま確率になります。つまり、全てのカードが異なる確率というのは、
全てのカードが異なる引き方
----------------------------------
カードの引きかたの全てのパターン
で計算できることになります。ここで、「全てのパターン」は簡単に計算できます。n枚のカードがあったとして、1枚目はn通りの選び方、2枚目はn-1通りの選び方、3枚目はn-2通りの選び方...n-1枚目は2通りの選び方、n枚目は1通りの選び方ができるわけですから、そのときの場合の数はこれらを全て掛け合わせたn!です。つまり
全てのカードが異なる引きかた
----------------------------
n!
で確率が計算できるわけです。
**「全てのカードが異なる引きかた」のパターン
では、「全てのカードが異なる引きかた」のパターンがいったい何通りあるのかを計算する式を作りましょう。とりあえずこの式に適当な名前をつけましょう。
miss(n) ≡ カードがn枚のとき、「全てのカードが異なる引きかた」のパターンの数
miss()という関数にカードの枚数を与えたら、全てのカードが合わないパターンが何通りあるかが返ってくるというわけです。このmiss()という書き方を利用すると、上の式は次のように書き換えられます。
$$\frac{\mathrm{miss}(n)}{n!}$$
今はまだmiss()関数の実態はわかりません。これから決めるわけです。現時点ではロクな手がかりがありませんから、最初のいくつかを力業で決定していきましょう。
***miss(0)
カードが1枚も無い場合です。どうすべきか悩むところですが、カードが一枚もないということはカードが一致することはないということです。そしてカードが一致しない組み合わせがひとつだけある(＝カードを出さない)のだと解釈します。よって、
$$\mathrm{miss}(0)=1$$
べつに0としてもいいのですが、どうやら1としておいたほうが後々役に立つっぽいのでこう定義しました。
***miss(1)
カードが1枚の場合です。カードを出せば必ず相手と一致します。なので、
$$\mathrm{miss}(1)=0$$
減りましたね。
***miss(2)
ここからは表を作っていきます。
|一致|パターン|計算式|
|2|1|省略|
|0|1|省略|
注目してほしいのは「1枚だけ一致というパターンがない」ということです。当然です。1枚正解してしまえばもう一枚は必ず正解です。一般化して言えば、n枚のカードのうちn-1枚を決定すれば残りの一枚は決定するので、n枚の一致とn-1枚の一致は同一であるということです。まあなにはともあれ
$$\mathrm{miss}(2)=1$$
戻りましたね。
***miss(3)
さて、少し計算が入ってきます。
|一致|パターン|計算式|
|3|1|略|
|1|3|$$_3 \mathrm{C} _1\mathrm{miss(2)}$$|
|0|2|$$3!-(1+3)$$|
一枚だけ一致する場合ですが、「一体どこでカードが一致するのか？」を考えないといけません。一人を固定しているわけですから、3枚のうちのどの1枚を選ぶのかを考えればいいわけです。よって組み合わせ記号を使って$$_3 \mathrm{C} _1$$によって計算できるわけです。この$$_n\mathrm{C}_r$$という記号の意味はいいと思いますが、後で使うので一応定義を確認しておきましょう。
$$_n\mathrm{C}_r=\frac{n!}{(n-r)!r!}$$
です。そして$$_3 \mathrm{C} _1$$にmiss(2)を掛けていますが、この意味は1枚が正解ということは残りの2枚は間違いでなければならないということです。
そうして1枚も合わない組み合わせの数というのは、全ての組み合わせから1枚以上一致する組み合わせを引いた数ですので上記のような計算式になるわけです。とりあえずこれで
$$\mathrm{miss}(3)=2$$
増えました。
***miss(4)
|一致|パターン|計算式|
|4|1|略|
|2|6|$$_4\mathrm{C}_2\mathrm{miss(2)}$$|
|1|8|$$_4\mathrm{C}_1\mathrm{miss(3)}$$|
|0|9|$$4!-(1+6+8)$$|
さてそろそろパターンが見えてきました。
$$\mathrm{miss}(4)=9$$
もうひとつくらいやってみましょう。
***miss(5)
|一致|パターン|計算式|
|5|1|略|
|3|10|$$_5\mathrm{C}_3\mathrm{miss(2)}$$|
|2|20|$$_5\mathrm{C}_2\mathrm{miss(3)}$$|
|1|45|$$_5\mathrm{C}_1\mathrm{miss(4)}$$|
|0|44|$$5!-(1+10+20+45)$$|
$$\mathrm{miss}(5)=44$$
さて！ある種の法則が見えてきました！一般化しましょう！
***miss(n)
$$\mathrm{miss}(n)=\left{n=0 \ \ \ \ 1 \cr n=1 \ \ \ \ 0 \cr n\ge2 \ \ \ \ n!-\sum_{i=0}^{n-1}_n\mathrm{C}_{n-i}\mathrm{miss}(i) $$
ようやく「全てのカードが異なる引きかたが何パターンあるのか？」を返してくれる関数ができました。右側にはmiss()関数自身が入っているためにmiss(0)の値から順に計算する必要があり、あまりきれいな形とは言えませんがとりあえずこれで我慢してください。
**全てのカードが異なる確率
では確率の計算に移りましょう。目的を忘れてしまいそうになりますが我々の目的は「全てのカードが異なる確率」を計算することにありました。そして、それは
$$\frac{\mathrm{miss}(n)}{n!}$$
で求められるのでした。そしてこの式の分子を占める関数がついほんの少し上で明らかとなったのです。まずはこの計算式にも名前をつけましょう。ミスしてしまう確率(probability)ですから、miss.prob()関数と名付けます。
$$\mathrm{miss.prob}(n)=\frac{\mathrm{miss}(n)}{n!}$$
では、ここへさきほど求めたmiss()関数の中身を代入しましょう。
$$\mathrm{miss.prob}(n)=\left{n=0 \ \ \ \ 1 \cr n=1 \ \ \ \ 0 \cr n\ge2 \ \ \ \ 1-\sum_{i=0}^{n-1}\frac{\mathrm{miss.prob}(i)}{(n-i)!}$$
なにやら単純に代入したとは思えない変形をしているように見えるかもしれませんが、組み合わせの定義
$$_n\mathrm{C}_r=\frac{n!}{(n-r)!r!}$$
に従って$$_n\mathrm{C}_{n-i}$$を展開して整理すれば割と簡単にこの形になりますから、気になる人は手計算してみてください。
