東大(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 によって 得られることを示せ。

---

ヒント
(1)　f(0) の可能性は 0 か 1 かの二通り、f(1) の可能性も 0 か 1 かの二通り、... 、 f(7) の可能性も 0 か 1 かの二通り。以上より写像は全部で 2⁸ 通りある。
(3)　f が (P) を満たすようにするには f(0),f(2),f(4),f(6) をまず決めて f(1) = 1 - f(0), f(3) = 1 - f(2), f(5) = 1 - f(4), f(7) = 1 - f(6) とすればよい。 答えは 2⁴ 通り
(2)　0 = b₁ = f(a₁) となるためには a₁ = 0
　　1 = b₂ = f(2a₁+a₂) = f(a₂) と成るためには a₂ = 1
　　0 = b₃ = f(4a₁+2a₂+a₃) = f(2+a₃) と成るためには a₃ = 1
　　1 = b₄ = f(4a₂+2a₃+a₄) = f(4+2+a₄) と成るためには a₄ = 0
　　0 = b₅ = f(4a₃+2a₄+a₅) = f(4+a₅) と成るためには a₅ = 0
　　1 = b₆ = f(4a₄+2a₅+a₆) = f(a₆) と成るためには a₆ = 1
　a₁, a₂,..., は 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, ... と類推される。
(m を自然数とするとき a_4m-3 = 0, a_4m-2 = 1, a_4m-1 = 1, a_4m-3 = 0 これが成り立つことを数学的帰納法で示せばよい。)
(4)　f を (P) を満たす写像として b₁, b₂,..., b_N を任意の 01 数列とする。
01 数列 a₁, a₂,..., a_N で, これから f により得られる数列が b₁, b₂,..., b_N になるものが存在することを N についての帰納法で示せばよい。

---

　解答　　 　もどる　　 　問題１　　 　問題３　　 　

---