• 098月

    本屋さんで「数の本」という本を見つけました。

    4431707700 数の本
    J.H. コンウェイ R.K. ガイ John Horton Conway Richard K. Guy
    シュプリンガー・フェアラーク東京 2001-12

    by G-Tools

    その名の通り、数にまつわる色んな話題が満載なんですけど、そんな中で
    「カタラン数」を扱ったものが面白かったので、ちょっとアレンジして、
    紹介してみます。

    本に載ってたのは円卓での握手の問題なんですが、もう少し分かりやすく(?)
    切符の問題で。
    出典は、下のサイトさんからです。
    http://aozoragakuen.sakura.ne.jp/taiwa/node86.html

    では、問題です。

    切符売場に1枚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』となります。

    ヒントを見ても「なんじゃ、これ!?」って感じかもですね。
    私もかなり悩みました。

    さきほどの出典元サイトでは図解して説明してくれてますから、納得がいかなかった
    方は、ご覧になってみると良いかもです。
    また、円卓の問題も掲載されてますので。

    Filed under: 雑学
    2005/08/09 9:37 pm | 数の本とカタラン数 はコメントを受け付けていません

Comments are closed.