Evolton

東京大学 1996年度 後期日程 第2次学力試験理系(後期)数学 第1問

nを正の整数とし,n個のボールを3つの箱に分けて入れる問題を考える。ただし,1個のボールも入らない箱があってもよいものとする。次の4つの場合について,相異なる入れ方の総数を求めよ。

(1) 1からnまで異なる番号のついたn個のボールを,A,B,Cと区別された3つの箱に入れる場合。

(2) 互いに区別のつかないn個のボールを,A,B,Cと区別された3つの箱に入れる場合。

(3) 1からnまで異なる番号のついたn個のボールを,区別のつかない3つの箱に入れる場合。

(4) nが6の倍数6mであるとき,互いに区別のつかないn個のボールを,区別のつかない3つの箱に入れる場合。

難易度7/ 10計算量6/ 10目安25分

場合の数、整数 数え上げ、場合分け、対称性の利用、和の計算

方針

(1) は各ボールの箱選択,(2)は3変数の非負整数解として数える。(3)はいったん箱を区別した入れ方を,箱の6通りの並べ替えで分類し,それぞれに変わらない入れ方を数える。(4)は箱内の個数を0≦x≦y≦zと並べ,xごとに可能なyを加える。

解答

(1)

各ボールに3箱の選択肢があるので,3n.(2)

各箱の個数をx,y,zとすると,x+y+z=n,x,y,z≧0の整数解の数である。よって(n+1)(n+2)2.(3)

まず3箱を区別した3n通りを考える。箱の並べ替えは6通りある。何も動かさない並べ替えでは全3n通りが変わらない。

2箱だけを交換する並べ替えは3通りあり,各場合で変わらない入れ方は,動かさない1箱に全ボールを入れる1通りだけである。3箱を巡回させる2通りの並べ替えでは,n>0なので変わらない入れ方はない。

したがって,同じ入れ方が6回ずつ数えられることを補正すると,3n+36.(4)

3箱の個数を0≦x≦y≦z,x+y+z=6mとする。xは0から2mまで動き,固定したxに対してx≦y≦⌊6m−x2⌋.よって総数は∑x=02m(⌊6m−x2⌋−x+1).ここで⌊6m−x2⌋=3m−⌈x2⌉であり,∑x=02m⌈x2⌉=m(m+1)だから,総数は(2m+1)(3m+1)−m(2m+1)−m(m+1)=3m2+3m+1.

別解

解法2

方針

(3) は使用する箱の個数を1個,2個,3個に分け,番号つきボールの集合の分割として数える。(4)は箱の個数をi,i+j,i+j+kとおき,方程式3i+2j+k=6mの非負整数解をiの偶奇に分けて数える。

解答

(1)

各ボールについて入れる箱をA,B,Cの3通りから選べるので,3n.(2)

3箱のボール数をx,y,zとすれば,x+y+z=n,x,y,z≧0の整数解の個数である。仕切り2本を用いると,(n+1)(n+2)2.(3)

非空の箱が1個なら1通りである。非空の箱が2個なら,ボールの集合を空でない2組に分ける。まず一方の組を選ぶ方法は2n−2通りであるが,2組の交換を同一視するので2n−1−1通りである。

非空の箱が3個なら,いったん3箱を区別する。全割り当て3n通りから,指定した1箱が空であるものを引き,2箱が空であるものを戻すと3n−3⋅2n+3通りである。3箱の並べ替え6通りを同一視するので3n−3⋅2n+36通りである。以上の和は1+(2n−1−1)+3n−3⋅2n+36=3n+36.(4)

3箱の個数を小さい順にi,i+j,i+j+kとおく。ここでi,j,kは非負整数である。和が6mだから3i+2j+k=6m.固定したiに対し,0≦j≦⌊6m−3i2⌋であり,kは一意に決まる。

i=2rの場合は0≦r≦mで,個数は3(m−r)+1.i=2r+1の場合は0≦r≦m−1で,個数は3(m−r)−1.したがって総数は∑r=0m{3(m−r)+1}+∑r=0m−1{3(m−r)−1}=3m2+3m+1.

総評

難度7、計算量6。4種類の『区別』を混同しないことが中心である。(3)は空箱を含むため箱の置換の固定点を正しく数え、(4)は順序づけた個数の範囲と床関数の偶奇和を明示した。 2解法の結論を相互照合し,定義域,端点,場合分け,図示範囲を確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の場合の数の問題で問題集を作る

出典: 東京大学 1996年度 後期日程 第2次学力試験 理系(後期) 後期 第1問。問題文はHTML表示のために再入力・数式組版しています。