今回扱うのはMMA Contest 021 E問題 No.3457 Fibo-shrinkです。問題文の一部と公式解説が間違っていると思うので、その解説をしてみます。

問題の概要

正確な問題文はこちらです。

フィボナッチ数列を$F_0,F_1,\ldots$と$0$-indexedで表します。

有理数に値を持つ何らかの価値が$1$日毎に更新されます。

$0$日目以前の価値は$0$です。

$1$日目の価値は$S$です。

次の日の価値は$K$以下の各非負整数$k$をわたる(現在の$k$日前の価値/$F_k$)の総和です。 $F_N$をmod $10007$で求めてください。

前置き

「$T$日目以前」と言った時に$T$日目を含む流儀と含まない流儀があり不明瞭ですが、最近AtCoderでも「$T$時$0$分以前」という表現で断りなく$T$時$0$分を含む立場を取っていた（AtCoder Weekday Contest 0004 Beta A - 出発までの準備）ので含む流儀で解釈しました。

「次の日の価値」の記述で「現在」がいつであっても適用されるのか（$0$日目でも適用されるのか否か）が不明瞭ですが、$0$日目でも適用されるとするとサンプルと矛盾するので「$1$以上の整数$t$を用いて$t$日目と表される任意の日」に対してのみ適用されると判断しました。

問題点1

問題文に

▼有理数 $X/Y$ の mod $10007$

$YP \equiv X \pmod{10007}$をみたす、$10007$未満の非負整数$P$を出力してください。$X/Y$に対してただひとつ存在します。

とあります。「有理数 $X/Y$ の mod $10007$」の定義を説明することが想定される箇所で定義ではなく出力方法について述べている点はさておき、ここで初出の$X/Y$に何の説明もないので任意の有理数の任意の分数表示（分子は整数で分母は$0$でない整数）だと解釈します。

するとこの文は間違っており、例えば有理数$10007^{-1}$の分数表示を$X = 1, Y = 10007$で与えると条件を満たす$P$は$1$つも存在しませんし、例えば有理数$1$の分数表示を$X=Y=10007$で与えると条件を満たす$P$は複数存在します。

出力について述べていることから察するに、未定義な$X/Y$には恐らく「後述する入力制約を満たす任意の入力に対する$N$日目の価値の既約分数表示を$X/Y$と置いた時」などの定義が本来あってそれを書き忘れたものだろうと推測します。

問題点2

公式解説には次の主張が定理として、出典なく引用されています。

$2$でも$5$でもない素数$p$について、$F_{p−(\frac{p}{5})}$のみが$p$の倍数である。ただし、添え字の$(\frac{p}{5})$はルジャンドル記号

数学で主張を引用する時、出典を述べるかまたは出典に辿り着けるようにするためのキーワード（定理名など）を述べることが多いです。これは単純にcreditの問題（業績の盗用に関する不正）を回避するためが１つの理由ですが、もう１つの理由は引用者自身と読者が出典を当たれるようにするためです。

出典を当たれるとどんな利点があるかと言うと、

1. その主張が存在するか（引用元の主張から改竄されていないか、つまり正しく引用できているか）
2. その主張の前提となる流儀が現文脈と一致しているか

などです。１つ目は言うまでもないですね。例えば本来課されている条件が抜け落ちたりしていれば気付くことができます。２つ目はややこしいですが、同じ記法に複数の流儀が存在する場合は正しく引用しても現文脈の流儀と反する流儀に従った主張を文字通りに読むと誤りになり得るので流儀の違いを明確にする必要があります。

さて、今回引用された主張には問題があります。「～のみが$p$の倍数である」という主張を正当化するには$2$点の論点があり、

1. 何の中でそれのみが$p$の倍数なのか
2. 実際にそれが$p$の倍数なのか

を気にする必要があります。１つ目は例えば「集合$\{F_{p−(\frac{p}{5})}\}$の中では$F_{p−(\frac{p}{5})}$のみ」ということなのか「非負整数$i$全体をわたる$F_i$の中では$F_{p−(\frac{p}{5})}$のみ」なのかで全く別の主張になります。数学の論文ではこのように曖昧な言明を割けるので、恐らく引用の際に主張の一部を落としてしまったのでしょう。

前者だとあまり意味のない言明になるので、後者の立場に立ってみましょうか。すると問題が生じます。例えば$p = 3$とするとこれは$2$でも$5$でもない素数となり、ルジャンドル記号は$(\frac{5}{p}) = -1$となります。従って$p - (\frac{5}{p}) = 3 - (-1) = 4$です。

一方で

\[ \begin{array}{rcl} F_0 & = & 1 \equiv 1 \pmod{3} \\
F_1 & = & 1 \equiv 1 \pmod{3} \\
F_2 & = & 2 \equiv 2 \pmod{3} \\
F_3 & = & 3 \equiv 0 \pmod{3} \\
F_4 & = & 5 \equiv 2 \pmod{3} \\
F_5 & = & 8 \equiv 2 \pmod{3} \\
F_6 & = & 13 \equiv 1 \pmod{3} \\
F_7 & = & 21 \equiv 0 \pmod{3} \\
F_8 & = & 34 \equiv 1 \pmod{3} \\
F_9 & = & 55 \equiv 1 \pmod{3} \end{array} \]

となることから、$F_4$でない$F_3$や$F_7$が$p$の倍数になってしまっています。

そもそも$F_4$自身が$p$の倍数でないという問題もあります。つまりこれは２つ目の論点自体もおかしいということです。

こういう時は引用元に戻れば原因が分かるものですが、それがないので推測するしかできません。例えば引用元と問題文でフィボナッチ数列の定義（$0$-indexedか否か）が違うことを確認し忘れたのかもしれません。

引用元がない場合も、証明を確認すれば誤りの原因が分かりますが、残念ながら公式解説には証明もありません。ただ一言「証明にはある程度の数論の知識が必要なので、生成AIに質問するなどしてください。」とだけあるので推測するしかできませんが、もしかしたら「ある程度の数論の知識」と述べられている部分に誤りがあるのかもしれません。例えばフィボナッチ数列を周期で打ち切ったものに関する命題とフィボナッチ数列そのものに関する命題を混同している、などかもしれません。

余談

★1.5埋めをしている人向けの余談です。公式ヘルプによると★1.5の目安の１つは「高校数学１年程度の知識（和の公式など）」ですが、この問題は「証明にはある程度の数論の知識が必要なので、生成AIに質問するなど」が想定されている問題です。

実際に高校数学１年程度の知識で解くには、数論の知識を使う代わりにフィボナッチ数列を（提出コードとは別のコードでローカルに）法$10007$で$F_{500}$まで（つまりこの問題で実際に使われる長さまで）計算して確認してみると良いですね。提出コードとは別のコードをローカルで実行してみる際は実行時間を気にしなくて良いので、必要ならば自分に合ったエラー出力なども入れてみると良いです。

それはそうと同じく公式ヘルプによると「1e9+7を使う問題（割り算以外）」もまた★1.5の目安です。今回は1e9+7ではなく1e4+7ですが割り算が要求されており、これまでの学習では出会わなかった単元だと思います。割り算の方法は公式解説に書いてありますので、整数としての割り算と混同しないように気をつけて学習していきましょう。

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。