PLM解説(問24)

前書き

この記事はPLM解説の7/8番目の記事です！
他の問題の解説を見る場合は以下のリンクから飛んでください！
(まだ上がってないところがあります)

• PILAME杯問題解説-序盤編(1~10問目)[未完成]
• PILAME杯問題解説-中盤編(11~15問目)[未完成]
• PILAME杯問題解説-中～終盤編(16~20問目)[未完成]
• PILAME杯問題解説-ボス問編1(21問目)[未完成]
• PILAME杯問題解説-ボス問編2(22問目)[未完成]
• PILAME杯問題解説-ボス問編3(23問目)[未完成]
• PILAME杯問題解説-ボス問編4(24問目)[本記事]
• PILAME杯問題解説-ボス問編5(25問目)[未完成]

終盤のボス問ラッシュ第四問目です！
正直この辺の問題を解く余裕があるなら本選進出は余裕だと思います.(JMO本戦11,12みたいなノリだと)

運営の方に聞いてみたところこの問題の正解者はいなかったらしいです. ほかのボスと比べて簡単に見えてたので意外でしたね～.

問題24

問題の難易度:OMC600700点程度 黄diff(2200) (無印のボスっぽい)

解く際に考えたこと

パッと見た感じ漸化式は$a_1\cdot a_2 \cdots a_n$の部分を前の項の式で置き換えられるかな～みたいな印象を受ける．

実際に置き換えてみると$ a_{n+1} =a_n(a_n+2)-2 $となりますが，この状態から得られる情報が少ないので，平方完成してみると$a_{n+1}+1=(a_n+1)^2-2$という形になるので,典型に従って$a_n=a^{2^n}+a^{-2^n}$の形になることが推測できる．
(この典型は OMC242(F) や HLMC002(H) などでも使えます.二乗の形が出てくると大体$a_n=k(a^{2^n}+a^{-2^n})$の形でおけまることを意識するとよいでしょう.)

$a_n$を先ほどのように置くと,以下の式が成り立つ.$$a^{2^{12}}+a^{-2^{12}}=16 ,\ a+a^{-1}=\alpha-1$$
この式で注目したいところは$a+a^{-1}=\alpha-1$なっていることで,右辺が答えの形と類似することに気づける.
このとき解法の候補として思いついたものとして,

• $a$を求めて計算する.
• うまく式変形して$(a+a^{-1})^{5000}$を$a^{2^{12}}+a^{-2^{12}}=16$で表す.

というものが考えられます.後者は$5000$と$2^{12}$の関係性がなさ過ぎたので無理だと判断し,前者で進めてみることとした.

このとき,$x^{2^{12}}=1$となる$\omega$を取ることで簡単に解が表せます.これの性質として$\omega^{nk}(0\leq k <2^{12})$の和が$n=2^{12}m$でないと$0$となるので,$5000$乗を二項定理でばらして$\omega$の方の和を取れば結構式が簡単になることがわかる.

解法

$n\geq3$のとき，$a_n+2=a_1\times a_2\times \cdots \times a_{n-1}$より，
\begin{align*} a_{n+1} &=a_1\times a_2\times \cdots \times a_{n-1}\times a_n - 2 \\ a_{n+1} &=a_n(a_n+2)-2\\ a_{n+1}+1&=(a_n+1)^2-2 \ (n\geq3) \ \cdots(\ast) \end{align*}
このとき，$b_n=a_n+1 =a^{2^{(n-3)}}+a^{-2^{(n-3)}}$とすると，$(\ast)$ の漸化式を満たす．
また，$b_n=a_{15}+1=16,\ b_3=a_3+1=a_1\times a_2-1=\alpha -1$なので，
\begin{align*} a^{2^{12}}+a^{-2^{12}}&=16\\ (a^{2^{12}})^2-16a^{2^{12}}+1&=0 \end{align*}
この式を満たす $a^{2^{12}}$ の値を$A,B$ とし，$x^{2^{12}}=1$ を満たす数 $x(\neq 0)$を$ \omega$ とすると，
$$A+B=16,AB=1,a+a^{-1}=\sqrt[2^{12}]{A} \ \omega ^k + \sqrt[2^{12}]{B} \ \omega ^{-k}\ (k=0,1,\cdots,2^{12}-1)$$
と表せる．このとき，$a+a^{-1}=\alpha-1$であるので, $(\alpha -1)^{5000}$ の取りうる数の和を $S$ とすると，
\begin{align*} S&=\sum_{k=0}^{2^{12}-1} ( \sqrt[2^{12}]{A} \ \omega ^k + \sqrt[2^{12}]{B} \ \omega ^{-k})^{5000}\\ &=\sum_{m=0}^{5000}(\sum_{k=0}^{2^{12}-1} {}_{5000} \mathrm{C}_m \omega^{k(5000-m)-km} \ A^{\frac{5000-m}{2^{12}}} \ B^{\frac{m}{2^{12}}})\\ &=\sum_{m=0}^{5000}(\sum_{k=0}^{2^{12}-1} {}_{5000} \mathrm{C}_m \omega^{(5000-2m)k} \ A^{\frac{5000-2m}{2^{12}}} ) \end{align*}
\begin{equation} \sum_{k=0}^{2^{12}-1} \omega^{(5000-2m)k}= \left\{ \begin{alignedat} {2} &\frac{\omega^{(5000-2m)2^{12}}-1}{\omega^{(5000-2m)}-1} \ = \ 0 \ &(\omega^{(5000-2m)}\neq 1) \\ &1\times 2^{12} \ &(\omega^{(5000-2m)}= 1) \end{alignedat} \right. \end{equation}
が成り立つので，
\begin{align*} S&=\sum_{m=0}^{5000}(\sum_{k=0}^{2^{12}-1} {}_{5000} \mathrm{C}_m \omega^{(5000-2m)k} \ A^{\frac{5000-m}{2^{12}}} \ B^{\frac{m}{2^{12}}})\\ &=2^{12}({}_{5000} \mathrm{C}_{452} A^{\frac{4096}{2^{12}}} + {}_{5000} \mathrm{C}_{2500} A^{\frac{0}{2^{12}}}+{}_{5000} \mathrm{C}_{4548} A^{\frac{-4096}{2^{12}}})\\ &=2^{12} {}_{5000} \mathrm{C}_{2500}+2^{12} {}_{5000} \mathrm{C}_{452}(A+A^{-1})\\ &=2^{12} {}_{5000} \mathrm{C}_{2500}+2^{16} {}_{5000} \mathrm{C}_{452} \end{align*}

解いた感想

なかなかの難問かつ面白い問題だったと思います.
特に最後の和の順番を入れ替える点がかなり面白く感じました.
この問題は大きく$a_n$を求める前半のフェーズと和を取る後半のフェーズに分けられると思います.
前半に関しては典型に従っていけば割と順当に解けると思います.
問題は後半部分で,このやり方が思い浮かんだとしても最後までの見通しがたってないと,うまくいくかがかなり怪しく感じるような解法なので,本番で回答するのは難しいと感じます.

小話ですが, この前のcamping001にてPLMの話題が上がり, この問題の話をしたところ,運営内ではOMC700点だと思われていたようなので, 本記事も訂正しました.
(camping001たのしかったな～)