- 追加された行はこの色です。
- 削除された行はこの色です。
- 七人の侍と刀 へ行く。
元ネタは高校生のときの確率のテストで出題された応用問題。出題した先生がまだ現役で先生されているみたいなので具体的な結果は載せず、解説だけに留める。
#contents
*お題 [#la6ef37a]
七人の侍がいて、それぞれちょうど一本ずつ刀を所持している。
全員で茶屋に入ったところ、刀を外して入店するよう言われたため、それに従い全員刀を外した。
退店時に、全員適当に刀を持って退店したため、全員で刀の元の持ち主を調べることとなった。
このとき、七人の侍全員が、自分のものでない刀を持っている確率はいくつか？
**ヒント [#d9090946]
-出題時に教師に忠告されたが、とんちのように解ける問題ではなく、解答は分子の分母も4桁の分数になる。
*n=1の場合 [#dbc25a40]
一般化するため、お侍さんの人数をn人として、n=1の場合を考える。
当然、刀も一本なのでこの場合「自分のものでない刀を持っている確率」は0である
*n=2の場合 [#m8baa8ce]
n=2の場合、刀は「自分のもの」か「相手のもの」の二択しかありえないので、「自分のものでない刀を持っている確率」は1/2である
*n=3の場合 [#o1947463]
-ここからようやく一般化が始まる。
-そもそも、これは1からnまでの数字を使って長さnの文字列を重複なく漏れなく全通り生成し、x桁目の文字列がxであるかどうかを全桁確認することになる。
-よって、確率の分母は&mimetex(n!);となる。またそのうちの1通りだけは確実に「全員が自分の刀を正しく持っている状態」なのは自明である。
-n=3の場合では6通りなので、全部書き出してみる
123 3人とも自分の刀
132
213
231 3人とも間違い(問題文に合致する)
312 3人とも間違い(問題文に合致する)
321
-さて、この中で、問題文の「自分のものでない刀を持っている」状態は「231」と「312」の2通りである。
-ここでよく見てみると、初めて「全員自分の刀」でも「全員他人の刀」でもなく、「一部自分の刀、一部他人の刀」を持ってる状態が発生する。
-前述の候補では「132」「213」「321」の3通りがそれに合致する。
-よって、n=3の場合は6通りのうち
--全員が自分の刀を持っている状態(1通り)
--1人だけが自分の刀、あとの2人は他人の刀を持っている状態(3通り)
--全員が他人の刀を持っている状態(2通り)
--と場合分けできることがわかる。
-最後が問題文として求めたい結果で、最初が自明な結果。つまるところ2番目の「一部自分の刀、一部他人の刀」を持っている状態をどうにか計算できるようにしたい。
-n=3はとりあえず力業で解けたので、n=4の場合を見てみよう
*n=4の場合 [#n2d1aeda]
-n=4の場合は、結果が以下の4通りに分けられる
--全員が自分の刀を持っている状態(1通り)
--1人だけが自分の刀、あとの3人は他人の刀を持っている状態
--2人だけが自分の刀、あとの2人は他人の刀を持っている状態
--全員が他人の刀を持っている状態
-よく考えればわかるのだが「3人が自分の刀を持っていて、残り1人だけ他人の刀を持っている」という状態は発生し得ない。
-というわけで、n=4の場合、「自分のものでない刀を持っている確率」は以下の数式で求められる
4!(全通り) - 1(全員が自分の刀を持っている状態) - (1人だけが自分の刀、あとの3人が他人の刀を持っている状態) - (2人だけが自分の刀、あとの2人が他人の刀を持っている状態)
-ここで、n人中、m人が自分の刀を持っていない状態を関数 &mimetex(f(m,n)); で表すことにしてみよう。
--&mimetex(f(0,n)); = 1 (全員が自分の刀を持っている状態、自明)
--&mimetex(f(1,n)); = 0 (1人だけ他人の刀を持っている状態はありえない、自明)
--:
--&mimetex(f(n,n)); = 今回の問題の答え
-とすると、今回の問題の答えである&mimetex(f(n,n));を求めるためには、以下の数式を解く必要がある
-&mimetex(f(n,n) = n! - \sum_{k=2}^{n-1}f(k,n) - 1);
-問題はmが0と1以外の場合の&mimetex(f(m,n));をどう求めるか、である。
**f(2,4)とf(3,4) [#c9cdccd6]
-&mimetex(f(2,4));は4人中2人の侍が間違えた刀を持つパターンである
-2人間違えるパターンはたくさんある。以下に列挙する
1243 1と2は正解
1432 1と3は正解
1324 1と4は正解
4231 2と3は正解
3214 2と4は正解
2134 3と4は正解
-ここに示す通り、2人間違えるということは2人正解することであり、正解する2人を選ぶと失敗する方法は残りの2人が刀を交換する方法しかない
-4人から重複なく2人を選ぶ方法は&mimetex(_4C_2=6);なので、これは全部で6通りある
-同様の方法で考えると&mimetex(f(3,4));は正解する1人を選んで、残りの3人のうちでそれぞれ間違える方法を考えることになる。
--正解する1人を選ぶ方法は4通り。
--そして、失敗した3人内で全員が間違える方法は、実は&mimetex(f(3,3));で、前節で2通りと計算している
--なので、&mimetex(4 \times f(3,3) = 4 \times 2 = 8);通りである
-というわけで、&mimetex(f(4,4));は以下のように求められる
f(4,4) = 4! - f(0,4) - f(1,4) - f(2,4) - f(3,4)
= 24 - 1 - 0 - 4C2 * f(2,2) - 4C1 * f(3,3)
= 24 - 1 - 0 - 6 * 1 - 4 * 2
= 24 - 1 - 0 - 6 - 8
= 24 - 15
= 9
-また、&mimetex(f(2,4));と&mimetex(f(3,4));はそれぞれ以下の式で一般化できる
-&mimetex(f(m,n) = {}_nC_{n-m} \times f(m,m)); (ただし&mimetex(m\neq0,1);)
-もしくは以下の式でも同じ
-&mimetex(f(m,n) = {}_nC_m \times f(m,m)); (ただし&mimetex(m\neq0,1);)
-このように、&mimetex(f(m,n));は再帰的な関数であり、&mimetex(f(7,7));を求めるためには&mimetex(f(1,1));から全部順番に求めなくては行けない。
-また、確率なので、全体を&mimetex(n!);で割らなくてはいけない。つまり&mimetex(f(4,4));の場合は24で割る。
*n=7の場合、つまりはf(7,7) [#fe637d5b]
-以下の式で表される
f(7,7) = 7! - f(0,7) - f(1,7) - f(2,7) - f(3,7) - f(4,7) - f(5,7) - f(6,7)
= 5040 - 1 - 0 - 7C2 * f(2,2) - 7C3 * f(3,3) - 7C4 * f(4,4) - 7C5 * f(5,5) - 7C6 * f(6,6)
= 5040 - 1 - 0 - 21 * 1 - 35 * 2 - 35 * 9 - 21 * f(5,5) - 7 * f(6,6)
-ただ、式中の&mimetex(f(5,5));と&mimetex(f(6,6));は計算する必要がある
-また、確率としては7!=5040で割る必要がある
*検算と余談 [#pad4b4d3]
-学生時代に「じゃあ俺プログラミングできるからそれで解く！」と先生に面と向かって宣言したところ「いいけれど、全部調べ上げていくつでした、ってのは駄目だ」と釘を刺された
-卒業して実に20年ぐらい経ってるけれど、今回は検算するのにbrute forceでやったやつと検算して、ちゃんとこの解法が合ってることを確認した
-なお、プログラミングの課題と考えても、再帰的な実装が必要なので、プログラムで解くのもそれはそれで正しいし興味深い。是非試してもらいたい。
[[:数学]]
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
