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

今回の記事はこちらの問題、本選の第3問です。

S={1,2, … , 999}とおく。fはS上で定義されSに値をとる関数であり、任意のSの要素nに対して

fn+f(n)+1(n)=fnf(n)(n)=n

が成り立つとする。このとき、f(a)=aをみたすSの要素aが存在することを示せ。
ただし、fk(n)でf(f(…f(n)…)) (fがk回登場する)を表すものとする。

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

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

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

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

このときf0(n)=nと考えてf0(n), … , fan-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(n) = f0(n)であるのでさらに操作をk回施すと
fan+k(n) = fk(n)となることから
すべての整数kについてan=afk(n)がいえる。

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

ここで、f(n) ≠ nであるnがとれるとする。(すなわちan > 1)
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とanが互いに素である場合、f(n)とanが1でない公約数をもつ。
上と同様な議論により
n,f2(n), … はすべてdと互いに素であり、f(n),f3(n), …はdの倍数であることがわかる。
したがってfan(n)=nでとくにdと互いに素なのでanは偶数でなければならないことがいえる。

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

Sにf(n) ≠ nとなる元nがない場合、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が必ず存在することが示される。□

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

スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク