0

2022JJMO5番の解説

251
0
$$\newcommand{Aut}[0]{\mathrm{Aut}} \newcommand{C}[0]{\mathbb{C}} \newcommand{char}[0]{{\bf char}} \newcommand{comp}[0]{\circ} \newcommand{core}[0]{\rm{core}} \newcommand{gen}[1]{\langle #1 \rangle} \newcommand{imply}[0]{\Rightarrow} \newcommand{iso}[0]{\simeq} \newcommand{lnormal}[0]{\triangleleft } \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{rnormal}[0]{\triangleright} \newcommand{semiprod}[3]{{#1}\ltimes_{#2}#3} \newcommand{Z}[0]{\mathbb{Z}} $$

問題は 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.

投稿日:2022212
更新日:20231114

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

bd
39
6382

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中