2022JJMO5番の解説
問題は
https://www.imojp.org/archive/mo2022/jjmo2022/problems/jjmo20hq.html
を見てください.
$k\leq 3$のときは,全探索することで$n=2,4$のみが解なことが分かる.
以下$k\geq 4$とし,$n$が条件を満たすと仮定し矛盾を導く.
$a_i=\lfloor\frac{n}{2^i}\rfloor$,$a_i$を$2$で割った余りを$b_i$,$\mathrm{ord}_2(a_i)=c_i$,$X=a_0a_1\cdots a_k$,$Y=X+2\cdot 4^{\lfloor\frac{k}{2}\rfloor}$と置く.
$a_i \not\equiv 3,5\pmod 8,a_i\not\equiv 0\pmod 3$
$a_i \equiv 3,5\pmod 8$と仮定して矛盾を導く. このとき,$p\equiv 3,5\pmod 8$を満たす$a_i$の素因数$p$が存在する. この時,$Y\equiv 2\cdot 4^{\lfloor\frac{k}{2}\rfloor}\pmod p$なので,平方剰余の第2補充則に矛盾する.
$a_i \equiv 0\pmod 3$のときは上の議論で$p=3$とすればよい.
$b_i+b_{i+1}+b_{i+2}\leq 1$
主張は$a_i\equiv 0,1,2,4\pmod 8$と同値である.
$a_i\equiv 0,1,2,4\pmod 8$を$i=k$から順に示す.
$i=k$のときは$a_i=1$より自明. $i$のとき正しいとすると,$\lfloor\frac{a_{i-1}}{2}\rfloor=a_i$より,$a_{i-1}\equiv 0,1,2,3,4,5\pmod 8$. これと補題1をあわせれば$i-1$でも正しいことがわかる.
$c_i+c_{i+1}\geq 1,c_i+c_{i+1}+c_{i+2}\geq 3$
$c_i$は$0=b_i=b_{i-1}=\cdots=b_{i-j+1}$を満たす最大の$j$であることに注意せよ.
主張の前半は補題2より,$b_i$と$b_{i+1}$のどちらかは$0$であることから従う.
後半は$b_i=b_{i+1}=0$もしくは$b_{i+1}=b_{i+2}=0$のときには正しく,補題2より残るパターンは$b_i=b_{i+2}=0,b_{i+1}=1$のみである. このとき再び補題2を$i-1$に適用すれば$b_{i-1}=0$となり,$c_i\geq 2,c_{i+2}=1$となる.
$c_k+c_{k-1}+c_{k-2}+c_{k-3}=6$
$a_k=1$より$a_{k-1}=2,3$だが,補題2より$a_{k-1}=2$.
よって$a_{k-2}=4,5$だが補題2より$a_{k-2}=4$.
よって$a_{k-3}=8,9$だが補題2より$a_{k-3}=8$.
ゆえに$c_k=0,c_{k-1}=1,c_{k-2}=2,c_{k-3}=3$.
$k\equiv 0\pmod 3$なら
$\mathrm{ord}_2(X)\geq k+1$
$k\not\equiv 0\pmod 3$なら
$\mathrm{ord}_2(X)\geq 3\lceil \frac{k}{3}\rceil$
補題3,4から従う.
補題5から,(場合分けを頑張ると)$\mathrm{ord}_2(X)> 2\lfloor\frac{k}{2}\rfloor+1$がわかり,よって$\mathrm{ord}_2(Y)=2\lfloor\frac{k}{2}\rfloor+1$となる. これは$Y$が平方数であることに矛盾.
雑感:$2\cdot 4^{\lfloor\frac{k}{2}\rfloor}$に「絶対に平方数にさせないぞ」という意志を感じるので,それに従うととける. この方針では主に$\mod 8$と第2補充則を使ったが,$\mod {15}$だと補充則なしで解ける($a_i\equiv 1,2,4,8\pmod {15}$が帰納的にわかる). おそらくこっちが本解だろう. Nっぽいけど実質C.
