今日の料理

f:id:nisemono_san:20160808113612j:plain

メンチカツサンドを汚なく作る方法。

トレーズというゲーム、そしてその問題

トレーズ(treize)というゲームがある。このゲームの名前はフランス語で13を表している。このゲームは、ジョーカーを抜いた52枚のトランプを使って遊ぶ。

まず、トランプを良くシャッフルする。そのトランプのカードに1から順番を付けながらめくっていく。このとき、順番と同じ番号が出た場合は勝利し、次のプレイヤーに残りのトランプを渡す。当然ながら、順番とカードの数が一致しないときもある。このとき、プレイヤーは負けということになる。

そこで、このカードゲームにならって、我々は13枚のカードを用意することにしよう。そして、このカードを順番を付けながらめくっていった場合、果して順番と一致しない数しか出ない確率はどれほどになるだろうか。さらに、もしこのカードの枚数を2倍に増やした場合、勝つ確率は上がるだろうか。それとも下るだろうか。

相対確率を調べる

上記の問題は、『反直感の数学パズル』から引用したものである。ちなみに相対確率(試行から当てはまったものを使う方法)では、次のようにして調べることができる。

def treize n
  card = [*0..(n - 1)].shuffle
  card.each_with_index do |k, i|
    return true if k == i
  end
  return false
end

TIMES = 100000

2.upto(52) do |n|
  win = 0
  1.upto(TIMES) do
    win += 1 if treize n
  end
  puts "#{n}枚の当たった回数は#{win}, 確率は#{win.to_f / TIMES}"
end

このようにして出力した結果は下のようになる。

13枚の当たった回数は63272, 確率は0.63272
26枚の当たった回数は63277, 確率は0.63277
39枚の当たった回数は63165, 確率は0.63165
52枚の当たった回数は63187, 確率は0.63187

本書には、13枚で1枚以上当たる確率と、52枚一枚以上当たる確率は、理論上「0.632121」まで一致すると伸べている。

完全順列

先ほどの、任意のカードをシャッフルして、順番と一致しないということを言いかえると、{1, 2, 3, ... , n}の順列とそれがシャッフルしてできた順列({a1, a2, a3, .. , an}と表記する)を照らしあわせると、それぞれの位置において同じ要素が現れない、という風に説明できる。これを完全順列と言うらしい。

さて、もしこのゲームにおいて外れる確率を計算したいとするならば、完全順列の総数を、順列の総数で割ればいいということになる。そこで、本書で紹介されているベルヌーイの方法を利用することにする。

包除原理を使う

包除原理とは、例えばAとBという集合があるとし、nをそこに属する要素を求める関数であると定義した場合、 $n(A \cup B)$ に属する要素を求めるにはどうすればいいか、ということである。

もちろん、AとBが独立している場合(つまり、要素の重複が存在しない場合)、 $n(A) + n(B)$ とすることで計算ができる。とはいえ、あらかじめ、AとBが独立しているかどうかがわからない場合、 $n(A) + n(B) - n(A \cap B)$ とする。理由は、Aを数え、かつBを数えた場合、AとBに属している数は2度数えられているという計算になるからだ。

さて、集合が2つの場合はわかった。今度は3つの集合であるA, B, Cの場合を考えてみよう。最初同様に、 $n(A) + n(B) + n(C)$ を計算する。当然ながら、 $n(A \cap B)$ 、 $n(A \cap C)$ 、 $n(B \cap C)$ の場合は前出同様、2重に数えられているわけだから、これを消す。

しかし、ちょっと考えてみよう。 $n(A \cap B \cap C)$ は、この段階でどれだけ含まれているか。まず、 $n(A) + n(B) + n(C)$ の段階で3回数えられている。そのあと $n(A \cap B)$ 、 $n(A \cap C)$ 、 $n(B \cap C)$ で3回除去されているので、実質計算されていないことになる。これではまずいので、 $n(A \cap B \cap C)$ を足しあわせることにする。

ここで、ある法則性が理解できる。先ほどの集合の名前A, B, CをA1, A2, A3と表現した場合、まず最初にそれぞれの総数をとりあえず求め、そのあとに、2組の重複、つまりは偶数組は引き算をおこない、そして、3組の重複、つまりは奇数組は足すとよい。これは集合が4つある場合もそうであるので、もし手元に手軽なノートがあるならば、各自で確認して欲しい。

完全順序と包除原理

さて、そこで完全順序の求めかたを考えてみよう。そこで、わかりやすいように、順列が{1, 2, 3}の場合を考えてみよう。

まず最初にこの順列をシャッフルして取りうる全ての数を計算する。そのリストを上げると下のようになる。

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

この程度なら個数は数えあげられるのだけれど、今はロジックを確認するためのものだから勘弁して欲しい。

まずそれぞれの順列に対して{a1, a2, a3}という名前を付ける。まず最初のケースとして{a1 = 1}, {a2 = 2}, {a3 = 3} という場合を取りあげる(今後、このように完全順序にならないものを「固定した」と表現する)。このとき、元の順列と、上記の事例は完全順序ではないので排除される。

{2, 3, 1}
{3, 1, 2}

実際、ここで既に要素は出ているのだが、あくまで包除原理にもとづいて計算を進める。先に言うと、奇数回で消さなければならない要素は{1, 2, 3}である。そこで、偶数回である今回は、{a1 = 1, a2 = 2}, {a2 = 2, a3 = 3} といった配列を足すことにする。とはいえ、これに当てはまるのは {1, 2, 3}だけなので、{1, 2, 3}を足すことになる。