区別のつかないn個のものを3つの箱に入れる場合の数（上級問題精講704）
Ciao!
数学リストランテへようこそ。
今回紹介する問題は上級問題精講を参照しました東京大学の問題です。
このブログでよく取り扱う参考書
上級問題精講でも難問として扱われるレベルの問題です。非常に解き甲斐のある問題になっています。では見ていきましょう。
まず1番ですが、これは大丈夫でしょう。入れ方の総和は3つの文字A.B.Cから重複を許してn個取り出す場合の数に等しいので、重複組み合わせに帰着させます。
n個の○と2つの/の順列と対応しているイメージを持ってn+2C2=1/2(n+1)(n+2)となります。
さあ問題は2番です。
（んー。1番を分解したような感じか、でもn個のボールは区別がつかないからな、1番では1スペース取ったり、3スペース取ったり、3！スペース取ったりするものが2では対等に扱われるってことか。んー。考えずらい。1番から2番への変換を考えるんだったら場合分けをして割る1割る3割る6するんか、でもその場合分けって、、、、）
頭がこんがりますよね。見方を変えましょう。2番の分け方をした後、それぞれの箱にA,B,Cと名前をつけるってゆうのはどうでしょう、逆からの発想ですよね。
これが上手くハマるんです。
2番の求める入れ方がN通りあるとします。3つの箱に入るボールの数が
①全て等しい
②2つだけが等しい
③いずれも異なる
で場合分けをしましょう。
①は全て2mの1通りで、2番から1番への名前付けも1通りです。
②は(0,0,6m),(1,1,6m-2),‥‥,(3m,3m,0)の3m+1通りから(2m,2m,2m,)を引いた3m通りで、2番から1番の名前付けは3通りある。
③は直接求めるのは難しいのでN-(①+②)と余事象的に考える。2番から1番への名前付けは6通りである。
これらの関係式を立てると
①+3②+6③=（1番の入れ方）
n=6mを考慮すると
1+3/2n+6{N-(1+1/2n)}=1/2(n+1)(n+2)
となりあとはこれを解くだけです。
今回は赤線部で勝負あったなって感じですよね。
実はこの解法と非常に似ている問題が日本の数学オリンピック予選問題であったんですよね。
この問題ですね。是非考えてみてください。解ければ猛者間違いなしです。
ちなみにこの問題集は組み合わせ論パーフェクトマスターです。鈴木晋一さんの本で数学オリンピックでの組み合わせ論の問題を集めたものになります。受験数学が緩いと感じる人は是非挑戦してみてください。格の違いを見せつけられます。
数学aに分類される整数、場合のかず・確率、幾何はどれも思考力が問われる問題が多く、数学オリンピックなどでも多く出題される分野でもあり僕はめちゃめちゃ好きな単元なんですが、その中でも場合の数・確率は好きです。整数と幾何は初めの方針で全てが決まるような問題が少なく、ゴリゴリ議論を重ねていく中での思考力だったりってゆう、そうゆう迷路みたいな感覚に近いところあるんですけど、場合の数とか確率って初めの計画立てのところでほとんど勝負がつくみたいな問題が多くて、「解けた！」感を凝縮して味わえるので僕は好きです。
Grazie! 最後までご覧いただきありがとうございました。
