JMO2025を解いてみた

　解いてみました．問７あたりからあまり自信ないです．それ以前も含めて，間違っていたら指摘してもらえれば訂正します（たぶん）．問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×5^2$である．
　$a=3^{a_1}×5^{a_2},b=3^{b_1}×5^{b_2},c=3^{c_1}×5^{c_2},d=3^{d_1}×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×4=44$通り．

問３

　$P_8, P_7,P_5,P_4,P_2,P_1$の順に，$4,2,4,2,4,2$通りの置き方がある．
　$(4×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$でなければならない．
　$60n+58$型の数であれば，これらをすべて満たす．
(ii)$6$で割った余りが$5$
　$2$で割った余りが$1$，$3$で割った余りが$2$がまず確定し，これによって，$4$で割った余りが$3$でなければならない．$5$で割った余りは$0,4$のいずれかならよい．
　$60n+35,60n+59$型の数であれば，これらをすべて満たす．

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

問５

　$\triangle QDC \sim \triangle QBA, \triangle PBC \sim \triangle PDA$である．
　相似比は内接円の半径の比に一致するので，$BC=5x,AD=6x$，$CD=y,AB=2y$と置ける．
　さらに，四角形$ABCD$は内接円を持つので$AB+CD=BC+DA$である．
　よって$11x=3y$であり，求めたい比は
$$\dfrac{BC}{CD}=\dfrac{5x}{y}=\dfrac{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) \ne v_2(b_1)$であれば条件を満たす．

• 一方が$v_2(*_1)=0$を満たす場合…$2×20×20=800$通り．
• 一方が$v_2(*_1)=1$，他方が$v_2(*_1) \geq 2$を満たす場合…$2×10×10=200$通り．
• 一方が$v_2(*_1)=2$，他方が$v_2(*_1) \geq 3$を満たす場合…$2×5×5=50$通り．
• 一方が$v_2(*_1)=3$（こちらが$8,24,40$），他方が$v_2(*_1) \geq 4$（$16,32$）を満たす場合…$2×3×2=12$通り．
• 一方が$v_2(*_1)=4$（つまり$16$），他方が$v_2(*_1) \geq 5$（$32$）を満たす場合…$2×1×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×25$のマス目は，$(k-1)×24$のマス目と$(20-k)×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+\cdots C_1C_{i-1}+C_i$$

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

$$C_n=\dfrac{(2n)!}{(n+1)!n!}$$

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

問８

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

$$a_2 \geq \dfrac{a_n}{2}, a_3 \geq \dfrac{a_2+a_n}{2} \geq \dfrac{3a_n}{4}, a_4 \geq \dfrac{a_3+a_n}{2} \geq \dfrac{7a_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 \dfrac{a_n}{2}$を思い出して，$a_n=10$としたくなる（例えば次の数列）
$0,5,7,9,10$
　しかし，
$0,5,7,8,9$
でも条件を満たしていることに気付いてほしい．
　このあたりで，次の予想が立つ．

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

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

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

$$ 0,2057-1024,\cdots,2057-32,\cdots,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$ である．

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

問９

　$AG$が円$ABC$の直径となるように点$G$を取り，$AD$と円$ABC$の交点を$H(\ne A)$とする．
　$\angle BAD= \angle CAG = 90°-\angle B$であり，$\angle AFE=\angle ADE =\angle B$である．このことから，

• $\triangle ABC \sim \triangle AFE$
• $AO \perp EF$

がわかる．さらに，
$$\angle EAD=\angle CAG, \angle DAO=\angle GAH, \angle OAF=\angle HAB$$
より，五角形$AEDOF$と五角形$ACGHB$の相似もわかる．この相似において点$P$と点$D$も対応していることから，相似比を$1:t$と置くと，$AD=11t, AG=11t^2$だとわかり，$AO=\dfrac{11t^2}{2}$である．
　$\triangle ADO$ に三平方の定理を適用して，$t=\dfrac{2\sqrt{77}}{11}$を得る．これより，$AD=2\sqrt{77}, AO=14$である．

　ここからは$EF$の長さを求めにいこう．$AD$の中点（つまりは円の中心）を$Q$，$EF$の中点を$M$，$AO$の中点を$N$とおく．
　$QM=NP=4$であり，$QE=\sqrt{77}$なので，$EM=\sqrt{61}$．よって$EF=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)) \iff f(0)f(a) \equiv f(f(a)) \cdots (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,2a)$を代入した式を考えてみよう．なお，$a=5$のときは$2a=10 \equiv 1$と考える等，臨機応変に$9$を法として読んでほしい．

$$f(a)^2 \equiv f(f(2a)) \cdots (2)$$

　この式は一見使いづらいが，任意の$2a \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)) \not\equiv 0$となる$a=3$or$6$が存在するので不適．

　ここまでで，$f(a)=0$を満たす$a \in S$が存在する場合は終わった．次に，$f(a) \ne 0$ for any $a \in S$の場合である．
　まず式$(2)$より，任意の$a$に対して$f(f(a)) = 1,4,7$である（式$(2)$の$2a$を改めて$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$を代入して矛盾を得る．

　以上から，条件を満たす$f$の個数は$216+36×2+1=289$通り．