-
![]()
る.
【基礎0.10.6】 (1993AIME 問8 )
Sは6個の元からなる集合とする. Sのふたつの部
分集合 A, B を選びS = AUB とする方法は何通り
あるか ただし AnB≠中でもよく、 またAとB
を交換しただけのものは同一の方法とみなす.例え
ば A={a,c},B={b,c,d,e,f} と A = {b,c,d,e,
f}, B = {a, c} は同じとみなす.
解答n=#S=6とする. S=AUB のとき、各
s∈Sは, s∈A-B,s∈B-A, a∈ANB の3通
りの可能性がある. だから (A,B) と (B, A) を区別
して数えるとき, A, B の選び方は3通りある. ま
たA=BとなるのはA=B=Sの場合に限る. し
たがって (A,B) = (B, A) とみなす場合, その場合
3-1
の数は, +1=365 通りとなり、これが求め
2
る答である.
第 0.10.2 項 確率と期待値
起り得るすべての場合を分母として,問題になっ
ている事柄が起きる場合の比をその確率という.
例えば、ある事柄が起こった場合賞金 a(z) 円
がもらえる場合が起きる確率をP(x) として, す
48
の必要十分条件は、 1回目のくじで (k-1) 位以上
だった (k-1) 人のいずれよりも2回目のくじで上
位になること, いいかえると, 1回目のくじで位
以内のk人の中で2回目のくじが1位であることで
であるので 求める期待値は
ある。 この確率は
N
k=1
である.
有限集合
【基礎0.10.8】 (1994JMO 本選問5)
Nを正の整数とする. 1 から Nまでの数字を一つず
つ書いたくじがあり, N人でこのくじを引けば1位
からN位までの順位をつけることができる. N人
でこのくじ引きを2回行い、 次のようにして景品を
与える人を決めることにする.
「ある人Aに対して、 1回目と2回目の順位の双
方がともにAより上位である人Bがいる場合には
Aには景品を与えない. そのようなBがいない場
合に限りAに景品を与える. 例えば、 1回目で1位
を引いた人は2回目が何位であっても景品をもら
える」
このとき、景品をもらえる人数の期待値を求めよ.
ただしくじはあらかじめよくかきまぜてあり、2回
目のくじ引きの前にもう一度よくかきまぜるものと
する. また「景品をもらえる人数の期待値」とは, そ
れぞれの場合が起こる確率とその場合に景品をもら
える人数を掛けた値を、全部の場合について足し合
わせたものである.
解答 1回目のくじでk位の人が景品をもらうため
とする. もしbi がnで割り切れるなら, { (1,02....
} が求める部分集合である. そこで、どのbiもn
で割り切れないとする。これらをnで割ったときの
余りは 1,2,... n-1 のどれかであるから、 鳩の巣原
理によりnで割ったあまりが等しい2数が存在す
る. それらをbi, bj (i < j) とする. すると
It n
bj-bi = Qi+1 + ai+2 + ... + aj
で割り切れるから, {ai+1, Oi+2..... aj} が求め
