東京大学 2004年度 後期日程 第2次学力試験理系（後期）数学 第2問

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

(2) 与えられた表を2進数の下3桁で見ると、入力 $4u+2v+w$ に対して$$f(4u+2v+w)=\{\begin{array}{ll}0& (v=w),\\ 1& (v\mathrm{\ne }w)\end{array}$$であり、最上位の $u$ には依存しない。また $f(0)=0,f(1)=1$ である。目標の $b_k$ は奇数番目で0、偶数番目で1だから、$a_1=0$ であり、$k\geqq 2$ では$$a_k=\{\begin{array}{ll}{a}_{k-1}& (k\text{が奇数}),\\ 1-a_{k-1}& (k\text{が偶数})\end{array}$$とすればよい。よって$$(a_1,a_2,a_3,a_4,\dots )=(0,1,1,0,0,1,1,0,\dots ),$$すなわち$$a_k=\{\begin{array}{ll}1& (k\equiv 2,3(\mathrm{m}\mathrm{o}\mathrm{d}4)),\\ 0& (k\equiv 0,1(\mathrm{m}\mathrm{o}\mathrm{d}4))\end{array}$$である。

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

(4) 任意の01数列 $b_1,\dots ,b_N$ を固定する。まず $f(0)\mathrm{\ne }f(1)$ だから、$f(a_1)=b_1$ となる $a_1\in \{0,1\}$ がただ一つ存在する。

$a_1,\dots ,a_{k-1}$ まで選べたとする。$k=2$ では入力候補は $2a_1$ と $2a_1+1$、$k\geqq 3$ では$$4a_{k-2}+2a_{k-1},4a_{k-2}+2a_{k-1}+1$$である。いずれも $2m,2m+1$ という一組である。条件(P)によりこの二つの $f$ の値は0と1を一つずつ取るから、$b_k$ を得る方を $a_k$ としてただ一つ選べる。

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

条件・検算

各段階で候補入力は必ず $2m,2m+1$ の対になり、条件(P)により出力0と1が1つずつ現れる。したがって構成は途中で止まらず、しかも一意である。