今日はこんな記事をみつけました。
コートの取り違えの問題
ホテルのクロークで、5人がコートを預けました。
用事が済んでコートを返してもらった時、5人全員が自分のものではないコートを受け取る場合の数は何とおり？
という問題を先輩からクイズで出されたのですが、考えれば考えるほどこんがらがってきます。
うまい方法はないでしょうか。
- 回答 -
モンモールの問題とよばれる有名な問題です。
色々な考え方がありますが、円順列を用いる方法を書いてみます。
5 人が手をつないで輪になったと思って下さい。
このとき、自分の右の人に、つまり右手をつないだ人に自分のコートを渡すと考えます。
この場合は、5 人全員でコートを交換することになります。
5 人の円順列ですから、ここまでに24 通りあります。
でも、これだけでなく、3 人の間でコートを交換し、残った 2 人の間で交換するという方法もあります。
これが先の 5 人の場合と違うことを図でも描いて確かめてみて下さい。
さて、この場合は、まず 2 人を選ぶ方法が 5C2 の 10 通りで、それぞれに対しコートの渡し方は 3 人の円順列で 2 通り（2人の方は1通りですね）。
ですから、この場合の総数は
10 × 2
の 20 通り。
従って先の 24 通りと合わせて全部で 44 通りになりますね。
【追加】
一応、一般の場合もやっておきましょうか。
上に書いた円順列を用いても出来ますが、普通の方法で。
n人を大文字A〜で、コートを対応する小文字a〜で表します。
まず、Aが持ち帰るコートはb〜の n-1 通りで、そのうちの b を持ち帰った場合を考えます。求める総数は、これに n-1 を掛ければいいですね。
A が b を持ち帰り、その A のコートaを B が持ち帰れば、残った人とコートは C〜 と c〜 の n-2 組ですので、これは n-2 人が n-2着のコートを持ち帰るという問題に帰着します。
つまり、本問の n が n-2 に変わっただけ。
その総数を P(n-2) と表しましょう。
本問の目的は P(n) を求めることです。
次に、B が a 以外のコートを持ち帰った場合を考えます。
この場合、B は a を持ち帰ることが出来ず、残った C〜 の n-2 人は自分のコートを持ち帰ることが出来ません。
結局 Bも含め n-1 人にそれぞれ一着ずつ、持ち帰ることが出来ないコートがありますので、P(n-1) を求めることになります。
以上のことから、A が b を持ち帰る場合の数は
P(n-2) + P(n-1)
となります。
従って求める P(n) は
P(n) = (n-1) { P(n-2) + P(n-1) }
で計算できますね。
P(1) = 0 と P(2) = 1 は容易に分かりますから、
P(3) = 2 ( 0 + 1 ) = 2
P(4) = 3 ( 1 + 2 ) = 9
P(5) = 4 ( 2 + 9 ) = 44
と、5人の場合が 44 通りと分かります。
（この記事は「Yahoo知恵袋」より引用させて頂きました）
コートの取り違えの問題
ホテルのクロークで、5人がコートを預けました。
用事が済んでコートを返してもらった時、5人全員が自分のものではないコートを受け取る場合の数は何とおり？
という問題を先輩からクイズで出されたのですが、考えれば考えるほどこんがらがってきます。
うまい方法はないでしょうか。
- 回答 -
モンモールの問題とよばれる有名な問題です。
色々な考え方がありますが、円順列を用いる方法を書いてみます。
5 人が手をつないで輪になったと思って下さい。
このとき、自分の右の人に、つまり右手をつないだ人に自分のコートを渡すと考えます。
この場合は、5 人全員でコートを交換することになります。
5 人の円順列ですから、ここまでに24 通りあります。
でも、これだけでなく、3 人の間でコートを交換し、残った 2 人の間で交換するという方法もあります。
これが先の 5 人の場合と違うことを図でも描いて確かめてみて下さい。
さて、この場合は、まず 2 人を選ぶ方法が 5C2 の 10 通りで、それぞれに対しコートの渡し方は 3 人の円順列で 2 通り（2人の方は1通りですね）。
ですから、この場合の総数は
10 × 2
の 20 通り。
従って先の 24 通りと合わせて全部で 44 通りになりますね。
【追加】
一応、一般の場合もやっておきましょうか。
上に書いた円順列を用いても出来ますが、普通の方法で。
n人を大文字A〜で、コートを対応する小文字a〜で表します。
まず、Aが持ち帰るコートはb〜の n-1 通りで、そのうちの b を持ち帰った場合を考えます。求める総数は、これに n-1 を掛ければいいですね。
A が b を持ち帰り、その A のコートaを B が持ち帰れば、残った人とコートは C〜 と c〜 の n-2 組ですので、これは n-2 人が n-2着のコートを持ち帰るという問題に帰着します。
つまり、本問の n が n-2 に変わっただけ。
その総数を P(n-2) と表しましょう。
本問の目的は P(n) を求めることです。
次に、B が a 以外のコートを持ち帰った場合を考えます。
この場合、B は a を持ち帰ることが出来ず、残った C〜 の n-2 人は自分のコートを持ち帰ることが出来ません。
結局 Bも含め n-1 人にそれぞれ一着ずつ、持ち帰ることが出来ないコートがありますので、P(n-1) を求めることになります。
以上のことから、A が b を持ち帰る場合の数は
P(n-2) + P(n-1)
となります。
従って求める P(n) は
P(n) = (n-1) { P(n-2) + P(n-1) }
で計算できますね。
P(1) = 0 と P(2) = 1 は容易に分かりますから、
P(3) = 2 ( 0 + 1 ) = 2
P(4) = 3 ( 1 + 2 ) = 9
P(5) = 4 ( 2 + 9 ) = 44
と、5人の場合が 44 通りと分かります。
（この記事は「Yahoo知恵袋」より引用させて頂きました）
- URL |
