本屋さんで「数の本」という本を見つけました。
 |
数の本 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』となります。
ヒントを見ても「なんじゃ、これ!?」って感じかもですね。
私もかなり悩みました。
さきほどの出典元サイトでは図解して説明してくれてますから、納得がいかなかった
方は、ご覧になってみると良いかもです。
また、円卓の問題も掲載されてますので。
(当サイトでは、Amazonアソシエイトをはじめとした第三者配信のアフィリエイトプログラムにより商品をご紹介致しております。)
