ゼッケンドルフの定理と全探索

はじめに

友人と会話してて得られた知見で、共有したいと思います。

ゼッケンドルフの定理

ゼッケンドルフの定理は

任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できる

というものです。
これを使うと、全探索がオーダーレベルで効率良く行えることがあります。

全探索

たとえば、一般的にこういう問題を考えます。

\(N\) 個のデータが順序ついて並んでいて、その部分集合であって、ある性質を満たすものを求める。

もしこの「ある性質」が、連続する2つのデータを取り出すと成り立たないようなものであれば、ゼッケンドルフの定理からオーダーが改善できます。
（成り立たないは直接的ですが、最小化問題などのときに、2連続は考えなくてもよい、みたいな状況もありえそうです。）

\(N\) 個の点を \(N\) ビットで表現するとすると、連続2点をえらばないので、
これはゼッケンドルフ表現と捉えることができます。
このような選び方が自然数と一対一対応するので、例えば \(N \leq 40\) だとすると、大体 \(F_{40} = 10^8\) 程度の部分集合しかないことがわかります。
なので、全探索が間に合う（かもしれない）ということですね。

最後に

結局考えてた問題ではこの性質は使わずに解きました（というか、こんな性質はなかったので使えなかった、悲しい）。