七人の侍と刀
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
元ネタは高校生のときの確率のテストで出題された応用問題。...
#contents
*お題 [#la6ef37a]
七人の侍がいて、それぞれちょうど一本ずつ刀を所持している。
全員で茶屋に入ったところ、刀を外して入店するよう言われた...
退店時に、全員適当に刀を持って退店したため、全員で刀の元...
このとき、七人の侍全員が、自分のものでない刀を持っている...
**ヒント [#d9090946]
-出題時に教師に忠告されたが、とんちのように解ける問題では...
*n=1の場合 [#dbc25a40]
一般化するため、お侍さんの人数をn人として、n=1の場合を考...
当然、刀も一本なのでこの場合「自分のものでない刀を持って...
*n=2の場合 [#m8baa8ce]
n=2の場合、刀は「自分のもの」か「相手のもの」の二択しかあ...
*n=3の場合 [#o1947463]
-ここからようやく一般化が始まる。
-そもそも、これは1からnまでの数字を使って長さnの文字列を...
-よって、確率の分母は&mimetex(n!);となる。またそのうちの1...
-n=3の場合では6通りなので、全部書き出してみる
123 3人とも自分の刀
132
213
231 3人とも間違い(問題文に合致する)
312 3人とも間違い(問題文に合致する)
321
-さて、この中で、問題文の「自分のものでない刀を持っている...
-ここでよく見てみると、初めて「全員自分の刀」でも「全員他...
-前述の候補では「132」「213」「321」の3通りがそれに合致す...
-よって、n=3の場合は6通りのうち
--全員が自分の刀を持っている状態(1通り)
--1人だけが自分の刀、あとの2人は他人の刀を持っている状態(...
--全員が他人の刀を持っている状態(2通り)
--と場合分けできることがわかる。
-最後が問題文として求めたい結果で、最初が自明な結果。つま...
-n=3はとりあえず力業で解けたので、n=4の場合を見てみよう
*n=4の場合 [#n2d1aeda]
-n=4の場合は、結果が以下の4通りに分けられる
--全員が自分の刀を持っている状態(1通り)
--1人だけが自分の刀、あとの3人は他人の刀を持っている状態
--2人だけが自分の刀、あとの2人は他人の刀を持っている状態
--全員が他人の刀を持っている状態
-よく考えればわかるのだが「3人が自分の刀を持っていて、残...
-というわけで、n=4の場合、「自分のものでない刀を持ってい...
4!(全通り) - 1(全員が自分の刀を持っている状態) - (1人だ...
-ここで、n人中、m人が自分の刀を持っていない状態を関数 &mi...
--&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人正解することで...
-4人から重複なく2人を選ぶ方法は&mimetex(_4C_2=6);なので、...
-同様の方法で考えると&mimetex(f(3,4));は正解する1人を選ん...
--正解する1人を選ぶ方法は4通り。
--そして、失敗した3人内で全員が間違える方法は、実は&mimet...
--なので、&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...
= 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)); (ただし&mi...
-もしくは以下の式でも同じ
-&mimetex(f(m,n) = {}_nC_m \times f(m,m)); (ただし&mimete...
-このように、&mimetex(f(m,n));は再帰的な関数であり、&mime...
-また、確率なので、全体を&mimetex(n!);で割らなくてはいけ...
*n=7の場合、つまりはf(7,7) [#fe637d5b]
-以下の式で表される
f(7,7) = 7! - f(0,7) - f(1,7) - f(2,7) - f(3,7) ...
= 5040 - 1 - 0 - 7C2 * f(2,2) - 7C3 * f...
= 5040 - 1 - 0 - 21 * 1 - 35 * 2...
-ただ、式中の&mimetex(f(5,5));と&mimetex(f(6,6));は計算す...
-また、確率としては7!=5040で割る必要がある
*検算と余談 [#pad4b4d3]
-学生時代に「じゃあ俺プログラミングできるからそれで解く!...
-卒業して実に20年ぐらい経ってるけれど、今回は検算するのに...
-なお、プログラミングの課題と考えても、再帰的な実装が必要...
[[:数学]]
終了行:
元ネタは高校生のときの確率のテストで出題された応用問題。...
#contents
*お題 [#la6ef37a]
七人の侍がいて、それぞれちょうど一本ずつ刀を所持している。
全員で茶屋に入ったところ、刀を外して入店するよう言われた...
退店時に、全員適当に刀を持って退店したため、全員で刀の元...
このとき、七人の侍全員が、自分のものでない刀を持っている...
**ヒント [#d9090946]
-出題時に教師に忠告されたが、とんちのように解ける問題では...
*n=1の場合 [#dbc25a40]
一般化するため、お侍さんの人数をn人として、n=1の場合を考...
当然、刀も一本なのでこの場合「自分のものでない刀を持って...
*n=2の場合 [#m8baa8ce]
n=2の場合、刀は「自分のもの」か「相手のもの」の二択しかあ...
*n=3の場合 [#o1947463]
-ここからようやく一般化が始まる。
-そもそも、これは1からnまでの数字を使って長さnの文字列を...
-よって、確率の分母は&mimetex(n!);となる。またそのうちの1...
-n=3の場合では6通りなので、全部書き出してみる
123 3人とも自分の刀
132
213
231 3人とも間違い(問題文に合致する)
312 3人とも間違い(問題文に合致する)
321
-さて、この中で、問題文の「自分のものでない刀を持っている...
-ここでよく見てみると、初めて「全員自分の刀」でも「全員他...
-前述の候補では「132」「213」「321」の3通りがそれに合致す...
-よって、n=3の場合は6通りのうち
--全員が自分の刀を持っている状態(1通り)
--1人だけが自分の刀、あとの2人は他人の刀を持っている状態(...
--全員が他人の刀を持っている状態(2通り)
--と場合分けできることがわかる。
-最後が問題文として求めたい結果で、最初が自明な結果。つま...
-n=3はとりあえず力業で解けたので、n=4の場合を見てみよう
*n=4の場合 [#n2d1aeda]
-n=4の場合は、結果が以下の4通りに分けられる
--全員が自分の刀を持っている状態(1通り)
--1人だけが自分の刀、あとの3人は他人の刀を持っている状態
--2人だけが自分の刀、あとの2人は他人の刀を持っている状態
--全員が他人の刀を持っている状態
-よく考えればわかるのだが「3人が自分の刀を持っていて、残...
-というわけで、n=4の場合、「自分のものでない刀を持ってい...
4!(全通り) - 1(全員が自分の刀を持っている状態) - (1人だ...
-ここで、n人中、m人が自分の刀を持っていない状態を関数 &mi...
--&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人正解することで...
-4人から重複なく2人を選ぶ方法は&mimetex(_4C_2=6);なので、...
-同様の方法で考えると&mimetex(f(3,4));は正解する1人を選ん...
--正解する1人を選ぶ方法は4通り。
--そして、失敗した3人内で全員が間違える方法は、実は&mimet...
--なので、&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...
= 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)); (ただし&mi...
-もしくは以下の式でも同じ
-&mimetex(f(m,n) = {}_nC_m \times f(m,m)); (ただし&mimete...
-このように、&mimetex(f(m,n));は再帰的な関数であり、&mime...
-また、確率なので、全体を&mimetex(n!);で割らなくてはいけ...
*n=7の場合、つまりはf(7,7) [#fe637d5b]
-以下の式で表される
f(7,7) = 7! - f(0,7) - f(1,7) - f(2,7) - f(3,7) ...
= 5040 - 1 - 0 - 7C2 * f(2,2) - 7C3 * f...
= 5040 - 1 - 0 - 21 * 1 - 35 * 2...
-ただ、式中の&mimetex(f(5,5));と&mimetex(f(6,6));は計算す...
-また、確率としては7!=5040で割る必要がある
*検算と余談 [#pad4b4d3]
-学生時代に「じゃあ俺プログラミングできるからそれで解く!...
-卒業して実に20年ぐらい経ってるけれど、今回は検算するのに...
-なお、プログラミングの課題と考えても、再帰的な実装が必要...
[[:数学]]
ページ名: