JMO2025を解いてみた

133

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

　解いてみました．問７あたりからあまり自信ないです．それ以前も含めて，間違っていたら指摘してもらえれば訂正します（たぶん）．問11は解いたら爆発しそうです．
　著作権の関係で怒られたりしたら記事は削除します．

問１

　 $7$ の位置を固定する（当然だが中央ではない）．それに隣り合う $3$ 箇所が $1, 2, 3$ のいずれかになる．
　 $7$ の"反対側"に $5, 6$ のいずれかが入ると， $5 + 6 = 11$ ができて矛盾するので， $7$ の"反対側"は $4$ ．
　以上を満たしさえすれば，条件を満たす．
　よって， $7$ の位置が $6$ 通り， $5, 6$ の決め方が $2$ 通り， $1, 2, 3$ の決め方が $3!$ 通り．かけ合わせて $72$ 通り．

問２

　 $2025 = 3^{4} \times 5^{2}$ である．
　 $a = 3^{a_{1}} \times 5^{a_{2}}, b = 3^{b_{1}} \times 5^{b_{2}}, c = 3^{c_{1}} \times 5^{c_{2}}, d = 3^{d_{1}} \times 5^{d_{2}}$ とおくと，

$a_{1} + b_{1} + c_{1} + d_{1} = 4, a_{2} + b_{2} + c_{2} + d_{2} = 2$
$a_{1}, b_{1}, c_{1}, d_{1}$ は全て偶数か，全て奇数
$a_{2}, b_{2}, c_{2}, d_{2}$ は全て偶数か，全て奇数

　 $(a_{1}, b_{1}, c_{1}, d_{1})$ の組み合わせは $11$ 通り， $(a_{2}, b_{2}, c_{2}, d_{2})$ の組み合わせは $4$ 通りなので， $11 \times 4 = 44$ 通り．

問３

　 $P_{8}, P_{7}, P_{5}, P_{4}, P_{2}, P_{1}$ の順に， $4, 2, 4, 2, 4, 2$ 通りの置き方がある．
　 $(4 \times 2)^{3} = 512$ 通り．

問４

　 $2, 3, 4, 5, 6$ の最小公倍数である $60$ を法にして考えたい問題だ．
　 $6$ で割った余りが $0 \sim 5$ のときにどうなるかを考えていこう．

$6$ で割った余りが $0$ → $2$ で割った余りを考えると矛盾
$6$ で割った余りが $1$ → $2$ で割った余りを考えると矛盾
$6$ で割った余りが $2$ → $3$ で割った余りを考えると矛盾
$6$ で割った余りが $3$ → $2$ で割った余りが $1$ であり， $4$ で割った余りが $1$ or $3$ になるため矛盾
$6$ で割った余りが $4, 5$ はもう少しきちんと議論する．

(i) $6$ で割った余りが $4$
　 $2$ で割った余りが $0$ ， $3$ で割った余りが $1$ がまず確定し，これによって， $4$ で割った余りが $2$ でなければならず， $5$ で割った余りが $3$ でなければならない．
　 $60 n + 58$ 型の数であれば，これらをすべて満たす．
(ii) $6$ で割った余りが $5$
　 $2$ で割った余りが $1$ ， $3$ で割った余りが $2$ がまず確定し，これによって， $4$ で割った余りが $3$ でなければならない． $5$ で割った余りは $0, 4$ のいずれかならよい．
　 $60 n + 35, 60 n + 59$ 型の数であれば，これらをすべて満たす．

　 $1000 = 60 \times 16 + 60$ なので， $960 (= 60 \times 16)$ までに条件を満たす数が $16 \times 3 = 48$ 個存在し，あと $995$ が条件に当てはまるので，全てで $49$ 個である．

問５

　 $△ Q D C \sim △ Q B A, △ P B C \sim △ P D A$ である．
　相似比は内接円の半径の比に一致するので， $B C = 5 x, A D = 6 x$ ， $C D = y, A B = 2 y$ と置ける．
　さらに，四角形 $A B C D$ は内接円を持つので $A B + C D = B C + D A$ である．
　よって $11 x = 3 y$ であり，求めたい比は
$\frac{B C}{C D} = \frac{5 x}{y} = \frac{15}{11}$

問６

　任意の $n$ に対して $a_{n}, b_{n}$ の少なくとも一方が常に偶数であることが必要条件である．
（特に，一方が奇数で他方が偶数であれば条件を満たすことは，わかりやすいだろう．）

　以下，正整数 $x$ が $2$ で割り切れる回数を $v_{2} (x)$ で表す．（例えば $v_{2} (2025) = 0, v_{2} (10) = 1, v_{2} (6^{5}) = 5$ である．）
　条件を満たす必要十分条件を考えるために，いくつかの例を考えてみよう．

(i) $v_{2} (a_{n}) = v_{2} (b_{n}) = k > 0$ の場合
（わかりづらければ， $a_{n}, b_{n}$ がともに $4$ の奇数倍である場合を考えてみよ）
　このとき， $v_{2} (a_{n + 1}) = v_{2} (b_{n + 1}) = k - 1$ となる．よって何度か繰り返すと $v_{2} (a_{N}) = v_{2} (b_{N}) = 0$ となり，どこかで整数でなくなるため矛盾．

(ii) $v_{2} (a_{n}) = k + 1, v_{2} (b_{n}) = k$ の場合
（わかりづらければ， $a_{n}$ が $4$ の奇数倍， $b_{n}$ が $2$ の奇数倍の場合を考えてみよ）
　このとき， $v_{2} (a_{n + 1}) = k, v_{2} (b_{n + 1}) \geq k + 1$ とすることができる．

(iii) $v_{2} (a_{n}) \geq k + 2, v_{2} (b_{n}) = k$ の場合
（わかりづらければ， $a_{n}$ が $8$ の奇数倍， $b_{n}$ が $2$ の奇数倍の場合を考えてみよ）
　このとき， $v_{2} (a_{n + 1}) = v_{2} (a_{n}) - 1, v_{2} (b_{n + 1}) = k$ とすることができる．

　以上の議論から， $v_{2} (a_{1}) \neq v_{2} (b_{1})$ であれば条件を満たす．

一方が $v_{2} (*_{1}) = 0$ を満たす場合… $2 \times 20 \times 20 = 800$ 通り．
一方が $v_{2} (*_{1}) = 1$ ，他方が $v_{2} (*_{1}) \geq 2$ を満たす場合… $2 \times 10 \times 10 = 200$ 通り．
一方が $v_{2} (*_{1}) = 2$ ，他方が $v_{2} (*_{1}) \geq 3$ を満たす場合… $2 \times 5 \times 5 = 50$ 通り．
一方が $v_{2} (*_{1}) = 3$ （こちらが $8, 24, 40$ ），他方が $v_{2} (*_{1}) \geq 4$ （ $16, 32$ ）を満たす場合… $2 \times 3 \times 2 = 12$ 通り．
一方が $v_{2} (*_{1}) = 4$ （つまり $16$ ），他方が $v_{2} (*_{1}) \geq 5$ （ $32$ ）を満たす場合… $2 \times 1 \times 1 = 2$ 通り．

　以上を足し合わせて， $1064$ 通りである．

問７

　 $1$ ターンで，ある $1$ 行を全て使うことができるので，最短は $20$ ターンである．それより少ないターンでゲームを終了できないことの証明は任せる．
　これから考えなければならないことは， $20$ ターンにわたる ${A_{n}}$ の選び方が何通り存在するか，である．
　まず毎ターン，いずれかの行を使い切らなければならない．ここで，一番上の行を使い切るような ${A_{n}}$ の選び方を考えよう．考えて見ると，以下のことがわかる．

${A_{n}}$ は左上隅のマスを含まなければならない．
${A_{n}}$ は左端の列のうち，上から連続したいくつかを選ぶことができる．

　ここで， ${A_{n}}$ が左端の列のうち，上から連続した $k (\geq 1)$ 個を選んだとしよう．
　 $k = 1, 30$ の場合は，単純に「 $20$ 行あったものが $19$ 行に減る」と考えればよい．
　問題は $k$ がそれ以外の場合である．このとき，上から $2$ 列目の行を使い切る ${A_{n}^{(2)}}$ の選び方を考えてみよう． ${A_{n}^{(2)}}$ は左から $2$ 列目のマス目を最大で $k - 1$ 個までしか選べないことがわかるだろう．これより多く選んでしまうと， $20$ ターンで終わらせることが不可能だからである（図を描いてみよ）．
　つまり最初の ${A_{n}}$ によって， $20 \times 25$ のマス目は， $(k - 1) \times 24$ のマス目と $(20 - k) \times 25$ のマス目に分割されたと考えられる．

　ここで一般に，縦 $i$ マス，横 $j (> i)$ マスのマス目を，条件を満たすような ${A_{n}}$ で区分けする場合の数を $C_{i}$ としよう．条件 $j (> i)$ から，この場合の数は $j$ によらないことに注意せよ．
　先ほどの議論から，

$C_{i + 1} = C_{i} + C_{i - 1} C_{1} + C_{i - 2} C_{2} + \dots C_{1} C_{i - 1} + C_{i}$

となることがわかる． $C_{1} = 1$ より，これがカタラン数であることを知っていれば，

$C_{n} = \frac{(2 n)!}{(n + 1)! n!}$

だとわかる．もしカタラン数を知らなければ， $C_{n}$ を小さい順に求めて推測することも可能である（後述）．
　いま求めたいものは， $C_{20}$ の $20!$ 倍である（ $C_{n}$ は区分けの仕方であり，それらに順に $1 \sim 20$ を割り振らなければならなかった）．
　よって解答は $\frac{40!}{21!}$

カタラン数の一般項の推測

C_{n}

を順に求めていくと，

1, 2, 5, 14, 42, 132, 429

となる．
　最初の方の階差数列を取ると，

1, 3, 9, 28, 90

となって

3^{n}

が関係しているように見えなくもないが，次の階差が

297

であることを見て，この方針は撤退すべきである．
　一応階差の階差も取ってみよう．

2, 6, 19, 62, 207

で意味不明である．往生際悪く，もう一度だけ階差を取ってみよう．

4, 13, 43, 145

…これはやめた方が良い．

　次なる選択肢は

\frac{C_{n + 1}}{C_{n}}

を観察することである．
　最初から順に，

\frac{2}{1}, \frac{5}{2}, \frac{14}{5}, \frac{3}{1}, \frac{22}{7}, \frac{13}{4}

である．
　ここで，分母に

5

と

7

があることに注目すれば，次のように変形することが思い浮かぶだろう．

\frac{6}{3}, \frac{10}{4}, \frac{14}{5}, \frac{18}{6}, \frac{22}{7}, \frac{26}{8}

　これより，

\begin{aligned} C_{n} & = \frac{2 \cdot 6 \cdot 10 \cdot 14 \dots (4 n - 2)}{2 \cdot 3 \cdot 4 \dots (n + 1)} \\ = \frac{2^{n} \cdot 1 \cdot 3 \cdot 5 \cdot 7 \dots (2 n - 1)}{(n + 1)!} \\ = \frac{2^{n} \cdot (2 n)!}{(n + 1)! \cdot 2 \cdot 4 \cdot 6 \dots 2 n} \\ = \frac{2^{n} \cdot (2 n)!}{(n + 1)! \cdot 2^{n} \cdot n!} \\ = \frac{(2 n)!}{(n + 1)! n!} \end{aligned}

問８

　問題文の $3$ 個目の条件がわかりづらい． $j$ を固定すると， $\frac{a_{i} + a_{k}}{2}$ の中で最大のものは $\frac{a_{j - 1} + a_{n}}{2}$ である．少し実験してみると，

$a_{2} \geq \frac{a_{n}}{2}, a_{3} \geq \frac{a_{2} + a_{n}}{2} \geq \frac{3 a_{n}}{4}, a_{4} \geq \frac{a_{3} + a_{n}}{2} \geq \frac{7 a_{n}}{8}$

である．どうも $2$ べきが関係しているようだ．
　もう少し実験を続けよう．例えば

$0, 1, 2$
$0, 2, 3, 4$
$0, 4, 6, 7, 8$
$0, 8, 12, 14, 15, 16$
$0, 16, 24, 28, 30, 31, 32$

などは美しい列である．では， $a_{2} = 5$ だとどうなるだろうか． $a_{2} \geq \frac{a_{n}}{2}$ を思い出して， $a_{n} = 10$ としたくなる（例えば次の数列）
$0, 5, 7, 9, 10$
　しかし，
$0, 5, 7, 8, 9$
でも条件を満たしていることに気付いてほしい．
　このあたりで，次の予想が立つ．

$2^{k} \leq a_{2} < 2^{k + 1}$ であれば，美しい列の長さの最大値は $k + 3$ である．
美しい列の作り方として，
$a_{n - i} = a_{n} - 2^{i - 1}$
とする方法がある．

　この予想に従って問題を解いてみよう．
　 $2^{10} < 2025 < 2^{11}$ より，美しい列の長さの最大値は $13$ である．そして美しい列の具体例として，

$0, 2025, 2025 + 512, 2025 + 512 + 256, \dots, 2025 + 1024$

を思いつくが，果たしてこれでよいか．必ずしも $a_{2} = 2025$ である必要はない．そのことに気付けば，次のような改案が得られる：

$0, 2057 - 1024, \dots, 2057 - 32, \dots, 2057 - 2, 2057 - 1, 2057$

（この例を考えるには， $2025 + 2^{c} > 2048$ を満たすような $c$ が存在しないかと考えればよい．）
　一応これが最小であることを確かめておこう． $2$ べきを使った典型的な美しい例をして，次の数列がある：
$0, 1024, 1536, 1792, 1920, 1984, 2016, 2032, 2040, 2044, 2046, 2047, 2048$
$2025$ を含む数列にするためには， $2016$ に $9$ を加えるのが最も近道であり， $a_{7} + 32 \leq a_{N}$ より $a_{N} \geq 2057$ である．

　予想が正しいことは，（自分でも証明していないのだが）疲れてきたので割愛する．

問９

　 $A G$ が円 $A B C$ の直径となるように点 $G$ を取り， $A D$ と円 $A B C$ の交点を $H (\neq A)$ とする．
　 $∠ B A D = ∠ C A G = 90 ° - ∠ B$ であり， $∠ A F E = ∠ A D E = ∠ B$ である．このことから，

$△ A B C \sim △ A F E$
$A O ⊥ E F$

がわかる．さらに，
$∠ E A D = ∠ C A G, ∠ D A O = ∠ G A H, ∠ O A F = ∠ H A B$
より，五角形 $A E D O F$ と五角形 $A C G H B$ の相似もわかる．この相似において点 $P$ と点 $D$ も対応していることから，相似比を $1 : t$ と置くと， $A D = 11 t, A G = 11 t^{2}$ だとわかり， $A O = \frac{11 t^{2}}{2}$ である．
　 $△ A D O$ に三平方の定理を適用して， $t = \frac{2 \sqrt{77}}{11}$ を得る．これより， $A D = 2 \sqrt{77}, A O = 14$ である．

　ここからは $E F$ の長さを求めにいこう． $A D$ の中点（つまりは円の中心）を $Q$ ， $E F$ の中点を $M$ ， $A O$ の中点を $N$ とおく．
　 $Q M = N P = 4$ であり， $Q E = \sqrt{77}$ なので， $E M = \sqrt{61}$ ．よって $E F = 2 \sqrt{61}$ である．

問１０

　以下，合同式はすべて $9$ を法として考えている．
　まず $(0, 0, 0)$ を代入してみたくなる．

$9 | f (0) f (0) - f (f (0))$

　これでは，どうもそんなに役立ちそうにない（ここから続けるなら $f (0) = a$ とおいたとき $a^{2} \equiv f (a)$ がわかるが，その後が続かない…よね？）．

　そこで， $(0, a, a)$ を代入してみよう．これも自然な代入である．

$9 | f (0) f (a) - f (f (a)) ⟺ f (0) f (a) \equiv f (f (a)) \dots (1)$

　一見役立ちそうにない式だが，もしある $a \in S$ が $f (a) = 0$ を満たすならば $0 \equiv f (0)$ ．すなわち $f (0) = 0$ であることがわかる（これは $a = 0$ を意味しているわけではないことに注意せよ）．
　以下， $f (0) = 0$ の場合を考えよう．式 $(1)$ より任意の $a \in S$ に対して $f (f (a)) = 0$ である．
　このあたりで，役立つ別の式がほしい．そこで， $(x, y, z = a, a, 2 a)$ を代入した式を考えてみよう．なお， $a = 5$ のときは $2 a = 10 \equiv 1$ と考える等，臨機応変に $9$ を法として読んでほしい．

$f (a)^{2} \equiv f (f (2 a)) \dots (2)$

　この式は一見使いづらいが，任意の $2 a \in S$ に対して $a \in S$ が $1 : 1$ 対応で存在するので， $f (f (a)) = 0$ と非常に相性がいい．つまり，任意の $a \in S$ に対して $f (a)^{2} \equiv 0$ という結論を得る．もう少しわかりやすい形にすれば， $f (a)$ は $0, 3, 6$ のいずれかである．
　ここまでの結果をまとめると， $f (x) f (y)$ も $f (f (z))$ も常に $0$ と合同なので，問題文の条件は十分満たしている．
　以下， $f (3), f (6)$ の値によって場合分けを考えよう．

$f (3) = f (6) = 0$ の場合
　 $1, 2, 4, 5, 7, 8$ の行き先は $0, 3, 6$ のいずれもよい．よって $6^{3} = 216$ 通り．
$f (3) = 6, f (6) = 0$ の場合
　 $1, 2, 4, 5, 7, 8$ の行き先は $0, 6$ のいずれかである．よって $6^{2} = 36$ 通り．
$f (6) = 3, f (3) = 0$ の場合
　上と同様． $36$ 通り．
これ以外の場合は $f (f (a)) ≢ 0$ となる $a = 3$ or $6$ が存在するので不適．

　ここまでで， $f (a) = 0$ を満たす $a \in S$ が存在する場合は終わった．次に， $f (a) \neq 0$ for any $a \in S$ の場合である．
　まず式 $(2)$ より，任意の $a$ に対して $f (f (a)) = 1, 4, 7$ である（式 $(2)$ の $2 a$ を改めて $a$ と置き直している）．特にある $b \in S$ が存在して $f (b) = 1, 4, 7$ だ．ここで $(x, y, z) = (x, b, x + b)$ を考えると $f (x) f (b) \equiv f (f (x + b))$ となる．両辺の $3$ で割った余りを考えることで，任意の $x \in S$ に対して $f (x) = 1, 4, 7$ を得る．
　さあゴールは近そうだ．あとは $f (0)$ の値で場合分けしてみよう．

$f (0) = 1$ の場合
　式 $(1)$ より $f (a) = f (f (a))$ であり，特に $a = 0$ を代入することで $f (1) = 1$ を得る．
　次に $(x, y, z) = (a, 1, a + 1)$ を考えると， $f (a) = f (f (a + 1)) = f (a + 1)$ となるので，結局 $f \equiv 1$ である．
$f (0) = 4$ の場合
　式 $(1)$ を使って， $f (4) = 7, f (7) = 1, f (1) = 4$ がわかる．
　式 $(2)$ に $a = 2$ を代入して $f (2) = 1$ がわかり，式 $(2)$ に $a = 1$ を代入して矛盾を得る．
$f (0) = 7$ の場合
　式 $(1)$ を使って， $f (7) = 4, f (4) = 1, f (1) = 7$ がわかる．
　式 $(2)$ に $a = 2$ を代入して $f (2) = 4$ がわかり，式 $(2)$ に $a = 1$ を代入して矛盾を得る．