Evolton

北海道大学 1986年度 前期日程 第2次学力試験理系数学 第5問

数直線上の整数点x=1, 2, 3, ⋯⋯ , nに,
合計n個の黒または白の石を1つずつ,
黒石どうしは隣り合わないように置く.
黒石を3個使う置き方は何通りあるか.
ただし,n≧5とする.

難易度3/ 10計算量2/ 10目安12分

場合の数 数え上げ、場合分け

方針

黒石を置く3つの位置を選べば、残りの位置はすべて白石で決まる。したがって、1≦x1<x2<x3≦n かつ隣り合わない、つまり x2≧x1+2、x3≧x2+2 を満たす3点の選び方を数えればよい。隙間を1つずつ詰める変換 y1=x1、y2=x2−1、y3=x3−2 によって、1 から n−2 までの中から3個選ぶ問題に直す。別解として、3個の黒石の間と両端の白石数を分配して数える方法もある。

解答

黒石を置く位置を 1≦x1<x2<x3≦n とする。黒石どうしが隣り合わない条件は x2≧x1+2,x3≧x2+2 である。

そこで y1=x1,y2=x2−1,y3=x3−2 とおく。このとき 1≦y1<y2<y3≦n−2 である。逆に、1≦y1<y2<y3≦n−2 を満たす3つの整数を選べば x1=y1,x2=y2+1,x3=y3+2 により、隣り合わない3つの黒石の位置がただ1通り定まる。

したがって置き方の数は、1,2,…,n−2 から3つを選ぶ数に等しい。よって n−2C3 通りである。

別解

解法2(白石をすき間へ分配)

方針

3個の黒石を先に置き、間の2か所に白石を1個ずつ必須配置する。残る白石を両端を含む4つのすき間へ分配し、非負整数解を数える。

解答

3個の黒石を黒 白 黒 白 黒の順に先に置く。これで黒石3個と必須の白石2個を使うので、残る白石は n−5 個である。

追加の白石を、左端、2つの黒石間、2つの黒石間、右端という4つのすき間へ入れる個数を u1,u2,u3,u4 とするとu1+u2+u3+u4=n−5,ui≧0.この非負整数解の個数は n−2C3である。各解から石の並びが一意に決まり、逆も成り立つので、求める置き方は n−2C3通りである。

総評

隣接しない位置の選択を数える問題で、目安は12分。位置を詰める方法と、必須の白石を先に置いてすき間へ分配する方法が対応する。n=5では黒白黒白黒の1通りとなり公式の端も確認できる。

Evolton Pro

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

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

出典: 北海道大学 1986年度 前期 数学。問題文はHTML表示のために再入力・数式組版しています。