フィボナッチ数列は再帰的な関係によって定義される:

$F_n = F_{n−1} + F_{n−2}$

$F_{541}$ (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. そして, $F_{2749}$ (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

$F_k$が, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき,$k$を求めよ.

数列の$k$個の項を与えられたときに, 次の項を確実に求めることは不可能である. その数列に合うような多項式が無限個存在するからである.

例として, 立方数の数列を考えよう. これは生成関数$u_n = n^3$で定義され, 1, 8, 27, 64, 125, 216, ...となる.

この数列の最初の2項のみが与えられているとしよう. "Simple is best"の法則にのっとり, 線形の関係があると仮定し, 3つ目の項が15であると予想する (差分が7). もし最初の3項のみが与えられていたとしても, 同じ原則により, 二次の関係があると仮定して次の項を予測する.

数列の最初の$k$項を生成できる最適な多項式の第$n$項を$\textrm{OP}(k, n)$で表すことにする. 明らかに,$n ≤ k$について$\textrm{OP}(k, n)$は正しい. 最初の異なる項 (First Incorrect Term, FIT) は$\textrm{OP}(k, k+1)$であろう. これを bad OP (BOP) と呼ぶことにする.

原則より, 最初の項しか与えられていない場合には, 定数項とするのが理に適っているだろう; 即ち,$n ≥ 2, \textrm{OP}(1, n) = u_1$.

従って, 立方数の数列について以下のOPを得る.

(BOPを赤くする)

明らかに,$k ≥ 4$のときにはBOPは存在しない.

BOPのFIT (上の例では赤で示されている) の和は,$1 + 15 + 58 = 74$である.

以下の10次多項式からなる生成関数を考える:

$u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}$

BOPのFITの総和を求めよ.

大きさの集合の要素の和をで表す. 空でなく共通要素を持たないいかなる 2 つの部分集合とに対しても以下の性質が真であれば,を特殊和集合と呼ぼう.

1. ; つまり, 部分集合の和が等しくてはならない.

2. がより多くの要素を含んでいればこのときとなる.

たとえば, は,であるため特殊和集合ではないが,はすべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, またである.

7個から12個の要素を含む集合100個が記された 4K のテキストファイル (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合をすべて特定し,を求めよ.

注意: この問題はとに関連している.

大きさの集合の要素の和をで表す. 空でなく共通要素を持たないいかなる 2 つの部分集合とに対しても以下の性質が真であれば,を特殊和集合と呼ぼう.

1. ; つまり, 部分集合の和が等しくてはならない.

2. がより多くの要素を含んでいればこのときとなる.

本問題に対しては, 与えられた集合は個の単調増加する要素を含み, かつ第二のルールをすでに満たしているものと仮定しよう.

驚くべきことに,の集合から得ることができる 25 個の可能な部分集合の対のうち, 1 個の対のみが 同一性（第一のルール）をテストされる必要がある. 同様に,のときは, 966 個の部分集合の対のうち 70 個のみがテストされる必要がある.

に対して, 得られる 261625 個の部分集合の対のうち, 同一性をテストされる必要があるものは何個か.

注意: この問題はとに関連している.

以下の無向ネットワークは7つの頂点と重み付きの12個の辺からなり, 重みの総和は243である.

このネットワークを以下の行列で表現することができる.

しかし, このネットワークを, 全ての頂点が連結であるように適当な辺を除いた上で最適化することが出来る. 節約される量が最大化されるように取り除いたネットワークが以下の画像である. この場合, 辺の重みの総和は93であり, 元のネットワークからの節約量は 243 - 93 = 150 である.

6Kバイトのテキストファイルnetwork.txt (右クリックして保存すること) には40頂点のネットワークを行列表示したものが記されている. ネットワーク全体が連結であるが冗長な辺を取り除いたときの節約量を最大にするようにした場合の節約量を答えよ.

次の等式では正の整数である.

では 3 つの異なる解がある.

解の数が 1000 を超える最小のを求めよ.

注: この問題はの易しいケースである. こちらを先に解く事を強く勧める.

3つの異なる点が$-1000 ≤ x, y ≤ 1000$かつ三角形となるように, デカルト平面上にランダムに与えられる.

以下の2つの三角形を考える.

• $A(-340,495), B(-153,-910), C(835,-947)$

• $X(-175,41), Y(-421,-714), Z(574,-645)$

三角形$ABC$が原点を内部に含み, $XYZ$は原点を内部に含まないことが確かめられる.

27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.

注: ファイル中の最初の二つは三角形ABC, XYZである.

次の等式で$x, y, n$は正の整数である.

$\displaystyle \frac{1}{x} + \frac{1}{y} = \frac{1}{n}$

$n = 1260$では 113 の異なる解があり, この$n$が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は問題108を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.

ダーツゲームでは, プレイヤーは 20 等分に分けられたダーツボードに 3 本のダーツを投げる. ダーツボードは 1 から 20 の番号がふられている.

ダーツの点数は, ダーツが刺さった領域の番号によって決まる. 外側の赤緑の輪の外に刺さったダーツは 0 点である. この輪の内側の黒と白の領域はシングル (1 倍) の点数を表している. しかし, 外側と内側の赤緑の輪はそれぞれダブル (2 倍) とトリプル (3 倍) の点数である.

ボードの中央の 2 つの同心円はブルやブルズアイと呼ばれる. 外側のブルは 25 点, 内側のブルはダブルの 50 点である.

ルールには多くのバリエーションがあるが, 最もポピュラーなゲームでは, プレイヤーは 301 または 501 点から始まり, 最も早く現在の得点を 0 点に減らしたプレイヤーが勝者となる. しかし, 普通は「ダブルアウト」方式でプレイをする. この方式では, プレイヤーは勝利するために, 最後のダーツをダブル (ボードの中央のダブルのブルズアイを含む) に刺さなければならない. それ以外で現在の得点を 1 点以下に減らした場合, 3 本のダーツに対する得点は「バースト(無効)」になる.

プレイヤーが現在の得点で終了できる場合を「チェックアウト」と呼ぶ. 最も高いチェックアウトは 170: T20 T20 D25 (トリプルの 20 を 2 回とダブルのブル) である.

得点が 6 でチェックアウトする異なるやり方はちょうど 11 通りある.

D1 D2 と D2 D1 は, 異なるダブルで終了しているので異なるとみなすことに注意しよう. しかし S1 T1 D1 の組み合わせは T1 S1 D1 と同じとみなす.

さらに, 組み合わせを考える上でミスは含まないこととする; たとえば, D3 は 0 D3 や 0 0 D3 と同じである.

信じられないことに, 異なるチェックアウトは全部で 42336 通りある.

得点が 100 未満の異なるチェックアウトは何通りあるか.

大きさ$n$の集合$A$の要素の和を$S(A)$で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合$B$と$C$に対しても以下の性質が真であれば,$A$を特殊和集合と呼ぼう.

1. $S(B) ≠ S(C)$; つまり, 部分集合の和が等しくてはならない.

2. $B$が$C$より多くの要素を含んでいればこのとき$S(B) > S(C)$となる.

ある$n$に対し$S(A)$が最小化されていれば, それを最適特殊和集合と呼ぼう. はじめの 5 つの最適特殊和集合は下に与えられる.

• $n = 1: \{1\}$

• $n = 2: \{1, 2\}$

• $n = 3: \{2, 3, 4\}$

• $n = 4: \{3, 5, 6, 7\}$

• $n = 5: \{6, 9, 11, 12, 13\}$

ある最適特殊和集合$A = \{a_1, a_2, \dots , a_n\}$に対し, 次の最適特殊和集合は$B = \{b, a_1+b, a_2+b, \dots ,a_n+b\}$となりそうである. ここで$b$は前列の「中央の」要素である.

この「法則」を用いると$n = 6$に対する最適特殊和集合は$A = \{11, 17, 20, 22, 23, 24\}$で, $S(A) = 117$と予期するだろう. しかしこれは, 最適に近い集合を与えるアルゴリズムを用いたにすぎないため, 最適特殊和集合とはならない.$n = 6$に対する最適特殊和集合は$A = \{11, 18, 19, 20, 22, 25\}$で,$S(A) = 115$である. これに対応する集合の文字列は 111819202225 である.

$A$を$n = 7$に対する最適特殊和集合とするとき, その集合の文字列を求めよ.

注意: この問題は問題105と問題106に関連している.