「カード合わせの問題」の編集履歴（バックアップ）一覧はこちら

「カード合わせの問題」(2009/09/27 (日) 01:19: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}\ge{2}....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}$$を展開して整理すれば割と簡単にこの形になりますから、気になる人は手計算してみてください。

**Rを使って計算
さて式は得られたわけですが、僕の計算の仕方がまずかったのか大変複雑な形になってしまいました。ちょっと数値を入れてみても簡単に答えが得られそうにありません。例えばmiss.prob(5)程度を計算するのにも相当な時間がかかりそうです。こういうときはコンピュータの力を借りましょう。

次のような関数を作りました。
 miss.prob <- function(n){
	if(n==0) return(1)
	if(n==1) return(0)
	miss <- 0
	for(i in 1:n-1){miss <- miss + miss.prob(i)/factorial(n-i)}
	1-miss
	}
再帰処理(関数の中で、その関数自身を呼び出す)とfor文が組み合わさっていて見るからに重そうです。実際重いです。あまりきれいな関数とは言えないです。いつもなら実際に実行してみろというところですが今回はあんまりオススメしません。ちょっとでかい数値を入れただけで計算時間が馬鹿みたいにかかります。やってみてもいいですが、止め方を覚えてからやってください。計算の強制終了は[ESCキー]です。今手元のPCでファンを全力で回しながら20まで計算してみました。結果は次の通りです。
  [1] 0.0000000 0.5000000 0.3333333 0.3750000 0.3666667 0.3680556 0.3678571
  [8] 0.3678819 0.3678792 0.3678795 0.3678794 0.3678794 0.3678794 0.3678794
 [15] 0.3678794 0.3678794 0.3678794 0.3678794 0.3678794 0.3678794
10を過ぎたあたりから値がずっと0.368794ですね。このまま続けてもずっと同じです。もっと細かいところでは動いているはずですが、どうやらmiss.prob()関数は0.368あたりに収束するようです。1/3よりはちっとばかし大きいですが、きっかり1/3と言っているわけでもありませんでしたし、おそらくこの値でよいのでしょう。

で、残念ですが僕はここでギブアップです。お手上げです。本当に確率が0.368あたりに収束するという証明もしていませんし、miss.prob()関数の一般的な(定義に自分自身を含まない)形も示していません。それにもしかするともっと簡単な解き方があるのかもしれません。ただ、力技で計算したらどうやら収束しそうだ、ということを言ったにすぎません。

この先、あるいは別の道があるのならぜひ見てみたいので、「この後はこうする！」とか「こういうやり方がある！」という意見があれば大歓迎です。
----
(追記)
もうちっとばかし効率のよい関数が出来ました。とりあえず「お客の数が1000人であろうと1万人であろうと、その確率はやはりほとんど三分の一である」ことは示せます。若干時間がかかりますが、↑の関数が30個の数値を計算するのに2時間かかったのに比べればまだ現実的な時間で計算をしてくれます(手元のPCでは43秒で10000までの値が計算できました)。
 miss.prob <- function(n){
  miss.p <- numeric(n)
  miss.p[c(1,2)] <- c(1,0)
  if(n==0) return(1)
  if(n==1) return(0)
  for(j in 3:n){
    i <- 1:j
    miss <- (sum(exp(log(miss.p[c(1:j)]) - lfactorial((j-1):0))))
    miss.p[j] <- 1-miss
    }
  miss.p
  }
さっきよりごちゃごちゃしてますが、再帰処理をやめて一々計算結果をベクトルに収納し、ベクトルを参照するようにしたこと、直接階乗を計算するfactorial関数(桁数の関係で170!までの計算しかできない)の代わりに結果の対数を返すlfactorial関数(10^305くらいまで計算できるみたいです)を使うようにしたことがポイントっぽいですが、ぶっちゃけ適当にいじったので自分でもなんで上手く行ってるのか分からない部分があります。

結果はこんな感じです。
#image(miss.prob.png)
まぁとにかく収束するっぽいですね。それもかなり早く。10000個目の値はやっぱり0.3678794でした。

- いまさらですがこの問題は包除原理というものを使って解くことができて、最終的に出てくる0.3676794...という値はいわゆるネイピア数e=2.718282...の逆数です。  -- 名無しさん  (2009-02-01 01:19:02)
#comment()

----

#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}\ge{2}....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}$$を展開して整理すれば割と簡単にこの形になりますから、気になる人は手計算してみてください。

**Rを使って計算
さて式は得られたわけですが、僕の計算の仕方がまずかったのか大変複雑な形になってしまいました。ちょっと数値を入れてみても簡単に答えが得られそうにありません。例えばmiss.prob(5)程度を計算するのにも相当な時間がかかりそうです。こういうときはコンピュータの力を借りましょう。

次のような関数を作りました。
 miss.prob <- function(n){
	if(n==0) return(1)
	if(n==1) return(0)
	miss <- 0
	for(i in 1:n-1){miss <- miss + miss.prob(i)/factorial(n-i)}
	1-miss
	}
再帰処理(関数の中で、その関数自身を呼び出す)とfor文が組み合わさっていて見るからに重そうです。実際重いです。あまりきれいな関数とは言えないです。いつもなら実際に実行してみろというところですが今回はあんまりオススメしません。ちょっとでかい数値を入れただけで計算時間が馬鹿みたいにかかります。やってみてもいいですが、止め方を覚えてからやってください。計算の強制終了は[ESCキー]です。今手元のPCでファンを全力で回しながら20まで計算してみました。結果は次の通りです。
  [1] 0.0000000 0.5000000 0.3333333 0.3750000 0.3666667 0.3680556 0.3678571
  [8] 0.3678819 0.3678792 0.3678795 0.3678794 0.3678794 0.3678794 0.3678794
 [15] 0.3678794 0.3678794 0.3678794 0.3678794 0.3678794 0.3678794
10を過ぎたあたりから値がずっと0.368794ですね。このまま続けてもずっと同じです。もっと細かいところでは動いているはずですが、どうやらmiss.prob()関数は0.368あたりに収束するようです。1/3よりはちっとばかし大きいですが、きっかり1/3と言っているわけでもありませんでしたし、おそらくこの値でよいのでしょう。

で、残念ですが僕はここでギブアップです。お手上げです。本当に確率が0.368あたりに収束するという証明もしていませんし、miss.prob()関数の一般的な(定義に自分自身を含まない)形も示していません。それにもしかするともっと簡単な解き方があるのかもしれません。ただ、力技で計算したらどうやら収束しそうだ、ということを言ったにすぎません。

この先、あるいは別の道があるのならぜひ見てみたいので、「この後はこうする！」とか「こういうやり方がある！」という意見があれば大歓迎です。
----
(追記)
もうちっとばかし効率のよい関数が出来ました。とりあえず「お客の数が1000人であろうと1万人であろうと、その確率はやはりほとんど三分の一である」ことは示せます。若干時間がかかりますが、↑の関数が30個の数値を計算するのに2時間かかったのに比べればまだ現実的な時間で計算をしてくれます(手元のPCでは43秒で10000までの値が計算できました)。
 miss.prob <- function(n){
  miss.p <- numeric(n)
  miss.p[c(1,2)] <- c(1,0)
  if(n==0) return(1)
  if(n==1) return(0)
  for(j in 3:n){
    i <- 1:j
    miss <- (sum(exp(log(miss.p[c(1:j)]) - lfactorial((j-1):0))))
    miss.p[j] <- 1-miss
    }
  miss.p
  }
さっきよりごちゃごちゃしてますが、再帰処理をやめて一々計算結果をベクトルに収納し、ベクトルを参照するようにしたこと、直接階乗を計算するfactorial関数(桁数の関係で170!までの計算しかできない)の代わりに結果の対数を返すlfactorial関数(10^305くらいまで計算できるみたいです)を使うようにしたことがポイントっぽいですが、ぶっちゃけ適当にいじったので自分でもなんで上手く行ってるのか分からない部分があります。

結果はこんな感じです。
#image(miss.prob.png)
まぁとにかく収束するっぽいですね。それもかなり早く。10000個目の値はやっぱり0.3678794でした。

- いまさらですがこの問題は包除原理というものを使って解くことができて、最終的に出てくる0.3676794...という値はいわゆるネイピア数e=2.718282...の逆数です。  -- r_ito (2009-02-01 01:19:02)
#comment()

----