数学オリンピック 2018 日本本選 3

今回の記事は本選の第３問です。問題は公式サイトで確認してください。

なかなかとっかかりが見えない難問です。ヒントは偶数奇数に注目することか。

今回は以下の方針でとくことができます。
「f(n) ≠ n ならばf^k(n)=nとなるkは偶数になれば都合がいい。これができれば偶数個ずつSの元を除外できるがSは奇数個なので最小でも1個残る。これがf(n)=nをみたす。」
ということで「f(n) ≠ nのときf^k(n)=nとなるkは偶数」をがんばって示していくことになります。

与えられた関係式からf^k(n)=nとなるようなkはすべてのSの元nに対して存在するので、それぞれのnに対して式が成立する最小の正の整数kをa_nとおく。

このa_nが1でないならば偶数になるかどうかを検証したいです。
次はグループ用の準備をします。まずはnから操作を繰り返して得られるグループを作ります。

このときf⁰(n)=nと考えてf⁰(n), … , f^a_n-1(n)を考える。
f^m₁(n)=f^m₂(n)となるようなm₁,m₂(m₁ ≦ m₂)があるならばf(n)=f(m)となるときn=mとなることから
f^{m₁– 1}(n)=f^m₂-1(n)が成立し、
以降順次議論していくことでf⁰(n)=f^m₂-m₁(n)が得られる。
m₂-m₁ < a_mなのでa_mの作り方からm₂=m₁がわかる。

この次はそのグループの性質を探ります。

また、f^a_n(n) = f⁰(n)であるのでさらに操作をk回施すと
f^a_n+k(n) = f^k(n)となることから
すべての整数kについてa_n=a_f^k(n)がいえる。

これで準備が整いました。ここからは関係式をいじって性質を探っていきます。

ここで、f(n) ≠ nであるnがとれるとする。(すなわちa_n > 1)
f^nf(n)(n)=nであるので、nf(n)はa_nで割り切れる。
a_nは1でないのでnとf(n)の少なくとも一方はa_nと互いに素でない。
そこでまずはnとa_nが1でない公約数dをもっている場合を考える。
n+f(n)+1もa_nで割り切れるのでdの倍数であるから、f(n)+1もdの倍数である。
したがってf(n)とdは互いに素であることがわかる。

また関係式f^n+f(n)+1(n)=nにおいてnをf^k(n)に置き換えると
f^{f^k(n)+f^k+1(n)+1}(f^k(n))=f^k(n)
が成り立つ。したがって
f^k(n)+f^k+1(n)+1もa_nの倍数であり
さらにkをk+1に置き換えたf^k+1(n)+f^k+2(n)+1もa_nの倍数なので
差をとって得られるf^k+2(n)-f^k(n)もa_nの倍数である。
これらを順次適用していくと
n,f²(n), … はdの倍数であり、f(n),f³(n), …はすべてdと互いに素である。
したがってf^a_n(n)=nでとくにdの倍数なのでa_nは偶数でなければならないことがいえる。

これで有用そうな偶奇に関係する性質が得られました。
残りも忘れずおさえましょう。

nとa_nが互いに素である場合、f(n)とa_nが1でない公約数をもつ。
上と同様な議論により
n,f²(n), … はすべてdと互いに素であり、f(n),f³(n), …はdの倍数であることがわかる。
したがってf^a_n(n)=nでとくにdと互いに素なのでa_nは偶数でなければならないことがいえる。

これでa_nが1か偶数であることがわかりましたので、あとはSからどんどん取り除いていくだけです。

Sにf(n) ≠ nとなる元nがない場合、Sは問題で求められている性質をみたしている。
Sにf(n) ≠ nとなる元nがある場合、Sの部分集合として{f(n),f²(n), … , f^a_n(n)}をとることができる。
この部分集合の全ての元mについて、f(m)がその部分集合の元になっていることがわかり、また作り方とfの性質からf(m)がその部分集合の元になるならばmもその部分集合の元であることがわかる。
したがってSからその部分集合を除いてできる集合S’に対して、引き続き同様の議論が可能である。
しかし各操作で取り除ける元の個数は偶数個でSの元は999個すなわち奇数なので、どのようにうまく除去できても最小で1個は残る。
残った元mはすなわちa_m=1をみたすものなのでf(m)=mをみたす。
すなわちSの元にはf(a)=aとなるaが必ず存在することが示される。□

ということで存在を示すことができました。かなり技巧的な方法を用いたと思います。