東北大学 2019年度後期・理系数学後期第5問解答・解説

問題

1枚のコインを投げる試行を繰り返し，数列 ${a_{n}}$ $(n = 1, 2, 3, \dots)$ を次のように定める。

(i) 1回目の試行において表が出たとき， $a_{1} = 0$ とする。

(ii) 1回目の試行において裏が出たとき， $a_{1} = 1$ とする。

(iii) $n ≧ 2$ について， $n$ 回目の試行において表が出たとき， $a_{n} = a_{n - 1}$ とする。

(iv) $n ≧ 2$ について， $n$ 回目の試行において裏が出たとき， $a_{n} = a_{n - 1} + 2^{n - 1}$ とする。

以下の問いに答えよ。

(1) $a_{10}$ が $2^{10}$ を3で割った商に等しくなったとき，1回目から10回目の試行におけるコインの表裏の出方を求めよ。

(2) 1回目から100回目の試行においてコインの表がちょうど4回出たとき， $a_{100}$ が $\frac{2 ^{100}}{3}$ より小さくなる条件付き確率を求めよ。

出典：東北大学 2019年度後期日程第2次学力試験後期・理系後期第5問

方針

解法1（表の回に対応する2の累乗を引く）

$a_{n}$ は、裏が出た回に対応する2進法の桁を1にした数である。(1)は $2^{10}$ を3で割った商を2進法で表せば、裏が出た回が読める。(2)は表が出た回の集合 $H$ を用いて、 $a_{100} = 2^{100} - 1 - \sum_{j \in H} 2^{j - 1}$ と表す。条件 $a_{100} < 2^{100} /3$ は高位4桁の選び方の不等式になり、最大桁から順に必要条件を詰めて数える。

解法2（2進表示を辞書順に比較する）

表を0、裏を1として、1回目から順に2進表示の下位桁から対応させる。(2)では向きを高位桁から読むため、100回目から1回目への0・1列を考え、基準値 $0101 \dots 01$ と辞書順に比較する。

解答

解法1（表の回に対応する2の累乗を引く）

(1)

$a_{10}$ は、裏が出た回に対応する $2^{0}, 2^{1}, \dots, 2^{9}$ を足した数である。 $2^{10} = 1024$ であり、これを3で割った商は $341$ である。これを2の累乗の和で表すと $341 = 2^{8} + 2^{6} + 2^{4} + 2^{2} + 2^{0}$ である。

したがって、裏が出たのは $1, 3, 5, 7, 9$ 回目であり、表が出たのは $2, 4, 6, 8, 10$ 回目である。よって出方は、1回目から順に「裏、表、裏、表、裏、表、裏、表、裏、表」である。

(2)

1回目から100回目のうち、表が出た回の集合を $H$ とする。表はちょうど4回なので、 $H$ は ${1, 2, \dots, 100}$ の4個の元からなる部分集合である。裏が出た回の桁が1になるので $a_{100} = 2^{100} - 1 - \sum_{j \in H} 2^{j - 1}$ である。 $2^{100} \equiv 1 (mod 3)$ なので $q = \frac{2 ^{100} - 1}{3}$ は整数である。 $a_{100} < \frac{2 ^{100}}{3}$ は、 $a_{100}$ が整数であることから $a_{100} ≦ q$ と同値である。したがって $\sum_{j \in H} 2^{j - 1} ≧ 2^{100} - 1 - q = \frac{2 ( 2 ^{100} - 1 )}{3}$ である。右辺は $\frac{2 ( 2 ^{100} - 1 )}{3} = 2^{99} + 2^{97} + \dots + 2^{1}$ である。

ここで指数で数えるため、 $E = {j - 1 ∣ j \in H}$ とおく。 $E$ は $0, 1, \dots, 99$ から4個選ぶ集合である。条件は $\sum_{e \in E} 2^{e} ≧ 2^{99} + 2^{97} + \dots + 2^{1}$ である。

まず $99 \in E$ が必要である。もし最大指数が98以下なら、最大でも $2^{98} + 2^{97} + 2^{96} + 2^{95} < 2^{99}$ となり、右辺に届かないからである。 $99 \in E$ とする。さらに $98 \in E$ なら、残り2個の指数は $0$ から97までの中から自由に選べる。これは $_{98} C_{2}$ 通りである。

次に $98 \in / E$ とする。このとき $97 \in E$ が必要である。もし最大が96以下なら、残り3個の和は右辺の $2^{97}$ に届かないからである。 $99, 97 \in E$ 、 $98 \in / E$ のもとで、残り2個を選ぶ。 $96 \in E$ なら、もう1個は $0$ から95まで自由に選べるので96通りである。 $96 \in / E$ の場合は、 $95$ と $94$ をともに選ぶ場合だけが条件を満たす。実際、 $2^{95} + 2^{94}$ は残りの必要量 $2^{95} + 2^{93} + \dots + 2^{1}$ 以上であり、 $94$ より小さい指数では足りない。

したがって条件を満たす表の出方は $_{98} C_{2} + 96 + 1 = 4753 + 97 = 4850$ 通りである。表がちょうど4回出る出方は全体で $_{100} C_{4}$ 通りで、どれも同様に確からしい。よって条件付き確率は $\frac{4850}{_{100} C _{4}} = \frac{2}{1617}$ である。

解法2（2進表示を辞書順に比較する）

(1)

$j$ 回目が裏なら $2^{j - 1}$ が加わり、表なら加わらない。したがって $a_{10}$ の2進表示は、10回目から1回目の順に表を0、裏を1として並べたものになる。

\frac{2 ^{10} - 1}{3} = 341 = (0101010101)_{2} .

$2^{10}$ を3で割った商も341なので、1回目から順に読むと

裏、表、裏、表、裏、表、裏、表、裏、表

である。

(2)

$a_{100}$ は整数だから

a_{100} < \frac{2 ^{100}}{3}

は

a_{100} ≦ \frac{2 ^{100} - 1}{3}

と同値である。右辺の100桁の2進表示は

0101 \dots 0101

である。

表がちょうど4回という条件は、100桁中の0がちょうど4個ということである。高位桁から基準列と比較すると、条件を満たす列は次の3種類に尽きる。

先頭の形 00 \dots 0100 \dots 01010011 \dots 1 残る 0 の置き方 残り 98 桁から 2 個 残り 96 桁から 1 個 1 通り

したがって有利な出方は

_{98} C_{2} + 96 + 1 = 4850

通りである。表が4回出る全出方は $_{100} C_{4}$ 通りなので

\frac{4850}{_{100} C _{4}} = \frac{2}{1617} .

東北大学 2019年度後期・理系数学 後期 第5問

問題

方針

解法1（表の回に対応する2の累乗を引く）

解法2（2進表示を辞書順に比較する）

解答

解法1（表の回に対応する2の累乗を引く）

(1)

(2)

解法2（2進表示を辞書順に比較する）

(1)

(2)

東北大学 2019年度
後期・理系数学後期第5問