[追記] 問題文が修正されました. 現在公開されている問題は, 公式解説と整合しています.
元の問題文
実数列 {Fn} は以下の漸化式をみたすものとします：
F1=F2=1,Fn+2=Fn+1+Fn(n≥1).
いま, 正整数 p≤q に対し, Uq={1,2,…,q} とし, Uq を空でない p 個の集合に分割する方法（分割後の集合の順序は区別しない）であって，以下の条件をみたすものの個数を f(p,q) とおきます：
- 分割後の p 個の集合を S1,S2,…Sp としたとき,
k∈S1∑Fk=k∈S2∑Fk=⋯=k∈Sp∑Fk.
2≤p≤q≤100 をみたす正整数の組 (p,q) すべてに対し f(p,q) を求め, それらの総和を解答してください.
集合の分割について
p 個の集合 S1,S2,…Sp が以下の条件をみたすとき, 集合 Uq の 分割 であるといいます：
- 1≤i<j≤p ならば Si∩Sj=∅.
- S1∪S2∪⋯∪Sp=Uq
【公式解説誤りの指摘】
Uq を分割する方法は, 各要素が S1,S2,…,Sp のいずれに属するかで区別される (分割後の集合の順序は区別しない). そのため, F1=F2 であっても, 1∈S1,2∈S2 と 1∈S2,2∈S1 を区別して計上される.
公式解説では, 誤ってこれらを区別していないため, q=5,8,11,… のときの f(p,q) の値を本来の 21 倍として算出している.
公式解説の該当箇所
q=2,3,5 の分割の方法がいずれも 1 種類として数えられることに注意すれば,
f(2,q)=⎩⎪⎪⎨⎪⎪⎧123q−123q−2−1(q=2,3,5)(q=6,9,12,…)(q=8,11,14,…)
となる. 以上より, 求める値は以下のように計算できる：
2≤p≤q≤100∑f(p,q)=3+(2+22+⋯+231)+(2+22+⋯+232)=12884901887.
修正後
f(2,q)={23q−123q−2(q=3,6,9,…)(q=2,5,8,…)
となる. 以上より, 求める値は以下のように計算できる：
2≤p≤q≤100∑f(p,q)=2(20+21+⋯+232)=2(233−1)=17179869182.