本屋さんで「数の本」という本を見つけました。
 |
数の本 J.H. コンウェイ R.K. ガイ John Horton Conway Richard K. Guy シュプリンガー・フェアラーク東京 2001-12 by G-Tools |
その名の通り、数にまつわる色んな話題が満載なんですけど、そんな中で
「カタラン数」を扱ったものが面白かったので、ちょっとアレンジして、
紹介してみます。
本に載ってたのは円卓での握手の問題なんですが、もう少し分かりやすく(?)
切符の問題で。
出典は、下のサイトさんからです。
http://aozoragakuen.sakura.ne.jp/taiwa/node86.html
では、問題です。
切符売場に１枚500円の切符を買うために、10人が並んでいます。
このうち、5人が500円硬貨を持っています。
残りの5人は1000円札しか持っていません。切符を売り始めた時点で、売場にお金がないとした時、
切符を買う人が誰も釣り銭ができるのを待たずに買える確率は？
仮に、500円硬貨を持ってる人をA、1000円札しか持ってない人を
Bとすると、たとえば、下の順番で売り場にやってくると、待たずに買えますね。
A→B→A→B→A→A→B→A→B→B
逆に、最初にBが来ちゃったら、その時点でアウトです。
さて、分かった方は、コメントで。
ちなみに、ヒント&解答は、続きのほうで。
もう少し人数を少なくすると、分かりやすいかもですね。
たとえば、4人中、それぞれ2人だとすると、うまくいくのは以下の2通り
しかありません。
A→A→B→B
A→B→A→B
うまくいかないパターンも含めた全パターンは、以下の6通りです。
A→A→B→B：OK
A→B→A→B：OK
A→B→B→A：3番目でNG
B→A→A→B：最初からNG
B→A→B→A：最初からNG
B→B→A→A：最初からNG
ここからは、白文字反転ヒント&解答にしておきますね。
全パターンの数は、以下の式で算出できます。(2*n人の場合)
(2*n)! / ( n! * n! )
つまり、10人だと、(10!)/(5!*5!) = 3628800/(120*120) = 252通り
ということになります。
で、うまくいくのは、その時までに買った人のうち、500円硬貨を
持ってる人のほうが1000円札しか持ってない人より多い場合です。
ここが、まさにカタラン数になってます。
で、10人だと、うまくいくのは(10*9*8*7*6)/(6*5*4*3*2*1) = 42通り
ですから答えは、『1/6』となります。
ヒントを見ても「なんじゃ、これ!?」って感じかもですね。
私もかなり悩みました。
さきほどの出典元サイトでは図解して説明してくれてますから、納得がいかなかった
方は、ご覧になってみると良いかもです。
また、円卓の問題も掲載されてますので。