東大(04後2)

集合 A, B を A = { 0, 1, 2, 3, 4, 5, 6, 7}, B = {0, 1} とし、N を 3 以上の整数とする。
また、各項が 0 または 1 からなる数列を 01 数列と呼ぶことにする。
01 数列 a₁, a₂,..., a_N に対し、A から B への写像 f を用いて新しい 01 数列 b₁, b₂,..., b_N を
　　b₁ = f(a₁), b₂ = f(2a₁+a₂),
　　 b_k = f(4a_k-2+2a_k-1+a_k)　　 (k = 3, 4, ..., N)
と定め b₁, b₂,..., b_N は 　 a₁, a₂,..., a_N から f によって得られるという。
ただし、A から B への写像 f とは、A の各要素 x に対して B の要素 f(x) を対応させる 規則をさすものとする。
　次の問いに答えよ。

(1)　A から B への写像は、全部で何通りあるか。
(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　　(k = 1, 2, ... , N)
となるような 01 数列 a₁, a₂,..., a_N をもとめよ。
(3)　A から B への写像 f が条件
　(P)　　f(2m) ≠ f(2m+1)　　(m = 0, 1, 2, 3)
を満たすとする。このような f は何通りあるか。
(4)　A から B への写像 f が条件 (P) を満たすならば、どのような N 項からなる 01 数列も、ある 01 数列 a₁, a₂,..., a_N から f によって 得られることを示せ。 　　

---

　ヒント　　 　問題１　　 　問題３　　 　

---