@Nabetani さんが出題していた「等比? 等差? フィボナッチ??」を解いてみました。
与えられた5つの部分数列が等比数列か等差数列か、はたまたフィボナッチ数列か(またはそれ以外か)を当てる問題でした。以下では、それぞれの判別方法について解説していきます。なお、第$i$項を$a_i$としています。
等比数列の判定
隣り合う項の比をとってやり、それが全て等しければ等比数列と判断できます。
比のままでは少し扱いづらいので、積の形に変形しています。
a_{i} : a_{i+1} = a_{i+1} : a_{i+2} \\
a_{i+1}a_{i+1} = a_{i}a_{i+2}
等差数列の判定
隣り合う項の差が全て等しければ等差数列と判断できます。これは特に説明は不要でしょう。
フィボナッチ数列の判定
これがこの問題のキモだったのではないでしょうか。フィボナッチ数列っぽくなってるかどうかは等式$a_{i+2}=a_{i+1}+a_{i}$が満たされていることを確認すればいいのですが、$a_i$、$a_{i+1}$($=A$とします)自体がフィボナッチ数ではない場合、いくら前述の等式が満たされているからといって、与えられた部分数列はフィボナッチ数列になり得ません。(追記:さらに、$a_i < a_{i+1}$かつ$a_{i+1} = a_{i-1}+a_{i} < a_i + a_i = 2a_i$、または$a_1=a_2=1$である必要もある。)
では、どうやって$a_i$がフィボナッチ数かを判断すればよいのでしょうか。結論から言うと、$5A^2 + 4$または$5A^2 - 4$が完全平方数(ルートをとってもなお整数であるような整数$:1,4,9,16,25,49,...$)であれば$A$はフィボナッチ数となります。
定理
$5A^2 \pm 4 = B^2 $ ならば $A$ は フィボナッチ数である。
証明
$5A^2 \pm 4 = B^2 $を次のように変形する。
\begin{eqnarray}
5A^2 \pm 4 = B^2 \\
B^2 - 5A^2 = \pm 4 \\
(B+\sqrt{5}A)(B-\sqrt{5}A)=\pm 4 \\
\left(\frac{B+\sqrt{5}A}{2}\right)\left(\frac{B-\sqrt{5}A}{2}\right)=\pm 1
\end{eqnarray}
ここで、整数$l$を用いて
\frac{B+\sqrt{5}A}{2} = \left(\frac{1+\sqrt{5}}{2}\right)^l \\
\frac{B-\sqrt{5}A}{2} = \left(\frac{1-\sqrt{5}}{2}\right)^l
と書けるので(参考[1]参照)、
\begin{eqnarray}
A = \frac{1}{\sqrt{5}}\left(\frac{B+\sqrt{5}A}{2} - \frac{B-\sqrt{5}A}{2} \right) \\
=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^l - \left(\frac{1-\sqrt{5}}{2}\right)^l \right) \\
= F_l
\end{eqnarray}
となり、$A$はフィボナッチ数$F_l$であることが分かる。$\blacksquare$
提出コード
提出コードはGolangで書きました。解答は特に晒すほどのものでもないので、リポジトリのリンクだけ載せておきます。