IMO Shortlist 2010 A6について

こちら からのリンク.

きれいな問題だが，Shortlist の答えが難解だったので，勉強がてらに以下により簡単な解を記載する.
　
［略解］
$f,g$ の最小値をそれぞれ $m_f,\; m_g$ とする.

前半の目標は $m_f=m_g$ を示すことである.
まず $f$ の全射的な性質 (③) を述べ，単射的な性質 (④) を示す.

①より，$f$ は$m_f$以上のすべての整数をとる.　⋯ ③

①②より $f(x)=f(y) \Longleftrightarrow g(x)=g(y)$が容易に示され，これを用いて
　$f(f(x))=f(f(y)) \Longrightarrow g(f(x))=g(f(y)) \underset{②}\Longrightarrow g(x)=g(y)\Longrightarrow f(x)=f(y)$
であるから，③より $x,y \geq m_f$ のとき $f(x)=f(y)\Longrightarrow x=y$ が成立する.　⋯ ④

$g$ についても同様に考えて，
　$g$ は$m_g$以上のすべての整数をとる.
　$x,y \geq m_g$ のとき $g(x)=g(y)\Longrightarrow x=y$ が成立する.

$m_f=m_g$を示す.

$m_g \geq m_f$ のとき，$f$ について考えると
　②より$f(n) \neq n$ であるから，$f(m_f) \gt m_f$
　よって③より $f(m_f)=f(n)+1=f(g(n))$ なる $n \in \mathbb{N}$ が存在し，
　$g(n) \geq m_g \geq m_f$ より，④から $m_f=g(n)\geq m_g$ が得られ $m_f=m_g$ が成立する.
$m_g \leq m_f$ のときも $g$ について同様に考えて，$m_f=m_g$が成立する.　$\square$

①②より$f(k)=g(k)=k+1 \Longrightarrow f(k+1)=g(k+1)=k+2$ であるから，
後半は $f(m_f)=m_f+1$ ⋯⑤ を示すことを目指す.　これが成立するとき，
同様に $g(m_f)=m_f+1$，帰納的に $f(n)=g(n)=n+1 \quad\forall n \geq m_f$ が成立し，
①より $f(n)+1=f(g(n))=g(n)+1$ から，題意が示される.

⑤を示す.
$f(m_f) \geq m_f+2$ と仮定すると，$f(x)=f(m_f)-2 \;(\geq m_f)$ なる $x \in \mathbb{N}$ が存在し，
　$f(m_f)=f(x)+2=f(g(g(x)))$　$\therefore$ ④より $m_f=g(g(x))$
さらに，$f(y)=g(x)$ なる $y \in \mathbb{N}$ が存在し，
　$m_f=g(g(x))=g(f(y))=1+g(y) \geq 1+ m_f$
となり矛盾する.　よって $f(m_f) \gt m_f$ より $f(m_f)=m_f+1$　$\square$

　
根本的には③④の性質が強力なので解けるのかもしれない.
AOPSの解答も複数見たが，多くの解答が③，④，$m_f=m_g$ を順に示していた.
上記の解法は集合が前面に出てこない，シンプルなものであるが，
Shortlist と同様の集合を用いた解法も以下に記載する.
この方が本質的なのかもしれないが，記述量が増えがちである.
　
[Shortlist と同様に集合を用いた解法]

$\mathbb{N}^{\geq 0}$ を非負整数全体の集合，$\mathbb{N}^{\geq 2}$ を2以上の整数全体の集合とする.
$f^k(n)=\underbrace{f(f(\ldots f}_{k\text{ 個}}(n)\ldots))$ とし，とくに $f^0(n)=n$ とする.

まず題意が成立した場合，$f(f(n))=f(n)+1 \quad\forall n\in \mathbb{N}$ となるので，
この場合の $f:\mathbb{N} \to \mathbb{N}$ について考えてみる.
③より，$n \geq m_f$ のとき $f(n)=n+1$ となる.　よって，
　$ f(n)= \begin{eqnarray} \left\{ \begin{array}{l} c\;\text{以上の任意の整数} \quad (n \lt c) \\ n+1 \quad (n \geq c) \end{array} \right. \end{eqnarray} $　$\quad (c \in \mathbb{N}^{\geq 2})$
ただし，$n \lt c$ において $f(n)=c$ となる $n$ が少なくとも一つ存在する.
f(n)

元の問題に戻る.　③④は同様に示す.

以上から，ある整数 $t\geq m_f$ に対し，$f(n)=t$ をみたす $n$ は複数存在しうる.
そこで $f(n)=t$ をみたす $n \in \mathbb{N}$ 全体の集合 $F_t$ を考え, その性質を調べる.

$t \gt m_f$ のとき，
　③より，ある $x \in \mathbb{N}$ が存在し，$f(g(x))=f(x)+1=t$ となるので，
　$y \geq m_g$ をみたす $y \in F_t$ が存在する.　⋯ ⑥

逆に $F_t$ が $y \geq m_g$ なる $y$ を含むとき，$y=g(x)$ をみたす $x \in \mathbb{N}$ が存在し，
$f(y)=f(g(x))=f(x)+1 \gt m_f$ であるから，$t \gt m_f$ となる.
よって，$t = m_f \Longleftrightarrow F_t$ は $m_g$ 未満の正の整数しか含まない.　⋯ ⑦

$g$ についても同様に検討し，$F_{m_f}=G_{m_g}$ を示す.
これは後半部分で用いる.

同様に $g(n)=t$ をみたす $n$ の集合 $G_t$ を考える.
上記と同様に，以下が成立する.
　$t = m_g \Longleftrightarrow G_t$ は $m_f$ 未満の正の整数しか含まない.

また$f(x)=f(y) \Longleftrightarrow g(x)=g(y)$ より，
ある $F_t$ と $G_s$ は等しいか互いに素であるかのいずれかである.
どの $F_t$ にも，それと等しい $G_s$ がただ一つ存在する (逆も成立する).

さて $m_g \geq m_f$ のとき，$G_{m_g}$は$m_g$未満の正の整数しか含まない.
$G_{m_g}$と等しい $F_t$ が存在するが，⑦よりそれは $F_{m_f}$ である.
$m_f \geq m_g$ のときも同様に，$F_{m_f}=G_{m_g}$ が成り立つ.　$\square$

$m_f=m_g$ を示す.

$m_g \geq m_f$ のとき，
　②より$f(n) \neq n$ であるから，$f(m_f) \gt m_f$ より $F_{m_f} \neq F_{f(m_f)}$ である.
　⑥より，$F_{f(m_f)}$ は $x \geq m_g \;(\geq m_f)$ をみたす $x$ を含む.
　$f(x)=f(m_f)$ かつ $x \geq m_f$ より，④から $x=m_f$ である.
　よって $m_f \geq m_g$ が成り立ち，$m_f=m_g$ である.
$m_g \leq m_f$ のときも $g$ について同様に考えて，$m_f=m_g$が成立する.　$\square$

ここから後半部.
$f(n_f)=m_f$ をみたす $n_f \in \mathbb{N}$ に対し，$g(n_f)=m_f$ を示す.

$F_{m_f}=G_{m_g}$ より，$f(n_f)=m_f \Longleftrightarrow g(n_f)=m_g=m_f$ である.　$\square$

すると①②より帰納的に，以下が成り立つ.　
　$f(g^{k}(n_f))=f(g^{k-1}(n_f))+1=⋯=m_f+k \quad\forall k \in \mathbb{N}^{\geq 0}$
　$g(f^{k}(n_f))=g(f^{k-1}(n_f))+1=⋯=m_f+k \quad\forall k \in \mathbb{N}^{\geq 0}$
次に，$f^{k+1}(n_f)=g^{k+1}(n_f)=m_f+k \quad\forall k \in \mathbb{N}^{\geq 0}$ ⋯ ⑧ を帰納法で示す.

$k=0$ で⑥は成立する.　ある $k=l \in \mathbb{N}^{\geq 0}$ で⑥が成り立つとき，
$f^{l+2}(n_f)=f(f^{l+1}(n_f))=f(g^{l+1}(n_f))=m_f+l+1$
同様に $g^{l+2}(n_f)=m_f+l+1$ も成立する.　$\square$

これらを用いて題意を示す.

任意の $n \in \mathbb{N}$ に対し，$f(n)=m_f+k=f(g^{k}(n_f))$ なる $k \in \mathbb{N}^{\geq 0}$ が存在し，
$f(x)=f(y) \Longleftrightarrow g(x)=g(y)$ より，$g(n)=g(g^{k}(n_f))=g^{k+1}(n_f)$
⑧より $g(n)=g^{k+1}(n_f)=m_f+k=f(n)$　$\square$

　
結局のところ，この解法では$F_{m_f}=G_{m_g}$ を示すことで後半の議論の起点としているが，これをきちんと示すのは意外と結構大変である.
最初の解答は $f(m_f)=m_f+1$ を示すことで，これをうまく回避しているとも考えられる.