JJMO2026本選解説

JJMO2026本選から少し時間が空きましたが、解いてみましたので解答(解説)を書きたいと思います。問題はこちら。

問1

上から$i$行目、左から$j$列目に書かれている数を$a_{i,j}$とする。
また、$d_{i,j}=a_{i,j+1}-a_{i,j}$とする。ここで、$d_{i,j}$は$0$または$1$であることに注意する。

まず、$n\leq 2^{2025}$を示す。
仮に、$n>2^{2025}$だとすると、鳩ノ巣原理より、ある$2^{2025}+1$以下の正の整数$s,t$であって$d_{s,1},d_{s,2},...,d_{s,2026}$と$d_{t,1},d_{t,2},...,d_{t,2026}$が順番も含めて等しいものが存在する。この時、$a_{s,i}-a_{t,i}$は$i$によらず、一定となるため条件を満たさない。よって$n\leq 2^{2025}$である。

今、$a_{1,1}=a_{2,1}=...=a_{2^{2025},1}=0$とし、$d_{i,j}$を$i-1$を$2$進数表記した時の下から$j$桁目とすれば、進数展開の一意性よりどの2行も必ず1箇所は異なり、必ず左端が等しいから条件を満たす。
よって、答えは$2^{2025}$。

問2

$\angle AQX=\angle AQP-\angle PQX=\angle APX-\angle PQB=\angle PBQ$より、$AQX \sim ABX$である。
同様に$APY\sim ACP$であるから、$AP=AQ$に気をつければ、
$AB\times AX=AQ^2=AP^2=AY\times AC$となる。
よって示された。

問3

$n$が偶数だとすると、$1$が奇数であることより、数列$\{d\}$の中に奇数と偶数が連続する場所が存在するが、この和が$2$べきとなることはないため、$n$は奇数である。
$n$の約数の個数が$3$個だとすると、$n=p^2$と表せる($p$は素数)。この時、$p+p^2$は$p$を素因数に持つため$2$べきではない。従って、$d_2=1$であるため、$1+p,1+p^2$が$2$べきである。今、$3^2+1\leq p^2+1\equiv 2\pmod 4$であるから、これは$2$べきではない。よって矛盾。
ここで、以下の補題を示す。
■ $n$の約数$d$について、$n$の約数$e< d$であって、$e+d$が$2$べきになるようなものは、高々1つ存在する。

証明

$2^s>d>2^{s-1}$となるような整数$s$を取ってくる。$2^{s-1}< e+d<2d<2^{s+1}$なので、$e+d=2^s$である。これは$e$が高々$1$つしかないことを示している。
よって示された。

補題を$d=n$に対して適用することで、$n=d_1$または$n=d_k$がわかる。対称性より、$n=d_1$として良い。また、$d_2$は$n$と互いに素であるため$1$である。
次に、$n$の最も小さい素数を$p$、$q=\frac np$として、$d=q$に対して補題を適用することで、$q$が$n$の約数の中で$n$の次に大きなものであることと合わせて、$q=d_k$となる。今、$k>3$だから、$d_{k-1}\neq 1$と$d_{k}=q$が互いに素なことより、$d_{k-1}=p$が得られる。仮に、$k\geq 5$だとすると、$n$の$3$番目に大きな約数$r\neq p$について、$r$が$r$以下の$n$の約数2つと隣接することになり、これは$d=r$について補題を適用することで矛盾が生じる。
以上より、$k=4,d_1=pq,d_2=1,d_3=p,d_4=q$となる。また、$p,q$は相異なる素数である。
$pq=2^a-1,p=2^b-1$とおき、$1< c=\frac a b$とすると、$b>1$に気をつけて、
$p+q=2^b-1+\frac{2^a-1}{2^b-1}=2^b-1+2^{b(c-1)}+2^{b(c-2)}+...+2^b+1\equiv2^{b+1}\pmod{2^{b+2}}$
とできる。
よって、$p+q=2^{b+1}$および、$c=2$がわかる。すなわち、$q=2^b+1$であり、$p,q,2^b$のいずれかは$3$の倍数であるから$p=3$が得られ、$q=5,n=15$がわかる。

従って、答えは$n=15$のみである。

問4

$2026=2n$とし、$r_i=\sqrt{\frac{x_i}{x_{i+1}}}$とする。更に、$k=\underset{i}{\min}{\{\max\{{r_i,\frac1{r_i}}\}\}}$とおく。
与式を
$(r_1+\frac1{r_1})(r_2+{\frac1{r_2}})...(r_{2n}+\frac1{r_{2n}})=(\frac{x_1+x_2}{\sqrt{x_1x_2}})(\frac{x_2+x_3}{\sqrt{x_2x_3}})...(\frac{x_{2n}+x_1}{\sqrt{x_{2n}x_1}})=3^{2n}$と変形する。
今、$r_i+\frac{1}{r_i}\geq k+\frac1k$だから、
$3^{2n}=(r_1+\frac1{r_1})(r_2+{\frac1{r_2}})...(r_{2n}+\frac1{r_{2n}})\geq (k+\frac1k)^{2n}$
となり、
$3\geq (k+\frac1k)\Rightarrow 0\geq k^2-3k+1$となり、
$k\geq \frac{3+\sqrt5}2$または$k\leq \frac{3-\sqrt5}2$であることがわかる。ここで、$k>1$より、前者である。
よって、$\frac Mm\geq k^2\geq (\frac{3+\sqrt5}2)^2=\frac{7+3\sqrt5}2$がわかる。
逆に、$x_1=x_3=x_5=...=x_{2n-1}=\frac{7+3\sqrt5}2,x_2=x_4=...=x_{2n}=1 $とすることで、$\frac Mm=\frac{7+3\sqrt5}2$となる。
よって、答えは$\frac{7+3\sqrt5}2$。

問5

一般化して、$n$枚のカードを並べる時に、並べ方が一意に定まる最小の$m=f(n)$を求める。

まず、以下の図1を考える。図1の上から$i$行目、左から$j$目を$(i,j)$とする。$(i,j)$に数字を入れていくことを考える。つまり、$(i,j)$には$i$枚目を入れた時に左から$j$番目に置かれていたカードに書かれた数を書き込む。すなわち、問題中の$(a_i,b_i,c_i)$は$(a_i,b_i)=c_i$に対応している。図1は特に、$n=5$の時の何も情報が入っていない時の様子を表している。
また、選ばれた$m$個の$(a_i,b_i)$を良いマスと呼ぶことにする。
$$ \begin{array}{c} \boxed{\phantom{0}} \\ \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \\ \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \\ \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \\ \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \quad \boxed{\phantom{0}} \\ \text{図1} \end{array} $$
まず、$f(n)\leq [\frac{2n}{3}]$を示す。
構成は以下に$n=3,4,5,7$の図を置いておくので、適当に察してください。(赤文字は良いマス、黒文字はそこから一意に定まる並べ方で並べた時の良いマス以外のマス)。
$$ \begin{array}{c} 1 \\ 1　\color{red}{2} \\ 1 \quad 2 \quad \color{red}{3} \\ \end{array} $$
$$ \begin{array}{c} 1 \\ 1 \quad 2 \\ 1 \quad {\color{red}2} \quad 3 \\ 1 \quad 2 \quad {\color{red}3} \quad 4 \\ \end{array} $$
$$ \begin{array}{c} 1 \\ 1 \quad 2 \\ 1 \quad {\color{red}2} \quad 3 \\ 1 \quad 2 \quad{\color{red}3} \quad 4 \\ 1 \quad 2 \quad 3 \quad 4 \quad{\color{red}5} \\ \end{array} $$
$$ \begin{array}{c} 1 \\ 1 \quad 2 \\ 1 \quad {\color{red}2} \quad 3 \\ 1 \quad 2 \quad{\color{red}3} \quad 4 \\ 1 \quad 2 \quad 3 \quad 4 \quad 5 \\ 1 \quad 2 \quad 3 \quad 4 \quad {\color{red}5} \quad 6\\ 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad {\color{red}6} \quad 7\\ \text{図2:構成} \end{array} $$

さて、ここからは帰納法で示す。$n=0,1,2$の時は、容易に確認できる。
$n=0,1,2,...,k-1$で$f(n)=[\frac{2n}3]$が成立しているとして、$n=k$でも成立することを示す。$f(k)< f(k-1)$だとすると、適当にやってダメなことがわかるので、$f$は広義単調増加である。

良いマスを1つ選びそのマスに書かれている数字$c$が書かれているマスを全て表示することを考える。この状態で、残りのマスに数字を一意に書き込むために必要な良いマスの個数の最小値は、$m-1$以下である。(図3は$n=7$の時に$c=4$を表示したときの一例)

$$ \begin{array}{c} \color{green} \boxed{\phantom 0} \\ \color{green}\boxed{\phantom 0} \quad \boxed{\phantom 0}\\ {\color{green}\boxed{\phantom 0} \quad \boxed{\phantom 0}} {\color{blue}\quad \boxed{\phantom 0}} \\ {\color{green}\boxed{\phantom 0} \quad \boxed{\phantom 0} }\quad 4 \quad {\color{blue}\boxed{\phantom 0} }\\ {\color{green}\boxed{\phantom 0} \quad \boxed{\phantom 0} \quad \boxed{\phantom 0}} \quad 4 \quad {\color{blue}\boxed{\phantom 0}} \\ {\color{green}\boxed{\phantom 0} \quad \boxed{\phantom 0} \quad \boxed{\phantom 0}} \quad 4 \quad {\color{blue}\boxed{\phantom 0} \quad \boxed{\phantom 0}}\\ {\color{green}\boxed{\phantom 0} \quad \boxed{\phantom 0} \quad \boxed{\phantom 0} \quad \boxed{\phantom 0}} \quad 4 {\color{blue}\quad \boxed{\phantom 0} \quad \boxed{\phantom 0}} \\ \text{図3} \end{array} $$
さて、このとき、$c$の右側にある数字が書かれたマスの集合を$S$(青色),左側にある数字が書かれたマスの集合を$T$(緑色)とする。また、上から$k$行目にある$S,T$の要素の個数をそれぞれ$s,t$とする。

このとき、$S\cup T=\{マス全体-cが書かれたマス\},S\cap T=\emptyset $であることに注意する。
今、$S$に注目する。上から$i+1$行目と$i$行目に書かれた$S$に含まれるマスの個数の差は$0$または$1$である。差が$0$の所は$i+1$行目と$i$行目の構成が不変である(より厳密には2つの行の左から$j$番目の$S$に含まれるマスに書かれた数が等しい)。
更に、$S,T$の要素$p,q$(共に同じ行にある)であって、$p$が$q$の左にあったとすると、それより下の行でも$p,q$に書かれた数字$p',q'$は$p'$が$q'$の左にあり続けるから、矛盾が生じる。

従って、差が$0$の部分を無視すると、これは$n=s$のケースと同様であるため、$S$に数を一意に書き込むためには少なくとも$f(s)$個の良いマスが存在することになる。同様に、$T$に数を一意に書き込むためには$f(t)$個良いマスが必要である。
ここで、次の場合分けをする。

・良いマスにかかれている数字が全て異なる
・ある$2$つの良いマスであって、書かれている数字$d$が等しいものが存在する。

1つ目のケースにおいて、
$m\geq f(s)+f(t)+1=[\frac 23s]+[\frac23t]+1$である。
今、$f(k)\geq f(k-1)=[\frac23(k-1)]>\frac13k$に注意すれば、$s$を$3$で割ったあまりは$2$通り以上あり得るから、そのうちの適切な方を良いマスを適切に選ぶことで選べば、($s+t=k-1$などに注意して)
$m\geq [\frac23s]+[\frac23t]+1=[\frac23(k-1)]+1\geq [\frac23k] \quad (k\equiv 0,2 {\pmod3})$
$m\geq [\frac23s]+[\frac23t]+1=[\frac23(k-1)]=[\frac23k]\quad \quad \quad (k\equiv1\pmod 3)$
となる。
2つ目のケースにおいて、
$c=d$とすれば、
$m\geq [\frac23s]+[\frac23t]+2\geq[\frac23]+1\geq [\frac 23k]$
となる。

よって、いずれのケースにおいても、$m\geq[\frac23k]$であるから、$f(k)=[\frac23k]$となる。よって示された。