トップ› 北海道大学› 1976年› 理系第2問

北海道大学 1976年理系第2問解説

注意画像の一部が不鮮明で、特に「集合 $S$ の末尾の要素」の読取りに不確実性があります。画像では $a_5$ が重複しているように見えますが、「相異なる6個の整数」という問題の前提から、以下は「$S=\{a_1, a_2, a_3, a_4, a_5, a_6\}$」として解釈した場合の解答解説です。

方針・初手

(1) は、6個の要素からなる集合の部分集合の総数を考え、そこから空集合の分を除外する。
(2) は、各部分集合の和を直接足し合わせるのではなく、特定の要素 $a_k$ がすべての部分集合の中で何回足されることになるかに着目する。
(3) は、条件を満たす4個の要素を $S$ から選び、それらを集合 $A$ と $B$ にどのように分配するかを考える。

解法1

(1)

相異なる6個の要素からなる集合 $S$ の部分集合の総数は $2^6$ 個である。

このうち、空集合は1個であるから、空集合でない部分集合の個数は

$$2^6 - 1 = 64 - 1 = 63$$

となる。

(2)

3個の要素からなる $S$ の部分集合は全部で ${}_6\mathrm{C}_3$ 個ある。

これらすべての部分集合における要素の和の総計を考える。

特定の要素、たとえば $a_k \ (1 \leqq k \leqq 6)$ を含む部分集合の個数は、$S$ の残り5個の要素から2個を選ぶ選び方に等しいため、${}_5\mathrm{C}_2$ 個である。

したがって、要素 $a_k$ はすべての $T$ の和の中で ${}_5\mathrm{C}_2$ 回足し合わされることになる。

これは $a_1$ から $a_6$ までのすべての要素について同様に成り立つ。

よって、すべての $T$ の和は

$$\sum_{k=1}^{6} {}_5\mathrm{C}_2 a_k = 10 \sum_{k=1}^{6} a_k = 10 (a_1 + a_2 + a_3 + a_4 + a_5 + a_6)$$

となる。

(3)

まず、$S$ の6個の要素から、$A$ と $B$ に属する合計4個の要素を選ぶ。

その選び方は ${}_6\mathrm{C}_4$ 通りである。

選んだ4個の要素を値の小さい順に $x_1, x_2, x_3, x_4$ とする（$x_1 < x_2 < x_3 < x_4$）。

$A, B$ はともに2個の要素からなり、$A \cap B = \phi$ であるから、この4個の要素を2個ずつ $A$ と $B$ に振り分ければよい。

条件「$A$ の要素の最小数は $B$ の要素の最小数より小さい」を満たすためには、4つの要素の中で最小である $x_1$ が必ず集合 $A$ に属していなければならない。

したがって、$A$ の要素は $x_1$ と、残り3つの要素 $x_2, x_3, x_4$ の中から選んだ1つの要素の組となる。

$A$ のもう1つの要素の選び方は ${}_3\mathrm{C}_1$ 通りである。

$A$ の要素が決まれば、残った2つの要素が自動的に $B$ の要素となる。

以上より、求める組の個数は

$${}_6\mathrm{C}_4 \times {}_3\mathrm{C}_1 = 15 \times 3 = 45$$

となる。

解法2

(3) の別解

$A$ と $B$ を順に選ぶ方法を考える。

まず、$S$ の6個の要素から $A$ の要素2個を選ぶ選び方は ${}_6\mathrm{C}_2$ 通りである。

次に、残った4個の要素から $B$ の要素2個を選ぶ選び方は ${}_4\mathrm{C}_2$ 通りである。

よって、$A \cap B = \phi$ を満たす順序付きのペア $(A, B)$ の総数は

$${}_6\mathrm{C}_2 \times {}_4\mathrm{C}_2 = 15 \times 6 = 90$$

通りである。

ここで、選ばれた $A$ と $B$ は互いに素であるから、それぞれの集合の最小の要素は必ず異なる値をとる。

したがって、全90通りのうち、「$A$ の最小要素 $< B$ の最小要素」となるものと、「$B$ の最小要素 $< A$ の最小要素」となるものは対称性により同数存在する。

よって、求める条件を満たす組の数は

$$\frac{90}{2} = 45$$

となる。

解説

(1) は部分集合の総数についての基本的な問題である。
(2) は各部分集合ごとに和を考えるのではなく、各要素が何個の部分集合に属するかを考える「主客転倒」の考え方を用いると計算量を大幅に減らすことができる。
(3) は条件の処理の仕方が問われる。解法1のように要素を先に選んでから分配すると見通しが良く、解法2のような対称性を利用する考え方も確率や組合せの問題で非常に強力である。