OMC040-F 解いてみた
はじめに
こんにちは. kkkaaaです. 私は今日, 暇なので, OMC040のコンテスト中に思いついたF問題の解法を思考過程と共に紹介します. 暇ならもっと別のことをやるべきでは
OMCのサイトは
こちら
OMC040-Fの問題ページは
こちら
問題
$N$を正整数とします. 数列 $\lbrace a_n\rbrace_{n=1,2,\cdots}$を
$$a_1=a_2=1,\ \ a_{n+2}=a_{n+1}+Na_{n}\ \ (n=1,2,\cdots)$$
で定めるとき, $a_n=p^m$なる合成数$n$, 素数$p$, $3$以上の整数 $m$ の組の個数を$f(N)$とします. このとき
$$f(1)+f(2)+\cdots+f\left(\dfrac{3^{12}-1}{2}\right)$$
を求めてください. ただし, いずれも小数第$4$位で四捨五入した値として, 以下が保証されます.
$$\log_{5}{3}\approx 0.683,\ \ \log_{7}{3}\approx 0.565,\ \ \log_{11}{3}\approx 0.458,\ \ \log_{13}{3}\approx 0.428$$
解答
ここからは私がコンテスト中に思いついた解答となります.
まず, $a_n$について実験します. $N$を決めて考えるのは性質が見えづらいように思うので, $a_n$を$N$の多項式として表します.
$$a_1=1$$
$$a_2=1$$
$$a_3=N+1$$
$$a_4=2N+1$$
$$a_5=N^2+3N+1$$
$$a_6=3N^2+4N+1=(3N+1)(N+1)$$
$$a_7=N^3+6N^2+5N+1$$
$$a_8=4N^3+10N^2+6N+1$$
$$a_9=N^4+10N^3+15N^2+7N+1$$
$a_6$が因数分解できることに注目します. $a_6=p^m$となる$(N,p,m)$を求めてみると, $3N+1$と$N+1$の最大公約数は$1$または$2$であるため, $(N,p,m)=(1,2,3)$となります. このように, 因数分解が可能な場合は最大公約数を利用して$(N,p,m)$を決定しやすいので, 因数分解ができるかどうかについても考えて実験します.
$$ \begin{eqnarray} a_8&=&4N^3+10N^2+6N+1\\ &=&(2N+1)(2N^2+4N+1) \end{eqnarray} $$
$$ \begin{eqnarray} a_9&=&N^4+10N^3+15N^2+7N+1\\ &=&(N+1)(N^3+9N^2+6N+1) \end{eqnarray} $$
この実験から, $i$が$j$の倍数なら$a_i$は$a_j$の倍数になりそうです.
$a_i\equiv ta_{i+j}$, $a_{i+1}\equiv ta_{i+j+1}$ならば$a_{i+2}\equiv ta_{i+j+2}$となるため, 合同式の法を$a_j$の約数$p^m$として考えると, 帰納的に$i$が$j$の倍数であることと$a_i$が$a_j$の倍数であることが同値であることが示されました.
よって, $a_k$が$p$の倍数となるような最小の正整数$k$をとると, $a_n=p^m$ならば$n$の正の約数$l$は$k$の倍数であるか, $a_l=1$です. $a_n$は広義単調増加なので, $n$の$1$,$2$でない正の約数は$k$の倍数です. $n$が偶数かどうかで場合分けして考えると, $q$を素数, $x$を正整数として$n=2q^x$または$n=q^x$となることがわかります. いずれの場合も$q=2$ならば$k=4$, $q$が奇素数ならば$k=q$です.
ここから数列$\left\lbrace\frac{a_{kn}}{a_k}\right\rbrace$について考えていきたいですが, この方針はあまり上手くできそうにないです. そのため, 数列$\lbrace a_{kn}\rbrace$を直接考察していきます.
$a_n$で$n$が$k$の倍数でないときを無視したいですし, $a_n$の関係を探してみます.
ここで, より一般に, $b_0=a$, $b_1=b$, $b_{n+2}=b_{n+1}+Nb_{n}$として数列$\lbrace b_n\rbrace$を考えます. 実験をするとこのようになります.
$$b_0=a$$
$$b_1=b$$
$$b_2=Na+b$$
$$b_3=Na+(N+1)b$$
$$b_4=(N^2+N)a+(2N+1)b$$
$$b_5=(2N^2+N)a+(N^2+3N+1)b$$
$$b_6=(N^3+3N^2+N)a+(3N^2+4N+1)b$$
このような数列$b_n$を設定した意図は, $a=a_i$, $b=a_{i+1}$とすると, $b_j=a_{i+j}$となるからです.
$b_n$は多項式$f_n,g_n$を用いて$b_n=f_n(N)a+g_n(N)b$と表せます.
$a_0=0$と自然に定義可能(漸化式を満たすように定義可能だということ)であることに留意して,
$a=0$, $b=1$を代入すると, $a_n=b_n=g_n(N)$.
$a=b=1$を代入すると, $a_{n+1}=b_n=f_n(N)+g_n(N)$.
よって, $f_n(N)=a_{n+1}-a_n$, $g_n(N)=a_n$であるため, $b_n=(a_{n+1}-a_n)a+a_nb$となります.
よって, $a=a_i$, $b=a_{i+1}$とすると, $$a_{i+j}=b_j=(a_{j+1}-a_j)a_i+a_ja_{i+1}$$となりました.
また, 以下の変形も便利そうな感じです.
$$
\begin{eqnarray}
a_{i+j+1}&=&(a_{j+2}-a_{j+1})a_i+a_{j+1}a_{i+1}\\
&=&Na_ia_j+a_{i+1}a_{j+1}
\end{eqnarray}
$$
これらを利用すると, $a_k$, $a_{k+1}$の値から$a_{nk}$, $a_{nk+1}$の値を考察することができそうです. $u=a_k$, $v=a_{k+1}$とおいて, $2$式それぞれに$i=nk$, $j=k$を代入して$a_{nk}$について実験してみます.
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
a_{(n+1)k}=(v-u)a_{nk}+ua_{nk+1}\\
a_{(n+1)k+1}=Nua_{nk}+va_{nk+1}
\end{array}
\right.
\end{eqnarray}
$$
$$ \begin{eqnarray} \left\{ \begin{array}{l} a_k=u \\ a_{k+1}=v \end{array} \right. \end{eqnarray} $$
$$ \begin{eqnarray} \left\{ \begin{array}{l} a_{2k}=2uv-u^2 \\ a_{2k+1}=v^2+Nu^2 \end{array} \right. \end{eqnarray} $$
$$ \begin{eqnarray} \left\{ \begin{array}{l} a_{3k}=3uv^2-3u^2v+(N+1)u^3 \\ a_{3k+1}=v^3+3Nu^2v-Nu^3 \end{array} \right. \end{eqnarray} $$
$u,v,N$の$3$変数だと随分見づらいし, 計算ミスもしそうなのでこの辺で止めましょう. $a_n=p^m$のとき$a_k$は$a_n$の約数だったので, $u$は$p$冪です. そこで, $\bmod{u^2}$で考えれば$N$が消えて, 良さそうです. ($a_{nk}$は$u$の倍数だから. )
帰納的に, $a_{nk}\equiv nuv^{n-1}\pmod{u^2}$, $a_{nk+1}\equiv v^n\pmod{u^2}$となることが容易にわかります.
ここからは, $n$の素因数が大きく影響しそうなので, 場合分けをしてから考えます.
- $n$が奇数のとき
上の議論から, 奇素数$q$を用いて$n=q^x$となり, $k=q$です.
$n$は合成数であるため, $n$は$q^2$の倍数であるため, $a_{q^2}$, $u$はいずれも$p$冪で, $a_{q^2}> a_{2q}>u^2$となるため, $a_{q^2}$は$u^2$の倍数です. よって, $qv^{q-1}$が$u$の倍数であることが必要で, $v$は$p$の倍数でないため, $q=p$, $a_p=p$です. $a_p=p$より, 簡単な不等式評価で, $(N,p)=(2,3),(1,5)$となるので, 後は個別撃破するだけです.
$(N,p)=(2,3)$のときは$a_9=171$は$3$冪でないため矛盾.
$(N,p)=(1,5)$のときは$a_{25}=75025$は$5$冪でないため矛盾.
(もしこれが$p$冪になったときは$u=a_{p^2}$, $v=a_{p^2+1}$などとして同様の議論をして決定させるつもりでした. ) - $n$が偶数のとき
上の議論から, 素数$q$を用いて$n=2q^x$となり, $k=q$または$k=4$です.
$n\neq4$のとき, $n$は$2k$の倍数であるため, $a_{2k}$, $k$はいずれも$p$冪で, $a_{2k}>u^2$となるため, $a_{2k}$は$u^2$の倍数です. よって, $2v$が$u$の倍数であることが必要で, $v$は$p$の倍数でないため, $p=2$, $u=2$です. よって, $(N,q)=(1,3)$で, このとき$a_6=8$, $a_9=34$より, $a_9$が$2$冪でないため$(N,n,p,m)=(1,6,2,3)$のみが適することがわかります.
$n=4$のとき, $a_4=2N+1$より, $N=\dfrac{p^m-1}{2}$となります.
後は数えるだけです.
$p=3$のとき$3\leq m\leq12$. 問題で与えられた値より$p=5$のとき$3\leq m\leq8$, $p=7$のとき$3\leq m\leq6$, $p=11,13$のとき$m=3,4,5$. $p=17,19,23$のとき$m=3,4$, $29\leq p\leq79$のとき$m=3$.
よって, これら$46$通りが適するため, 求める値は$46$でした.
おわりに
$i$が$j$の倍数であることと$a_i$が$a_j$の倍数であることが同値であることは$a_{i+j}=(a_{j+1}-a_j)a_i+a_ja_{i+1}$から示せますが, この記事ではコンテスト中に私が考えた順番を優先しました.
OMC公式の解説
の方が強い結果で, $(N,p)=(2,3),(1,5)$みたいな変なケースも一気に消せています.
この議論におよそ$70$分もかけてしまったので, E問題までで$2$位に$30$分弱の差をつけていても抜かされるのは当然といえば当然でしょう.
