除夜の鐘コンテスト2024 問題・解説

はじめに

　2024年12月31日にX( @1231_math )にて開催された除夜の鐘コンテスト2024の予選，敗者復活戦，決勝の問題・解説です．たくさんの方のご参加ありがとうございました！
　なお，予選A4については問題にミスが発覚致しました．改めてお詫び申し上げます．

予選

代数

解説

　並べ替え不等式より，$S$が最大となるのは
$$(a_1,a_2,\ldots,a_{23})=(b_1,b_2,\ldots,b_{23})=(1,2,\ldots,23)$$
のときであり，$S$が最小となるのは
$$(a_1,a_2,\ldots,a_{23})=(b_{23},b_{22},\ldots,b_{1})=(1,2,\ldots,23)$$
のときなので，求める値は，
$$M-m=\displaystyle\sum_{k=1}^{23}k^2-\displaystyle\sum_{k=1}^{23}k(24-k)=\displaystyle\sum_{k=1}^{23}(2k^2-24k)=\mathbf{2024}$$
である．

解説

　$3$倍角の公式を変形することで，
$$\sin{3\theta}=-4\sin{\theta}\sin{(\theta-60°)}\sin{(\theta+60°)}$$
を得る．これより，
$$\prod_{k=1}^{9}\sin{(10k-5)°} =(\sin{5°}\sin{55°}\sin{65°})(\sin{15°}\sin{45°}\sin{75°})(\sin{25°}\sin{35°}\sin{85°})=\frac{\sin{15°}}{4}\cdot\frac{\sin{45°}}{4}\cdot\frac{\sin{75°}}{4}=\frac{\sin{15°}\sin{45°}\sin{75°}}{64}=\frac{\sin{45°}}{256}=\frac{\sqrt{2}}{512}$$
である．よって，$\cos{\theta}\tan{\theta}=\sin{\theta}$だから，
$$\prod_{k=1}^{9}\sin^2{(10k-5)°}=\frac{1}{131072}$$
であり，解答すべき値は$\mathbf{131073}$である．

解説

　まず，$3\leq{k}\leq{N}$を満たす整数$k$について，$\alpha_k^{N}+\alpha_k^{N-1}-7\alpha_k+5=0$が成立するから，$\alpha_k^{N-1}+\alpha_k^{N-2}=7-\dfrac{5}{\alpha_k}$である．ここで$\displaystyle\prod_{k=1}^{N}\alpha_k=\beta_N$とおくと，解と係数の関係により，$N$が$3$以上の奇数であるときは$\beta_N=-5，\displaystyle\sum_{k=1}^{N}\frac{\beta_N}{\alpha_k}=-7$が従い，$N$が$4$以上の偶数であるときは$\beta_N=5，\displaystyle\sum_{k=1}^{N}\frac{\beta_N}{\alpha_k}=7$が従う．これより，$N$が$3$以上の整数であるときは偶奇に関わらず
$$\sum_{k=1}^{N}(\alpha_k^{N-1}+\alpha_k^{N-2})= \sum_{k=1}^{N} \left(7-\frac{5}{\alpha_k}\right)=7N-5\times\frac{\sum_{k=1}^{N}\frac{\beta_N}{\alpha_k}}{\beta_N}=7N-7$$
が成立する．以上より，求める値は
$$\sum_{N=3}^{100}\sum_{k=1}^{N}(\alpha_k^{N-1}+\alpha_k^{N-2})=7\times(3+4+\dots+100)-7\times98=\mathbf{34643}$$
である．

組合せ

解説

　$a,b,c$の十の位の数字を決定する方法は，大小関係より相異なる$3$つの数字を選ぶ方法と一致するため${}_{10}\mathrm{C}_3=120$通り．また，十の位の数字の決定によって大小関係は満たされるため，一の位の数字を決定する方法は$7\times6\times5=210$通り．よって，求める値は$120\times210=\mathbf{25200}$通り．

解説

　まず，正十二面体の$2$頂点を結ぶ線分の長さは$5$種類あるので，それらを短い順に$A,B,C,D,E$とする．長方形の対角線も$A\sim{E}$のいずれかであることを踏まえて調べると，長方形の隣り合う二辺の長さの組は$(A,D)，(B,B)，(B,C)$のいずれかである．
　$(A,D)$であるものは，正十二面体の辺の数が$30$であることより$30÷2=15$通りある．
　$(B,B)$であるものは，正十二面体の$2$頂点を結ぶ線分のうち，長さが$B$であるものは$12\times5=60$あるから，正方形であることと合わせて$60\times2÷4=30$通りある．
　$(B,C)$であるものは，正十二面体の$2$頂点を結ぶ長さ$B$の線分が$60$あることより$60÷2=30$通りある．
　よって，$15+30+30=\mathbf{75}$通り．

解説

　以下，${0}\leq{x}\leq{7}$かつ${0}\leq{y}\leq{7}$かつ ${0}\leq{z}\leq{7}$の範囲を良い範囲と呼ぶ．
　良い範囲において点$(x,y,z)$に書き込まれる数は，点$(0,0,0)$から点$(x,y,z)$まで辺上を通って移動する最短経路数と一致する．さらにこの値は，$\dfrac{(x+y+z)!}{x!y!z!}$に等しい．良い範囲におけるこの値の分母は明らかに$11$の倍数でないため，$\displaystyle\prod_{x=0}^{7}\displaystyle\prod_{y=0}^{7} \displaystyle\prod_{z=0}^{7}(x+y+z)!$が$11$で割り切れる回数を考える．
　${0}\leq{x+y+z}\leq{10}$であるとき，$(x+y+z)!$は$11$で割り切れない．また，${11}\leq{x+y+z}\leq{21}$であるとき，$(x+y+z)!$は$11$でちょうど$1$回割り切れる．そして，${0}\leq{x+y+z}\leq{10}$となるような$(x,y,z)$の組と${11}\leq{x+y+z}\leq{21}$となるような$(x,y,z)$の組は組$(7-x,7-y,7-z)$を考えることで同数あることが容易に確かめられる．また，これらによって良い範囲にある格子点は網羅される．よって，求める回数は$8^3÷2\times1=\mathbf{256}$回である．

解説

　まず，$a_i,a_{i+1},\dots,a_j$の中に$3$があると明らかに$\displaystyle\prod_{k=i}^{j}a_k$は$3$の倍数であるため，組$(i,j)$がスコアに寄与するためには$a_i,a_{i+1},\dots,a_j$の中に$3$が含まれない必要がある．そこで，数列に含まれる$4$つの$3$のうち左から$n$番目にあるものを$T_n(1\leq n\leq 4)$とし，$T_n$よりも左にある$1,2$の個数をそれぞれ$x_n,y_n$とする．(ただし，$T_4$より右にあるものは$x_5,y_5$とした．)このとき，明らかに$x_1+y_1+x_2+y_2+\dots+x_5+y_5=2020$である．また，$1\leq i\leq 5$に対し，「$1$を$x_i$個，$2$を$y_i$個並べてできる長さ$x_i+y_i$の数列が取り得るスコアの最小値」を$N_i$とするとき，求めるべきは$N_1+N_2+\dots+N_5$の取り得る最小値である．そこで，$N_i$について考える．$1$が$x_i$個，$2$が$y_i$個含まれる数列$b_1,b_2,\dots,b_{x_i+y_i}$を任意にとる．このとき，$1\leq j\leq k\leq x_i+y_i$に対して，$\displaystyle\prod_{l=j}^{k}b_l$を$3$で割った余りが$1$になることは，$b_j,b_{j+1},\dots,b_k$の中に$2$が偶数個含まれることと同値である．またこれは，$b_1,b_2,\dots,b_m$の中に含まれる$2$の個数を$c_m$としたとき，$c_{j-1}≡c_k\pmod{2}$となることと同値．(ただし，$c_0=0$とする．)ここで，数列$c_0,c_1,\dots,c_{x_i+y_i}$を考えると，これは隣接する$2$項の差が$0$または$1$となる広義単調増加な数列となり，$0,1,\dots,y_i$がいずれも$1$つ以上含まれる数列となる．このとき，組$(i,j)$がスコアに寄与することは，$c_{i-1}$と$c_j$の偶奇が一致することと同値だから，$c_0,c_1,\dots,c_{x_i+y_i}$に含まれる偶数の個数を$A$，奇数の個数を$B$とすると，スコアは
$${}_A\mathrm{C}_2+{}_B\mathrm{C}_2=\frac{A^2+B^2-(A+B)}{2}=\frac{A^2+B^2-(x_i+y_i+1)}{2}$$
になることがわかる．また，この値の下限は，$x_i+y_i$が奇数のときは$\dfrac{(x_i+y_i)^2-1}{4}$となり，偶数のときは$\dfrac{(x_i+y_i)^2}{4}$となることが容易に確かめられる．よって，$x_i+y_i=s_i$とし，$s_1,s_2,\dots,s_5$のうち奇数であるものの個数を$h$とすると，
$$N_1+N_2+\dots+N_5\geq\frac{s_1^2+s_2^2+\dots+s_5^2-h}{4}$$
であることがわかる．$s_1+s_2+\dots+s_5=2020$のため，この値は集合$\{s_1,s_2,s_3,s_4,s_5\}$を多重集合として$\{404,404,404,404,404\}$または$\{403,404,404,404,405\}$または$\{403,403,404,405,405\}$と一致するとき最小値$204020$をとるとわかる．よって，$N_1+N_2+\dots+N_5\geq{204020}$であり，スコアの取り得る最小値も$204020$以上とわかる．
　そして，以下のように数列$a_1,a_2,\dots,a_{2024}$を定めることで，スコアは$204020$となる．

• $a_{405}=a_{810}=a_{1215}=a_{1620}=3$
• $1\leq i\leq 404，811\leq i\leq1214$の場合，$i$が偶数ならば$1$，奇数ならば$2$
• $406\leq i\leq 809，1216\leq i\leq 1619$の場合，$i$が偶数ならば$2$，奇数ならば$1$
• $1621\leq i\leq 2024$の場合，$i=1620+3n(1\leq n\leq 38)$または$i=1736$または$i=1737+2m(1\leq m\leq 143)$と表されるならば$2$，そうでないならば$1$

　以上より，求めるべき最小値は$\mathbf{204020}$である．

幾何

解説

　内心が角の二等分線の交点であることと簡単な角度追跡により，$\angle{AHP}=\angle{AIP}=120°$がわかる．また，$AH=AI$より$\angle{AHI}=\angle{AIH}$である．これらのことより，
$$\angle{PHI}=\angle{AHP}-\angle{AHI}=\angle{AIP}-\angle{AIH}=\angle{PIH}$$
であるから，$PH=PI$がわかる．
　$AH=AI，PH=PI$より$\triangle{AHP}\equiv\triangle{AIP}$であるから，$\angle{PAH}=\angle{PAI}=\angle{IAC}$より$\angle{PAH}=10°$がわかる． よって，$\angle{HPI}=(60°-10°)\times2=\mathbf{100}°$である．

解説

　まず，$\angle{AFE}=\angle{ADE}$より$4$点$A,D,F,E$は共円である．これより，$\angle{EAF}=\angle{EDF}$であり，$\angle{BAF}=\angle{EAC}$より$\angle{BAE}=\angle{FAC}$である．これらと$\angle{BAE}=\angle{EDF}$から$\angle{BAE}=\angle{EAF}=\angle{FAC}$がわかり，$AB:AF=AE:AD=5:6，AE:AC=3:5$を得る．ここで，$AE=15x$とおくと，$AD=18x，AC=25x$だから$DC=7x$となる．よって，方べきの定理より
$$7x\cdot25x=10\cdot16，x^2=\frac{32}{35}$$
であり，$AE=15x=\sqrt{\dfrac{1440}{7}}$だから，解答すべき値は$\mathbf{1447}$である．

解説

　線分$AC$上に$AB=AX$なる点$X$をとると，$P$は$CX$の中点である．また，直線$PQ$と直線$AC$の交点を$R$とすると，三角形$CQR$の外接円は$AC$に接する．よって，$$XP^2=CP^2=PR\cdot PQ$$であるので，三角形$XQR$の外接円は$AC$に接することがわかる．
　さらに，$B,X$を通り$AB,AC$に接する円を$\Omega$とし，この円と三角形$ABC$の外接円，$BC$の交点をそれぞれ$Q^\prime,R^\prime$とすると，簡単な角度追跡により$\angle CQ^\prime R^\prime=\angle ACB$であるので，三角形$CQ^\prime R^\prime$が$AC$に接することがわかり，$\Omega$が$AC$に$X$で接することから，方べきの定理より，直線$Q^\prime R^\prime$は$CX$の中点，すなわち$P$を通る．$\angle BQ^\prime R^\prime=\angle ABC$と併せて，$Q^\prime,R^\prime$はそれぞれ$Q,R$と一致することがわかり，これにより$B,Q,R,X$は同一円周上にあることがわかる．
　以上から，$\triangle BQX \sim \triangle XQC$と$\triangle ABQ \sim \triangle CRQ$が角度追跡によっててわかり，$XQ^2=120,QR=8$がわかる．
$PQ=x$とすると，中線定理と方べきの定理より，$$10^2+120=2\lbrace x^2+x(x-8) \rbrace$$これを解くことで，$x=2+\sqrt{59}$が求められるので，解答すべきは$\textbf{61}$．

解説

　$I$について$D$と対称な点を$G$とする．このとき，$6$点$[A,F,E,R,Q,P]$と$[M,B,C,G,I,D]$は相似だから$3$点$M,G,B$は共線．さらに，
$$\angle{BGI}=\frac{\angle{BMC}}{2}=\frac{\angle{BAC}}{2}=\angle{BAI}$$
より$4$点$A,G,I,B$は共円．いま，$MG=MA$であり，$\angle{AMG}=2\angle{AEG}$より$M$は三角形$AGE$の外心．さらに，$\triangle{MGI}\sim\triangle{MIB}$より$MB=9$，相似比から$IG=2x，IB=3x$とすると$BD=\sqrt{5}x，BG=\sqrt{21}x$であり，$x=\dfrac{5}{\sqrt{21}}$である．
　ところで，$\triangle{MAB}≡\triangle{MEC}$より$AB=CE$が成り立つ．$BD:DC=BG:(GM+MC)=5:13$だから，
$$AB=\frac{13}{5}BD=\frac{13}{5}\cdot\frac{5\sqrt{5}}{\sqrt{21}}=\sqrt{\frac{845}{21}}$$
であり，特に解答すべき値は$\mathbf{866}$である．

整数

解説

　$2025\times10^n=2^n\times3^4\times5^{n+2}$だから，
$$\frac{1}{d(2025\times10^n)}= \frac{1}{5}\times\frac{1}{(n+1)(n+3)}$$
である．これより，
$$\frac{a}{b}=\sum_{n=0}^{98} \left(\frac{1}{5}\times\frac{1}{(n+1)(n+3)}\right)=\frac{1}{5}\times\frac{1}{2}\times\left(1+\frac{1}{2}-\frac{1}{100}-\frac{1}{101}\right)= \frac{14949}{101000} $$
だから，解答すべき値は$\mathbf {115949}$．

解説

　以下，正整数$y$が正整数$x$で割り切れる最大の回数を$v_x(y)$で表す．
　まず，$d(n)=4$より${p}\leq{q}$を満たす素数$p,q$を用いて$n=p^3$または$n=pq$と表される．
　$n=p^3$であるとき，$v_{p}((n-1)!)=a$とし，ある正の整数$b$が存在して
$$d(n!)=b(a+4)，d((n-1)!)=b(a+1)$$
であるから，$a=\dfrac{23}{5}$を得るが，$a$が整数であることと矛盾し，条件を満たす$n$は存在しない．
　$n=pq$であるとき，$v_{p}((n-1)!)=a，v_{q}((n-1)!)=b$とし，ある正の整数$c$が存在して
$$d(n!)=c(a+2)(b+2)，d((n-1)!)=c(a+1)(b+1)$$
であるから，問題の条件と合わせて
$$\frac{(a+2)(b+2)} {(a+1)(b+1)}= \frac{43} {28}$$
である．これは$(15a-13)(15b-13)=1204$と変形でき，${p}\leq{q}$より${a}\geq{b}$であることを考慮すると，正の整数の組$(a,b)$として考えられるものは$(a,b)=(41,1)$のみだとわかる．
　これより，${p}\leq{q}，v_p((pq)!)=42，v_q((pq)!)=2$を満たす素数の組$(p,q)$を全て求めれば良い．まず，$p=2$であるとき，$pq$は偶数であるから$pq=46$であり，$q=23$となる．このとき，$v_{23}(46!)=2$より$n=46$は問題の条件を満たす．一方，${p}\geq{3}$であるとき，${v_q((pq)!)}\geq{3}$だから条件を満たす$n$は存在しない．
　以上より，$n$として考えられる値は$46$のみなので，求める値は$\mathbf{46}$である．

解説

　まず，$1$を$24$個並べてできる整数$\dfrac{10^{24}-1}{9}$はフェルマーの小定理より$7$の倍数．これより，求めるべきは$0\leq{a_1}\leq{a_2}\dots\leq{a_{10}}\leq23$を満たす非負整数組$(a_1,a_2,\dots,a_{10})$全てに対する，$10^{a_1}+10^{a_2}+\dots+10^{a_{10}}$を$7$で割った余りの総和だとわかる．ここで，非負整数$n$に対して$10^n$を$7$で割った余りは，$n≡0,1,2,3,4,5\pmod6$についてそれぞれ$1,3,2,6,4,5$であるから，本問題は以下の問題に言い換えられる．
　$1$以上$6$以下の整数のうちの$1$つが書かれた区別できるボールが各整数に対して$4$つずつ計$24$個ある．これらのボールの中から相異なる$10$個を選ぶ方法全てについて，選んだボールに書かれた整数の和を$7$で割った余りの総和を求めよ．
　この問題を考える．まず，選んだボールに書かれた整数の和を$7$で割った余りが$k(0\leq{k}\leq6)$になる選び方が何通りあるかを求める．これは$2$変数多項式$f(x,y)=(xy+1)^4(xy^2+1)^4\dots(xy^6+1)^4$ の $x^{10}y^{7m+k}(0\leq{m})$の係数の総和に等しい．$0< k$の場合，これは$y^{7-k}f(x,y)$の$x^{10}y^{7m}(0\leq{m})$の係数の総和に等しくなるため，$1$の原始$7$乗根を$\omega\left(=\cos\dfrac{2\pi}{7}+i\sin\dfrac{2\pi}{7}\right)$としたときの
$$\frac{[x^{10}]1^{7-k}f(x,1)+[x^{10}]\omega^{7-k}f(x,\omega)+\dots+[x^{ 10}](\omega^6)^{7-k}f(x,\omega^6)}{7}$$
の値に等しくなるとわかる．ただし，多項式$g$と非負整数$d$について$[x^d]g(x)$で$g(x)$の$x^d$の係数を表すものとした．ここで，$[x^{10}]1^{7-k}f(x,1)={}_{24}\mathrm{C}_{10}$は明らかである．また，$1\leq{l}\leq6$に対して$\{\omega^l,\omega^{2l},\dots,\omega^{6l}\}=\{\omega,\omega^2,\dots,\omega^6\}$が成立するため，$f(x,\omega^l)=(x^6-x^5+x^4-x^3+x^2-x+1)^4$が成立するとわかる．ここで，
$$(x^6-x^5+x^4-x^3+x^2-x+1)^4=(x^{12}-2x^{11}+3x^{10}-\dots-6x^7+7x^6-6x^5+5x^4-\dots-2x+1)^2$$
より，
$$[x^{10}]f(x,\omega^l)=[x^{10}](x^{12}-2x^{11}+3x^{10}-\dots-6x^7+7x^6-6x^5+5x^4-\dots-2x+1)^2$$
となり，これは
$$(3\times1+(-4)\times(-2)+5\times3+(-6)\times(-4)+7\times5)\times2+(-6)^2=206$$
と計算できる．そして$1\leq{k}\leq6$のとき$\{\omega^{7-k},(\omega^2)^{7-k},\dots,(\omega^6)^{7-k}\}=\{\omega,\omega^2,\dots,\omega^6\}$だから，
$$\frac{[x^{10}]1^{7-k}f(x,1)+[x^{10}]\omega^{7-k}f(x,\omega)+\dots+[x^{ 10}](\omega^6)^{7-k}f(x,\omega^6)}{7}=\frac{{}_{24}\mathrm{C}_{10}+206(\omega+\omega^2+\dots+\omega^6)}{7}=280150$$
が従う．よって，求めるべき値は$(1+2+\dots+6)\times280150=\mathbf{5883150}$である．

解説

　$i$と$10^{10}$の最大公約数を$g_i$とする．このとき，$i$日目に呼ばれる番号は$10^{10}$以下の正整数のうち$g_i$の倍数であるもの全てである．つまり，番号$j$が $i$ 日目に呼ばれることは，$j$が$g_i$の倍数であることと同値である．これより，$g_i$は$j$の約数かつ$10^{10}$の約数であり，$j$と$10^{10}$の最大公約数を$g_j$とすると，$g_i$は$g_j$の約数とわかる．よって，番号$j$が$i$日目に呼ばれるような$i$の集合は，ある$g_j$の約数$n$によって$g_i=n$が実現されるような$i$の集合と一致することがわかる．ここで，$g_i=n$となるような$i$の個数は，$1\leq{m}\leq\dfrac{10^{10}}{n}$かつ$\gcd\left(m,\dfrac{10^{10}}{n}\right)=1$を満たすような正整数$m$の個数に等しく，それは$\varphi\left(\dfrac{10^{10}}{n}\right)$であるとわかる．以上より，番号$j$が呼ばれる合計回数は，$g_j$の約数$n$全てに対して$\varphi\left(\dfrac{10^{10}}{n}\right)$を足し合わせた値に一致する．ここで，$10$以下の非負整数$a,b$について$g_j=2^a\times5^b$とすると，$g_j$の約数は${c}\leq{a}，{d}\leq{b}$なる非負整数$c,d$を用いて$2^c\times5^d$と表される整数全てとなり，番号$j$が呼ばれる合計回数は
$$\sum_{c=0}^{a}\sum_{d=0}^{b}\varphi(2^{10-c}\times5^{10-d})=\sum_{c=0}^{a}\varphi(2^{10-c})\sum_{d=0}^{b}\varphi(5^{10-d})$$
となることがわかる．そして，$a<10$のとき$\displaystyle\sum_{c=0}^{a}\varphi(2^{10-c})=2^{10}-2^{9-a}$，$a=10$のとき$\displaystyle\sum_{c=0}^{a}\varphi(2^{10-c})=2^{10}$，$b<10$のとき$\displaystyle\sum_{d=0}^{b}\varphi(5^{10-d})=5^{10}-5^{9-b}$，$b=10$のとき$\displaystyle\sum_{d=0}^{b}\varphi(5^{10-d})=5^{10}$であることが容易に確かめられる．また，$g_j=2^a\times5^b$となるような$j$の個数が$\varphi(2^{10-a}\times5^{10-b})$であることも容易にわかる．
　これを踏まえて番号$j$が呼ばれる合計回数が$7$の倍数になるような$j$の個数を求める．まず，$\displaystyle\sum_{c=0}^{a}\varphi(2^{10-c})$が$7$の倍数になるのは$a=2,5,8$の場合であり，$\displaystyle\sum_{d=0}^{b}\varphi(2^{10-d})$が$7$の倍数になるのは$b=5$の場合であることから，満たすべき条件は「$a\in\{2,5,8\}$または$b=5$」であるとわかる．まず，$a\in\{2,5,8\}$を満たすような$j$の個数を求める．これは，
$$(\varphi(2^2)+\varphi(2^5)+\varphi(2^8))(\varphi(5^0)+\varphi(5^1)+\dots+\varphi(5^{10}))=146\times5^{10}=1425781250$$
と計算できる．同様に，$b=5$を満たすような$j$の個数は，
$$(\varphi(2^0)+\varphi(2^1)+\dots+\varphi(2^{10}))(\varphi(5^5))=2^{10}\times2500=2560000$$
と計算できる．そして，$a\in\{2,5,8\}$かつ$b=5$となるような$j$の個数は
$$(\varphi(2^2)+\varphi(2^5)+\varphi(2^8))(\varphi(5^5))=146\times2500=365000$$
であるため，結局求めるべき答えは$1425781250+2560000-365000=\mathbf{1427976250}$になるとわかる．

敗者復活戦

解説

　問題の$3$次方程式は以下のように変形できる．
$$(x-2k)(x-5k)(x-10k)=0$$
　これより，この方程式の$3$解は$2k,5k,10k$だとわかる．また，このうちちょうど$2$つが整数であることから$k$は有理数だとわかり，条件は$k$を既約分数で表したときの分母が$2$または$5$であることと同値．よって，$k$として考えられるものは
$$\frac {1} {2}，\frac {1} {5}， \frac {2} {5}，\frac {3} {5}，\frac {4} {5} $$
だから，解答すべき値は$\mathbf{637}$である．

解説

$$|CDP|=78÷2-27=12，|DAP|=78÷2-15=24$$
だから，
$$EP=\frac{12}{27+12}BC=\frac{4}{13}BC，FP=\frac{24}{15+24}AB=\frac{8}{13}AB$$
である．よって，四角形$DEPF$の面積は
$$78\times\frac{4}{13}\times\frac{8}{13}=\frac{192}{13}$$
であるから，解答すべき値は$\mathbf{205}$である．

解説

　以下，合同式の法を $3$ とする．
　$\omega^3=1$より$a_k≡0$のとき$\omega^{a_k}=1$，$a_k≡1$のとき$\omega^{a_k}=\omega$，$a_k≡2$のとき$\omega^{a_k}=\omega^2$である．このことと$\omega^2+\omega=-1$より$(a_1,a_2,\dots,a_{10})$をどのように定めても整数$m,n$を用いて
$$\sum_{k=1}^{10}\omega^{a_k}=m\omega+n$$
と表すことができ，$m=0$であるときのみこれは整数値を取る．また，$m=0$になるのは$a_k≡1$なる$a_k$と$a_k≡2$なる$a_k$の個数が等しいときである．
　以上より$a_k ≡0,1,2$となるものの個数の組はそれぞれ高々$5$個であることに留意して$(4,3,3)，(2,4,4)，(0,5,5)$のいずれかであり，求める個数は
$${}_5\mathrm{C}_4\cdot({}_5\mathrm{C}_3)^2+{}_5\mathrm{C}_2\cdot({}_5\mathrm{C}_4)^2+1=\mathbf{751}$$
である．

解説

　以下，九九表の奇数行奇数列のマス目を奇マス，偶数行偶数列のマス目を偶マス，それ以外のマス目を両マスと呼ぶ．
　このとき，元の九九表に書かれている数の総和は$(1+2+\dots+9)^2=2025$，奇マスに書かれている数の総和は$(1+3+5+7+9)^2=625$，偶マスに書かれている数の総和は$(2+4+6+8)^2=400$，両マスに書かれている数の総和は$2025-625-400=1000$である．
　新しく奇マスに書き込まれる数の総和は，奇マスの隣がすべて両マスであることと，各両マスの上下左右に奇マスがちょうど$2$マスずつあることより$1000\times2=2000$である．よって，求める値は$2025-625+2000=\mathbf{3400}$である．

解説

　以下，$a$行$b$列のマス目を$(a,b)$と表す．
　まず，中心間の距離が$(\sqrt2,\sqrt5,\sqrt5)$であるような $3$マスの組は
$$\{(1,1),(2,3),(3,2)\}，\{(1,2),(2,1),(3,3)\}，\{(1,2),(2,3),(3,1)\}，\{(1,3),(2,1),(3,2)\}$$
の$4$組である．ここで，$(1,2),(2,1),(3,2),(2,3)$を順にア，イ，ウ，エとすると，アとイ，イとウ，ウとエ，エとアは条件よりそれぞれ色が異なる．これら$4$マスの塗り分け方は，アが赤，イが青であるものが$3$通りあることより$3\times2\times3=18$通りある．よって，ア，イ，ウ，エの彩色が決まれば角の$4$マスの彩色が決まることと，$(2,2)$の彩色は任意であることより求める場合の数は$18\times3=\mathbf{54}$通りである．

解説

　以下，$\min(A,B,C)$で$A,B,C$の最小値を表す．
$$v_2(n)=x，v_3(n)=y，v_5(n)=z$$
とすると，問題の条件は$540,600,2250$の素因数分解を考えることで，
$$\min\left(x,\left\lfloor\frac{y}{2}\right\rfloor,\left\lfloor\frac{z}{3}\right\rfloor\right)=100，\min\left(\left\lfloor\frac{x}{2}\right\rfloor,\left\lfloor\frac{y}{3}\right\rfloor,z\right)=70，\min\left(\left\lfloor\frac{x}{3}\right\rfloor,y,\left\lfloor\frac{z}{2}\right\rfloor\right)=46$$
と言い換えられるので，$140\leq{x}，210\leq{y}，300\leq{z}$である．以下これをもとに$x$の値で場合分けする．$x=140$であるとき，右$2$式は満たされ，$1$式目より$z=300,301,302$のとき条件を満たす．$x\geq{141}$であるとき，$x,y,z$の範囲より$3$式目が満たされないため不適である．
　よって，$n$は非負整数$a$と$2$以下の非負整数$b$と$2,3,5$を素因数に持たない正の整数$c$を用いて，
$$n=2^{140}\cdot3^{210+a}\cdot5^{300+b}\cdot{c}$$
と表される．このとき， $3^a\cdot5^b\cdot{c}$として考えられる値は$125$の倍数でない任意の奇数であり，特に$70$番目に小さいものは$141$だから$(a,b,c)=(1,0,47)$である．そのため
$$N=2^{140}\cdot3^{211}\cdot5^{300}\cdot47$$
である．よって，$N$の正の約数の個数は$\mathbf{17994984}$個である．

解説

　直線$CG$について点$P$と対称な点を$P'$とすると，$3$点$A,G,P'$が同一直線上にあり，$4$点$A,B,P',C$が同一円周上にあることが容易に確認できる．よって，方べきの定理により
$$BC^2=36\cdot8\cdot4=\mathbf{1152}$$
である．

解説

　$X^{5} - X^{2} + 3X - 5 = 0$は明らかに$X = 0$を解として持たないため，$a, b, c, d, e$はいずれも$0$ではない．よって，$a^{4} = \dfrac{a^{5}}{a} = \dfrac{a^{2} - 3a + 5}{a} = a - 3 + \dfrac{5}{a}$が成立すると分かる．これより，$a^{4} + b + c + d + e = a + b + c + d + e - 3 + \dfrac{5}{a} = -3 + \dfrac{5}{a}$が分かる．(ここで，解と係数の関係より$a + b + c + d + e = 0$であることを用いた．)同様に考えて，$a + b^{4} + c + d + e = -3 + \dfrac{5}{b}, \dots, a + b + c + d + e^{4} = -3 + \dfrac{5}{e}$も分かる．ここで，$X^{5} - X^{2} + 3X - 5 = 0$の$X$を$\dfrac{1}{X}$ に置き換えて得られる$\dfrac{1}{X^{5}} - \dfrac{1}{X^{2}} + \dfrac{3}{X} - 5 = 0$ は $X = \dfrac{1}{a}, \dots, \dfrac{1}{e}$を解に持つため，特に$ - 5X^{5} + 3X^{4} - X^{3} + 1 = 0$は$X = \dfrac{1}{a}, \dots, \dfrac{1}{e}$を解に持つ$5$次方程式と分かる．さらに，この方程式の$X$を$\dfrac{X + 3}{5}$に置き換えて得られる方程式$- \dfrac{1}{625} (X+3)^{5} + \dfrac{3}{625} (X+3)^{4} - \dfrac{1}{125} (X+3)^{3} + 1 = 0$は$X = -3 + \dfrac{5}{a}, \dots, -3 + \dfrac{5}{e}$を解として持つと分かる．よって，$f(X) = (X+3)^{5} - 3(X+3)^{4} + 5(X+3)^{3} - 625$が分かる．特に，$f(X)$の$X^{2}$の係数は$3^{3}\times {}_5\mathrm{C}_2 - 3 \times 3^{2} \times {}_4\mathrm{C}_2 + 5 \times 3^{1} \times {}_3\mathrm{C}_2 = \mathbf{153}$である．

解説

　一般に，${p}\geq{r}，{q}\geq{s}$を満たす非負整数$p,q,r,s$について，点$(0,0)$から点$(p,q)$に点$(r,s)$を通って辺上を移動する最短経路数は
$${}_{r+s}\mathrm{C}_{r}\cdot{}_{p+q-(r+s)}\mathrm{C}_{p-r}$$
であるため，$M$は「${x}\leq{60}，{y}\leq{100}$なるすべての非負整数の組$(x,y)$について，点$(0,0)$から点$(60,40)$に点$(x,y)$を通って辺上を移動する最短経路数の総和」と言い換えられる．さらに，点$(0,0)$から点$(60,40)$に辺上を移動する${}_{100}\mathrm{C}_{40}$の最短経路はそれぞれ$101$個の格子点を通るため，$1$つの最短経路が$101$点に寄与する，と捉えることで
$$M={}_{100}\mathrm{C}_{40}×101$$
がわかる．よって，解答すべき値は$101+97=\mathbf{198}$である．

解説

　$3, 5$のいずれとも互いに素な正整数$M$，及び非負整数$a, b$によって$N = 3^a \times 5^b \times M$と表したとする．このとき，
$$f(N) = \sum_{i = 0}^{4} \sum_{j = 0}^{2} 3^{\min(i, a)} \times 5^{\min(j, b)} = \left ( \sum_{i = 0}^{4} 3^{\min(i, a)} \right ) \times \left (\sum_{j = 0}^{2} 5^{\min(j, b)} \right )$$
と表される．ここで，$\displaystyle \sum_{i = 0}^{4} 3^{\min(i, a)}$の値は
$a = 0, \ a = 1, \ a = 2, \ a = 3, \ a \geq 4$の場合にそれぞれ$5, 13, 31, 67, 121$となり，$\displaystyle \sum_{j = 0}^{2} 5^{\min(j, b)}$の値は$b = 0, \ b = 1, \ b \geq 2$の場合にそれぞれ$3, 11, 31$となることが容易に確認できる．よって，$ \left ( \displaystyle \sum_{i = 0}^{4} 3^{\min(i, a)} \right ) \times \left (\displaystyle \sum_{j = 0}^{2} 5^{\min(j, b)} \right )$の取り得る値は$15$種類しかないとわかる．ここで，$d(N^2 f(N))$の値が奇数のため，$N^2 f(N)$ が平方数であること，つまり，$f(N)$が平方数であることが分かる．これを満たすのは，$a = 2, \ b \geq 2, \ f(N) = 31^2$の場合のみである．そして，この条件下で$d(N^2 f(N)) = 2025$となる$N$の値を調べると，$N = 2^4 \times 3^2 \times 5^2 \times 7$が条件を満たす最小値であることがわかる．よって，解答すべき値は$\mathbf{25200}$となる．

解説

　簡単な角度追跡から，$\triangle{ANX}$は$AN=XN，\angle{ANX}=\angle{BAC}$を満たす二等辺三角形であり，$\triangle{NBC}$は$BN=CN，\angle{BNC}=\angle{BAC}$を満たす二等辺三角形であることがわかる．よって，点$N$を中心とした回転相似を考えることで，$\triangle{NAB}≡\triangle{NXC}$がわかり，特に$AB=XC$である．次に，円$ALM$と直線$BC$の交点を$P(≠L)$とする．簡単な角度追跡から$P$は$\angle{BAC}$の外角の二等分線と直線$BC$の交点であることがわかる．そのため，外角の二等分線定理から$BP:CP=BA:CA$である．また，円$ALM$と直線$AB$の交点を$Y(≠A)$とすると，方べきの定理から$CX \times CA=CL \times CP，BY \times BA=BL \times BP$であり，$BP:CP=BA:CA，BL=CL$と合わせて$CX=BY$を得る．これより$AB=BY$である．$AB=t$とすれば，外角の二等分線定理により$BP=\dfrac{20t}{41-t}$と表せるので，方べきの定理より$t^2=10\times\dfrac{20t}{41-t}$だから$t=\dfrac{41+\sqrt{881}}{2}$となる．よって，解答すべき値は$\mathbf{924}$である．

決勝

解説

$$\dfrac{1}{a}+\dfrac{1}{b}-\dfrac{2(a^2+b^2)}{a^3+b^3}=\dfrac{(a+b)(a^3+b^3)-2ab(a^2+b^2)}{ab(a^3+b^3)}=\dfrac{(a-b)(a^3-b^3)}{ab(a^3+b^3)}\geq0$$
より，$\dfrac{1}{a}+\dfrac{1}{b}\geq\dfrac{2(a^2+b^2)}{a^3+b^3}$なので，操作により，黒板に書かれた数の逆数和は広義単調減少とわかる．よって，最初の黒板に書かれた数の和は$n$なので，黒板に書かれた数の逆数和は常に$n$以下であり，最後に残る数は$\dfrac{1}{n}$以上であることが示された．

解説

　まず，橋を$\dfrac{7n^2-3n}{2}$本以下しかかけられないことを示す．同じ都市が保有している島同士の間に橋をかけてしまっても$3$番目の条件には影響を与えないため，同じ都市が保有している島同士の間にはすべて橋がかけられているとして良い．また，都市$A$が保有する島を$a_0,a_1,\dots,a_{n-1}$，都市$B$が保有する島を$b_0,b_1,\dots,b_{n-1}$，都市$C$が保有する島を$c_0,c_1,\dots,c_{n-1}$とする．その上で，$m=0,1,\dots,n^2-1$についての数列$\{x_m\}，\{y_m\}，\{z_m\}$を以下のように定める．

• $\{x_m\}=\left\lfloor\dfrac{m}{n}\right\rfloor$
• $\{y_m\}=m\%n$($m$を$n$で割った余り)
• $\{z_m\}=\left(\left\lfloor\dfrac{m}{n}\right\rfloor+m\%n\right)\%n$

　このとき，異なる$2$つの島同士の組の集合を$S_m=\{(a_{x_m},b_{y_m})，(b_{y_m},c_{z_m})，(c_{z_m},a_{x_m})\}$とし，$S=S_0\cup S_1\cup\dots\cup S_{n^2-1}$とする．すると，$S$は異なる都市が保有している$2$つの島同士の組を$1$つずつ含む集合であることが確認できる．また，$0\leq m\leq n^2-1$について，$a_{x_m}$と$b_{y_m}$，$b_{y_m}$と$c_{z_m}$，$c_{z_m}$と$a_{x_m}$の間にすべて橋をかけると$3$番目の条件に反することから，異なる都市が保有している$2$つの島同士の間にかけられた橋の本数の合計は，高々$2n^2$本であるとわかる．同じ都市が保有している島同士にかけられた橋は合計$3\times{}_{n}\mathrm{C}_{2}$本であるため，かけられる橋の本数は計$2n^2+3\times{}_{n}\mathrm{C}_{2}=\dfrac{7n^2-3n}{2}$本以下だと示された．
　次に，条件を満たすように$\dfrac{7n^2-3n}{2}$本の橋をかけられることを示す．これは，相異なる$2$つの島$X,Y$について，一方が$A$が保有する島で一方が$C$が保有する島の場合は$X$と$Y$の間には橋をかけず，そうでない場合は$X$と$Y$の間には橋をかけるようにすれば良い．
　以上より，答えは$\dfrac{7n^2-3n}{2}$本である．

解説

　点$O$に関して点$A,T$と対称な点を$A',T'$とする．$AA',TT'$はともに三角形$ABC$の外接円の直径だから$\angle TPT'=\angle AQA'=90°$であり，$3$点$P,H,T'$と$Q,D,A'$は共線だとわかる．また，四角形$ATA'T'$は長方形だから$A'T'\parallel DH$であり，$\triangle HRD\sim\triangle T'RA'$がわかる．そして，$\angle BHC=180°-\angle BAC=\angle BTC$より，$T$は直線$BC$について$H$と対称で，$HD=TD$である．これらのことより，$RD:RA'=HD:T'A'=TD:TA$であるから，$RD:DA'=TD:DA$がわかり，$\triangle RDT\sim\triangle A'DA$だから$RT\parallel AA'$，すなわち$AO\parallel RT$が示された．

解説

　$m$を$2,3,\dots,b-1$で割った余りが異なることに留意する．いま，$k\geq2$について次の補題が成り立つ．

補題:$m$を$a,2a,\dots,ka$で割った余りが相異なるとき，これらは公差が$a$の等差数列を成す．

　$a=2$でこの補題を適用し，$m$を$2,4,6,\dots$で割った余りは$1,3,5,\dots$または$0,2,4,\dots$だとわかる．さらに，任意の$s<\dfrac{b}{2}$について，$a=s$でこの補題を適用することで，$\dfrac{b}{2}$より小さい素因数を持つような任意の$b$未満の正整数$t$について$m$を$t$で割った余りが常に$t-1$または常に$t-2$であることがわかる．
　$\dfrac{b}{2}$より小さい素因数を持つような$b$未満の正整数の集合を$S$とする．$b$が$S$のいくつかの要素の最小公倍数として表されるとすると，$n$を$b$で割った余りも$b-1$または$b-2$である．また，$a$を$S$の要素とすると，$(n\pmod a，n\pmod b)=(a-1,b-1)，(a-2,b-2)$だから$n$を$a,b$で割った余りは等しくならない．したがって$a$は$S$の要素ではなく，素数であるとわかる．また，$b$が$S$のいくつかの要素の最小公倍数として表されないとすると，$b$はある素数$p$と正整数$q$によって$2p$または$p^q$と表される．以上により，題意は示された．

解説

　以下，$P(m,n)$で与式への$x=m，y=n$の代入を表す．
$$P(x,0):x(f(x)+f(0))+f(0)=f(f(x))^2$$
より，実数$a,b$について$f(a)=f(b)$とすると，
$$f(a)=f(b)=-f(0)(\dots①)$$
が成り立つ．
$P(0,x):f(x^2)=f(f(0)+x)^2$と$P(0,-x)$を比較して，
$$|f(x+f(0))|=|f(-x+f(0))|(\dots②)$$
を得る．
　ここで，$f(0)\neq0$とする．②に$x=f(0)$を代入して$|f(2f(0))|=|f(0)|$を得る．また，$P(0,0)$より$f(0)>0$で，$f(2f(0))>0$とすると①より$f(2f(0))=f(0)=-f(0)$が成り立つので$f(0)=0$となり不適．また，$f(2f(0))<0$とすると$P(0,\sqrt{2f(0)})$より$f(f(0)+\sqrt{2f(0)})$が実数とならず不適．よって$f(0)=0$である．
　したがって，$P(x,0)$より$xf(x)=f(f(x))^2$であり，$P(0,x)$より$f(x^2)=f(x)^2$であるから，$xf(x+y)+(x+y)f(y)=f(f(x)+y)^2$である．これに$y=-x$を代入し，$f(f(x)-x)^2=0$だから
$$f(f(x)-x)=0(\dots③)$$
である．
　いま，$f(c)=0$となる実数$c\neq0$が存在すると仮定する．このとき$P(x,c-x)$より$cf(c-x)=f(f(x)+c-x)^2$が成り立つ．$c>0$とすると任意の$x$について$f(x)\geq0$となるが，$f(x^2)=f(x)^2$より$|f(x)|=|f(-x)|$だから$f(x)=f(-x)$となり，①より$0$でない実数$x$について$f(x)=0$である．$c<0$としても同様の議論により$f(x)=0$を得る．
　逆に仮定を満たさないとき，$f(x)=0$のとき$x=0$だから③より$f(x)=x$である．
　以上より，$f(x)=0，f(x)=x$である．またこれらは与式を満たす．

解説

(1)　以下，$\measuredangle$で有向角を表す．
　点$Q$に関して点$B$と対称な点を$X$とする．$AI$は円$IMN$と接し，中点連結定理より$MQ\parallel CX$なので，
$$\measuredangle CPN = \measuredangle AIN + \measuredangle CAI = \measuredangle IMN + \measuredangle MNB = \measuredangle MQN = \measuredangle CXN $$
である．よって，$4$点$N,X,P,C$は共円であり，$\measuredangle PXB =\measuredangle PCN = \measuredangle ABN $．したがって，$BR \parallel PX$であり，$QB=QX$より$Q$は$PR$の中点であることが示された．
(2)　$AC$と円$AIN$の交点を$Y(\neq A)$とする．$\angle INY= \angle IAX =\angle BNM，\angle IYN = 180°- \angle NAI = 90°=\angle BMN$なので，三角形$IYN$と三角形$BMN$は相似．
さらに，$\angle CPN=\angle MQN$であったので，$4$点$[I,Y,N,P]$と$[B,M,N,Q]$は相似．
以上より，$NP:PI=NQ:QB$で$PQ\parallel BI$，すなわち$PR\parallel BI$が示された．