今回の記事は本選の第３問です。問題はこちらです。
なかなかとっかかりが見えない難問です。ヒントは偶数奇数に注目することか。
今回は以下の方針でとくことができます。
「f(n) ≠ n ならばfk(n)=nとなるkは偶数になれば都合がいい。これができれば偶数個ずつSの元を除外できるがSは奇数個なので最小でも1個残る。これがf(n)=nをみたす。」
ということで「f(n) ≠ nのときfk(n)=nとなるkは偶数」をがんばって示していくことになります。
このanが1でないならば偶数になるかどうかを検証したいです。
次はグループ用の準備をします。まずはnから操作を繰り返して得られるグループを作ります。
fm1(n)=fm2(n)となるようなm1,m2(m1 ≦ m2)があるならばf(n)=f(m)となるときn=mとなることから
fm1– 1(n)=fm2-1(n)が成立し、
以降順次議論していくことでf0(n)=fm2-m1(n)が得られる。
m2-m1 < amなのでamの作り方からm2=m1がわかる。
この次はそのグループの性質を探ります。
fan+k(n) = fk(n)となることから
すべての整数kについてan=afk(n)がいえる。
これで準備が整いました。ここからは関係式をいじって性質を探っていきます。
fnf(n)(n)=nであるので、nf(n)はanで割り切れる。
anは1でないのでnとf(n)の少なくとも一方はanと互いに素でない。
そこでまずはnとanが1でない公約数dをもっている場合を考える。
n+f(n)+1もanで割り切れるのでdの倍数であるから、f(n)+1もdの倍数である。
したがってf(n)とdは互いに素であることがわかる。
また関係式fn+f(n)+1(n)=nにおいてnをfk(n)に置き換えると
ffk(n)+fk+1(n)+1(fk(n))=fk(n)
が成り立つ。したがって
fk(n)+fk+1(n)+1もanの倍数であり
さらにkをk+1に置き換えたfk+1(n)+fk+2(n)+1もanの倍数なので
差をとって得られるfk+2(n)-fk(n)もanの倍数である。
これらを順次適用していくと
n,f2(n), … はdの倍数であり、f(n),f3(n), …はすべてdと互いに素である。
したがってfan(n)=nでとくにdの倍数なのでanは偶数でなければならないことがいえる。
これで有用そうな偶奇に関係する性質が得られました。
残りも忘れずおさえましょう。
上と同様な議論により
n,f2(n), … はすべてdと互いに素であり、f(n),f3(n), …はdの倍数であることがわかる。
したがってfan(n)=nでとくにdと互いに素なのでanは偶数でなければならないことがいえる。
これでanが1か偶数であることがわかりましたので、あとはSからどんどん取り除いていくだけです。
Sにf(n) ≠ nとなる元nがある場合、Sの部分集合として{f(n),f2(n), … , fan(n)}をとることができる。
この部分集合の全ての元mについて、f(m)がその部分集合の元になっていることがわかり、また作り方とfの性質からf(m)がその部分集合の元になるならばmもその部分集合の元であることがわかる。
したがってSからその部分集合を除いてできる集合S’に対して、引き続き同様の議論が可能である。
しかし各操作で取り除ける元の個数は偶数個でSの元は999個すなわち奇数なので、どのようにうまく除去できても最小で1個は残る。
残った元mはすなわちam=1をみたすものなのでf(m)=mをみたす。
すなわちSの元にはf(a)=aとなるaが必ず存在することが示される。□
ということで存在を示すことができました。かなり技巧的な方法を用いたと思います。