ご注文は数オリですか?

問題一覧へ戻る

#35
代数
★☆☆☆☆

正の整数に対して定義され, 正の整数値をとる関数 f が, 任意の正の整数 x に対し以下の条件をみたす.

  • 1f(x)x2019
  • f(f(x))x(mod2019)

このとき, ある正の整数 x が存在し, 任意の正の整数 k に対し fk(x)=x+2019k が成り立つことを示せ.

ただし fk(x)fk 回合成を表す.

平山:限りなくギャグっぽい
渡辺f(f(x))=x+2019 または x+4038
宿田:どこかで後者ならそれが満たすな
渡辺2019 が奇数なのが本質説があって
平山:常に f(f(x))=x+odd は無理ってやつ
平山:確か過去のIMOで見て、1987年とかかな
渡辺:数直線埋めるとどっかで矛盾する雰囲気が
平山:1987年であってた、記憶力オバケかもしれない
平石:なんで年代まで覚えてんねん
馬杉:なんか適当に mod 2019 でペアにすれば
平山f(x+2019)=f(f(f(x)))=f(x)+2019 だからOK
渡辺:いいんじゃない
平山:というか x<f(x) だからそれすら要らなかった…
馬杉:色々と終わってんじゃん

以下より各 x について f(f(x))=x+2019 または f(f(x))=x+4038 が必要である.2(f(f(x))f(x))+(f(x)x)4038ここである x0 について f(f(x0))=x0+4038 であったとすると, f(x0)=x0+2019 が必要であり, これより帰納的に任意の k について fk(x0)=x0+2019k であることが容易に従う. したがって以下, 任意の x についてf(f(x))=x+2019であると仮定し矛盾を導けばよい.

証明1. 工事中

証明2. 一般に c>0 を奇数とし, 任意の x に対し f(f(x))=x+c であるような f:Z+Z+ は存在しないことを示そう. 明らかに f(x)x で, f は単射である. いま仮定よりf(x+c)=f(f(f(x)))=f(x)+cであるから, fZ/cZZ/cZ とみなすことができる.

ここである x0c について f(x0)x0(modc) であったとき, k=(f(x0)x0)/c とおけばf2k(x0)=x0+kc=f(x0)となる. しかしこのとき, 単射性よりx0+(2k1)c=f4k2(x0)=f2k1(x0)=x0となり不適である. したがって Z/cZ の各元を頂点とし, xf(x) の間に辺を張ったグラフを考えると, 一連の議論によりこのグラフの各連結成分は長さ 2 のサイクルとなるが, これは c が奇数であることに反する.