トップ› 東京工業大学› 2013年› 理系第1問

東京工業大学 2013年理系第1問解説

方針・初手

(1) 与えられた2次方程式から解と係数の関係を用いて $\alpha + \beta$ と $\alpha\beta$ の値を求める。対称式 $\alpha^n + \beta^n$ に関する問題なので、$c_n = \alpha^n + \beta^n$ とおき、解が満たす方程式を利用して $c_n$ の隣接3項間の漸化式を導くのが定石である。その後は数学的帰納法により証明を進める。

(2) 6個のさいころの目の出方はすべてで $6^6$ 通りである。「ちょうど4種類の目が出る」という条件を満たす場合の数を求める。まず4種類の目の選び方を計算し、それらが6個のさいころにどのように割り当てられるかを「出目の回数の型」で場合分けして数え上げる方針、または包除原理を用いて「4種類の目がすべて少なくとも1回出る」場合を数え上げる方針が考えられる。

解法1

(1)

$c_n = \alpha^n + \beta^n$ とおく。

2次方程式 $x^2 - 3x + 5 = 0$ の2つの解が $\alpha, \beta$ であるから、解と係数の関係より

$$ \begin{aligned} \alpha + \beta &= 3 \\ \alpha \beta &= 5 \end{aligned} $$

が成り立つ。

また、$\alpha, \beta$ は方程式の解であるから $\alpha^2 - 3\alpha + 5 = 0, \beta^2 - 3\beta + 5 = 0$ を満たし、移項して

$$ \begin{aligned} \alpha^2 &= 3\alpha - 5 \\ \beta^2 &= 3\beta - 5 \end{aligned} $$

となる。これらの両辺にそれぞれ $\alpha^n, \beta^n$ を掛けると

$$ \begin{aligned} \alpha^{n+2} &= 3\alpha^{n+1} - 5\alpha^n \\ \beta^{n+2} &= 3\beta^{n+1} - 5\beta^n \end{aligned} $$

を得る。これらを辺々加えると、数列 $c_n$ についての隣接3項間の漸化式

$$ c_{n+2} = 3c_{n+1} - 5c_n $$

が得られる。

これを用いて、「すべての正の整数 $n$ について $c_n$ は整数であり、$c_n \equiv 3^n \pmod 5$ が成り立つ」こと（命題 $P(n)$ とする）を数学的帰納法により証明する。

(i)

$n=1, 2$ のとき

$$ \begin{aligned} c_1 &= \alpha + \beta = 3 \\ c_2 &= \alpha^2 + \beta^2 = (\alpha + \beta)^2 - 2\alpha\beta = 3^2 - 2 \cdot 5 = -1 \end{aligned} $$

よって $c_1, c_2$ は整数である。また、法を 5 として合同式を考えると

$$ \begin{aligned} c_1 &= 3 \equiv 3^1 \pmod 5 \\ c_2 &= -1 \equiv 4 \equiv 9 = 3^2 \pmod 5 \end{aligned} $$

となるため、$n=1, 2$ のとき命題 $P(n)$ は成り立つ。

(ii)

$n=k, k+1$ （$k$ は正の整数）のとき、命題 $P(n)$ が成り立つと仮定する。すなわち $c_k, c_{k+1}$ は整数であり、$c_k \equiv 3^k \pmod 5$, $c_{k+1} \equiv 3^{k+1} \pmod 5$ が成り立つとする。漸化式より

$$ c_{k+2} = 3c_{k+1} - 5c_k $$

仮定より $c_k, c_{k+1}$ は整数であるから $c_{k+2}$ も整数である。また、$c_k$ が整数であることから $5c_k$ は 5 の倍数であるため、合同式をとると

$$ c_{k+2} \equiv 3c_{k+1} \pmod 5 $$

となる。仮定より $c_{k+1} \equiv 3^{k+1} \pmod 5$ であるから

$$ c_{k+2} \equiv 3 \cdot 3^{k+1} = 3^{k+2} \pmod 5 $$

よって $n=k+2$ のときも命題 $P(n)$ は成り立つ。

(i), (ii) より、すべての正の整数 $n$ について $c_n$ は整数であり、$c_n \equiv 3^n \pmod 5$ が成り立つ。

したがって、$c_n - 3^n \equiv 0 \pmod 5$ であり、$\alpha^n + \beta^n - 3^n$ はすべての正の整数 $n$ について 5 の整数倍になる。（証明終）

(2)

6個のさいころの目の出方はすべてで $6^6 = 46656$ 通りであり、これらは同様に確からしい。

ちょうど4種類の目が出る事象について考える。まず、出る4種類の目の選び方は

$$ {}_6\mathrm{C}_{4} = 15 \text{（通り）} $$

である。

選ばれた4種類の目が、6個のさいころに何回ずつ出るかによって場合分けを行う。 4種類の目がすべて少なくとも1回は出るため、回数の組み合わせは以下の2つの型に限られる。

（ア） 1種類の目が3回、他の3種類の目が1回ずつ出る場合（3, 1, 1, 1 型）選ばれた4種類の目のうち、3回出る目の選び方が $4$ 通りある。その特定の目がどのさいころに出るかが ${}_6\mathrm{C}_{3}$ 通りであり、残りの3つのさいころには残りの3種類の目が1回ずつ出るのでその並べ方が $3!$ 通りある。したがって、この型になる目の出方は

$$ 4 \times {}_6\mathrm{C}_{3} \times 3! = 4 \times 20 \times 6 = 480 \text{（通り）} $$

（イ） 2種類の目が2回ずつ、他の2種類の目が1回ずつ出る場合（2, 2, 1, 1 型）選ばれた4種類の目のうち、2回出る2つの目の選び方が ${}_4\mathrm{C}_{2}$ 通りある。選ばれた4種類の目を（2回、2回、1回、1回）となるように6個のさいころに並べる場合の数は、同じものを含む順列を考えて $\frac{6!}{2!2!1!1!}$ 通りある。したがって、この型になる目の出方は

$$ {}_4\mathrm{C}_{2} \times \frac{6!}{2!2!1!1!} = 6 \times 180 = 1080 \text{（通り）} $$

(ア), (イ) より、特定の4種類の目がすべて少なくとも1回出る出方は

$$ 480 + 1080 = 1560 \text{（通り）} $$

全体として、ちょうど4種類の目が出る場合の数は、目の選び方と掛け合わせて

$$ 15 \times 1560 = 23400 \text{（通り）} $$

となる。

以上より、求める確率は

$$ \frac{23400}{46656} = \frac{325}{648} $$

解法2

(1)の別解

$a_n = \alpha^n + \beta^n - 3^n$ とおく。

解法1と同様にして、$\alpha + \beta = 3, \alpha\beta = 5$ であり、以下の式が成り立つ。

$$ \alpha^{n+2} + \beta^{n+2} = 3(\alpha^{n+1} + \beta^{n+1}) - 5(\alpha^n + \beta^n) $$

両辺から $3^{n+2}$ を引くと

$$ \alpha^{n+2} + \beta^{n+2} - 3^{n+2} = 3(\alpha^{n+1} + \beta^{n+1}) - 5(\alpha^n + \beta^n) - 3 \cdot 3^{n+1} $$

これを $a_n$ を用いて整理すると

$$ a_{n+2} = 3a_{n+1} - 5(\alpha^n + \beta^n) $$

が得られる。ここで、$\alpha^n + \beta^n$ は解法1で示した通りすべての正の整数 $n$ について整数である。

次に、$a_n$ が 5 の倍数であることを数学的帰納法で示す。

(i)

$n=1, 2$ のとき

$$ \begin{aligned} a_1 &= \alpha + \beta - 3 = 3 - 3 = 0 = 5 \times 0 \\ a_2 &= \alpha^2 + \beta^2 - 3^2 = -1 - 9 = -10 = 5 \times (-2) \end{aligned} $$

よって、$a_1, a_2$ は 5 の整数倍である。

(ii)

$n=k, k+1$ （$k$ は正の整数）のとき、$a_k, a_{k+1}$ が 5 の整数倍であると仮定する。

$$ a_{k+2} = 3a_{k+1} - 5(\alpha^k + \beta^k) $$

仮定より $a_{k+1}$ は 5 の倍数であり、$\alpha^k + \beta^k$ は整数であるから、$3a_{k+1}$ と $5(\alpha^k + \beta^k)$ はともに 5 の倍数である。ゆえに、それらの差である $a_{k+2}$ も 5 の倍数となる。

(i), (ii) より、すべての正の整数 $n$ について $a_n$ は 5 の整数倍になる。（証明終）

(2)の別解

特定の4種類の目がすべて少なくとも1回出る場合の数を、包除原理を用いて求める。

ある特定の4種類の目（例えば $1, 2, 3, 4$）だけで6個のさいころの目が出る場合の数は $4^6$ 通りである。このうち、出る目の種類が3種類以下になってしまうものを除く。

4種類のうち、特定の1種類の目が出ない（3種類以下の目しか出ない）場合の数出ない目の選び方が ${}_4\mathrm{C}_{1}$ 通りあり、その場合の数は ${}_4\mathrm{C}_{1} \times 3^6$ 通り。
4種類のうち、特定の2種類の目が出ない（2種類以下の目しか出ない）場合の数出ない目の選び方が ${}_4\mathrm{C}_{2}$ 通りあり、その場合の数は ${}_4\mathrm{C}_{2} \times 2^6$ 通り。
4種類のうち、特定の3種類の目が出ない（1種類の目しか出ない）場合の数出ない目の選び方が ${}_4\mathrm{C}_{3}$ 通りあり、その場合の数は ${}_4\mathrm{C}_{3} \times 1^6$ 通り。

包除原理により、特定の4種類の目のうち出ない目がある場合の数は

$$ \begin{aligned} {}_4\mathrm{C}_{1} \times 3^6 - {}_4\mathrm{C}_{2} \times 2^6 + {}_4\mathrm{C}_{3} \times 1^6 &= 4 \times 729 - 6 \times 64 + 4 \times 1 \\ &= 2916 - 384 + 4 \\ &= 2536 \text{（通り）} \end{aligned} $$

したがって、特定の4種類の目がすべて少なくとも1回出る場合の数は

$$ 4^6 - 2536 = 4096 - 2536 = 1560 \text{（通り）} $$

ちょうど4種類の目が出る場合の数は、4種類の目の選び方を掛けて

$$ {}_6\mathrm{C}_{4} \times 1560 = 15 \times 1560 = 23400 \text{（通り）} $$

求める確率は

$$ \frac{23400}{6^6} = \frac{325}{648} $$

解説

(1) は対称式の値が整数になることの証明と、倍数証明を融合した典型的な問題である。$\alpha^n + \beta^n$ のような形が現れたら、2次方程式から $x^2 = px + q$ の形を作り、両辺に $x^n$ を掛けて隣接3項間の漸化式を作る手法が非常に有効である。合同式を用いると、整数の性質の記述がすっきりとまとまる。

(2) は「部屋割りモデル（全射の個数）」と呼ばれる有名テーマである。区別できる $n$ 個のものを区別できる $k$ 個のグループ（空箱なし）に分ける場合の数は、型の分類で直接数え上げる方法と、包除原理を用いる方法の2パターンを習得しておくことが望ましい。本問程度の数であれば、型の分類（解法1）の方が計算ミスに気付きやすい場合がある。