JMO2025予選 第10問 証明

2025年に行われた日本数学オリンピック予選の第10問の証明を書いてみました．

問題

公式サイトより抜粋

証明

\(S\)上に定義され\(S\)に値をとる関数\(f\)に対し，任意の\(S\)の要素\(x,y,z\)に対して，\(x+y-z\)が9の倍数ならば\(f(x)f(y)-f(f(z))\)も\(9\)の倍数であるという条件を\((*)\)とおく．

条件\((*)\)を満たす関数を\(F\)とおく．

\(F(0) \in S\)の値によって場合分けする．

\(F(0)=0\)と仮定したとき

条件\((*)\)より，

$$F(z)F(0)-F(F(z)) \equiv 0 \pmod 9 \quad (\forall z \in S) \tag{1}$$

\(F(0)=0\)より，

$$F(F(z)) \equiv 0 \pmod 9 \quad (\forall z \in S) \tag{2}$$

すなわち

$$F(F(z))=0 \quad (\forall z \in S) \tag{3}$$

任意の\(x,y\in S\)について\(x+y-z\)が9の倍数となるような\(z \in S\)は存在するから，条件\((*)\)は，関数\(f\)に対し以下の2式が共に成り立つことと同値である．

$$\begin{align}
f(f(z)) \equiv 0 \pmod 9 &\quad& (\forall z \in S) \tag{4}\\
f(x)f(y) \equiv 0 \pmod 9 &\quad& (\forall x,y \in S) \tag{5}
\end{align}$$

が成り立つ．(5)式からただちに，

$$ \{F(x)\}^2 \equiv 0 \pmod 9 \quad (\forall x \in S) \tag{6}$$

すなわち，

$$ F(x)=0,3,6 \quad (\forall x \in S) \tag{7}$$

がわかる．また，(7)式が成り立つならば，任意の\(x \in S\)について\(F(x)\)は3の倍数であるから，その積は9の倍数である．ゆえに(5)式が成り立つ．したがって(5)式と(7)式は同値である．

つまり，(*)は(4)式と(7)式が共に成り立つことと同値である．

ここで，\(T=\{F(x) \; | \; x \in S\}\)とおく．

(i) \(T=\{0\}\)のとき

関数\(F\)としてありうるのは\(1\)通り

(ii) \(T=\{0,3\}\)のとき

ある\(x \in S\)について\(F(x)=3\)であるから，(4)式より\(F(3)=0\)

残る要素\(x \in S \setminus \{0,3\}\)について，\(F(x)=0,3\)すべての関数値が0である場合を除いて\(2^7-1=127\)（通り）

(iii) \(T=\{0,6\}\)のとき

ある\(x \in S\)について\(F(x)=6\)であるから，(4)式より\(F(6)=0\)

残る要素\(x \in S \setminus \{0,6\}\)について，\(F(x)=0,6\)すべての関数値が0である場合を除いて\(2^7-1=127\)（通り）

(iv) \(T=\{0,3,6\}\)のとき

上と同様の議論により\(F(3)=F(6)=0\)である．\(T=\{0\},\{0,3\},\{0,6\}\)の場合を除いて，\(3^6-(2^6-1)-(2^6-1)-1=602\)（通り）

(i), (ii), (iii), (iv)より，\(F(0)=0\)なる関数\(F\)は\(1+127+127+602=857\)（通り）

\(F(0)=3,6\)と仮定したとき

\(F(0)=3k \quad (k=1,2)\)とおく．

条件\((*)\)より，

$$\begin{align}
F(0)F(0) – F(F(0)) &\equiv& 0 \pmod 9 \tag{8} \\
F(3k) &\equiv& 9k^2 \pmod 9 \tag{9}\\
F(3k) &\equiv& 0 \pmod 9 \tag{10}
\end{align}$$

ゆえに，

$$ F(3k)=0 \tag{11}$$

しかし，条件\((*)\)より

$$\begin{align}
F(0)F(3k)-F(F(3k)) \equiv 0 \pmod 9 \tag{12} \\
F(0) \equiv 0 \pmod 9 \tag{13}
\end{align}$$

(13)式は\(F(0)=3\)の仮定に矛盾する．ゆえに\(F(0)=3\)なる関数\(F\)は存在しない．

\(F(0)=1,2,4,5,7,8\)と仮定したとき

関数\(f\)に対して，

$$f^n(x) = \underbrace{f(f(\dots f(x) \dots))}_{n \text{ 回}}$$

と書くものとする．条件\((*)\)より，

$$\begin{align}
F(0)F(F^n(0))-F(F^n(0)) &\equiv& 0 \pmod 9 \tag{14} \\
F^{n+1}(0) &\equiv& F(0)F^n(0) \pmod 9 \tag{15}
\end{align}$$

それゆえ，

$$F^n(0) \equiv \{F(0)\}^n \tag{16}$$

ここで，仮定より\(F(0)\)は9と互いに素であるから，オイラーの定理より，ある自然数\(l\)が存在して，

$$\{F(0)\}^l \equiv 1 \pmod 9 \tag{17}$$

(16)式を適用し，

$$F^l(0) \equiv 1 \pmod 9 \tag{18}$$

両辺に関数\(F\)を適用し，

$$F^{l+1}(0) \equiv F(1) \pmod 9 \tag{19}$$

(15)式および(17)式より，

$$F(0) \equiv F(1) \pmod 9 \tag{20}$$

すなわち

$$F(1) = F(0) \tag{21}$$

ここで，任意の\(x \in S\)について\(F(x)=F(0)\)であることを示す．

\(n \in S \setminus \{8\}\)について，条件\((*)\)より，

$$\begin{cases}
F(n+1)F(0)-F(F(n+1)) \equiv 0 \pmod 9 \\
F(n)F(1)-F(F(n+1)) \equiv 0 \pmod 9
\end{cases}\tag{21}$$

が成り立つ．辺々差し引いて整理し，

$$F(n+1)F(0) \equiv F(n)F(1) \pmod 9 \tag{22}$$

(21)式より，

$$F(n+1)F(0) \equiv F(n)F(0) \pmod 9 \tag{23}$$

\(F(0)\)は9と互いに素なので，逆元が存在して

$$F(n+1) \equiv F(n) \pmod 9 \tag{24}$$

明らかに，

$$F(n+1) = F(n) \tag{25}$$

したがって，

$$F(0)=F(1)=F(2)=\dots=F(8)$$

よって，関数\(F\)は以下の式を満たす．

$$\{F(0)\}^2-F(0) \equiv 0 \pmod 9 \tag{26}$$

これを満たすのは，\(F(0)=1\)の場合のみ．

結論

以上，\(F(0)\)の値による場合分けから，\(857+1=858\)（通り）.

(16)式に気づくことが肝だと思います．