東京大学 2004年度後期・理系数学後期第2問解答・解説

問題

$A = {0, 1, \dots, 7}, B = {0, 1}$ 、 $N ≧ 3$ とする。01数列 $a_{1}, \dots, a_{N}$ と写像 $f : A \to B$ から、 $b_{1} = f (a_{1})$ 、 $b_{2} = f (2 a_{1} + a_{2})$ 、 $b_{k} = f (4 a_{k - 2} + 2 a_{k - 1} + a_{k})$ $(3 ≦ k ≦ N)$ を定める。

(1) 写像 $f$ の総数を求めよ。

(2) $f (0) = f (3) = f (4) = f (7) = 0$ 、 $f (1) = f (2) = f (5) = f (6) = 1$ のとき、 $b_{k} = {1 + (- 1)^{k}} /2$ となる $a_{k}$ を求めよ。

(3) $f (2 m) \neq = f (2 m + 1)$ $(m = 0, 1, 2, 3)$ を満たす $f$ の総数を求めよ。

(4) この条件を満たす $f$ では、任意の $N$ 項01数列がある01数列 $a_{1}, \dots, a_{N}$ から得られることを示せ。

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

方針

写像は8個の入力それぞれへの0,1の割当てとして数える。(2)では与えられた表が直前2項の排他的な違いを出力していることを読み取る。(4)では、過去の項を固定すると新しい項 $a_{k}$ の二つの候補が必ず連続する偶数・奇数の組になることを使い、先頭から順に構成する。

解答

(1)

$A$ の8個の各要素に対し、像は0または1の2通りから独立に選べる。したがって

2^{8} = 256

通りである。

(2)

与えられた表を2進数の下3桁で見ると、入力 $4 u + 2 v + w$ に対して

f (4 u + 2 v + w) = {01 (v = w), (v \neq = w)

であり、最上位の $u$ には依存しない。また $f (0) = 0, f (1) = 1$ である。目標の $b_{k}$ は奇数番目で0、偶数番目で1だから、 $a_{1} = 0$ であり、 $k ≧ 2$ では

a_{k} = {a_{k - 1} 1 - a_{k - 1} (k が奇数), (k が偶数)

とすればよい。よって

(a_{1}, a_{2}, a_{3}, a_{4}, \dots) = (0, 1, 1, 0, 0, 1, 1, 0, \dots),

すなわち

a_{k} = {10 (k \equiv 2, 3 (mod 4)), (k \equiv 0, 1 (mod 4))

である。

(3)

各組 ${2 m, 2 m + 1}$ では $f (2 m)$ を2通りから選ぶと $f (2 m + 1)$ はその反対に一意に決まる。4組は独立なので

2^{4} = 16

通りである。

(4)

任意の01数列 $b_{1}, \dots, b_{N}$ を固定する。まず $f (0) \neq = f (1)$ だから、 $f (a_{1}) = b_{1}$ となる $a_{1} \in {0, 1}$ がただ一つ存在する。

$a_{1}, \dots, a_{k - 1}$ まで選べたとする。 $k = 2$ では入力候補は $2 a_{1}$ と $2 a_{1} + 1$ 、 $k ≧ 3$ では

4 a_{k - 2} + 2 a_{k - 1}, 4 a_{k - 2} + 2 a_{k - 1} + 1

である。いずれも $2 m, 2 m + 1$ という一組である。条件(P)によりこの二つの $f$ の値は0と1を一つずつ取るから、 $b_{k}$ を得る方を $a_{k}$ としてただ一つ選べる。

以上を $k = N$ まで繰り返せば、与えられた任意の $b_{1}, \dots, b_{N}$ を生む01数列 $a_{1}, \dots, a_{N}$ が構成できる。

東京大学 2004年度後期・理系数学 後期 第2問

問題

方針

解答

(1)

(2)

(3)

(4)

東京大学 2004年度
後期・理系数学後期第2問