MathLabs

第4問

非負整数全体からそれ自身への関数 ff で、すべての非負整数 nn に対して f(f(n))=n+1987f(f(n)) = n + 1987 を満たすものが存在しないことを証明せよ。
ステップ 4/5: 二つの部分はちょうど 1987 個の元を分割する
前のステップ次のステップ
ざっくり言うと

二回目の反復は最初の 1987 個の非負整数をちょうど取り逃がし、A と B はその取り逃がされた集合を二つの層に分ける。

A∩B=∅,A∪B=N0∖f(f(N0))={0,1,…,1986}A\cap B=\varnothing,\qquad A\cup B=\mathbb N_0\setminus f(f(\mathbb N_0))=\{0,1,\ldots,1986\}
詳しい解説

AA と BB は互いに素である:AA は f(N0)f(\mathbb N_0) の外側にあり、B⊆f(N0)B\subseteq f(\mathbb N_0) だからである。AA は f(N0)f(\mathbb N_0) の補集合、BB は f(N0)f(\mathbb N_0) のうち f(f(N0))f(f(\mathbb N_0)) の外側の部分なので、それらの和集合は f(f(N0))f(f(\mathbb N_0)) の補集合である。関数方程式から f(f(N0))={n+1987:n≥0}={1987,1988,…}f(f(\mathbb N_0))=\{n+1987:n\ge0\}=\{1987,1988,\ldots\}、したがって和集合は {0,1,…,1986}\{0,1,\ldots,1986\} で、その大きさは 19871987 である。