Problem 415 「タイタニック集合」

格子点の集合 S について, そのうちの2点のみを通る直線が存在するとき, その S をタイタニック集合と呼ぼう.

例えば以下の集合はタイタニック集合である, S = {(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)}, ここで (0, 1) と (2, 0) を通る直線は S の他の点を通ることがない.

一方, 集合 {(0, 0), (1, 1), (2, 2), (4, 4)} はタイタニック集合ではない, なぜなら集合内のいかなる2つの点を通る直線も他の2つの点を通るからである.

ある正の整数 N に対して, 0 ≤ x, yN を満たすすべての点 (x, y) におけるタイタニック集合 S の数を T(N) としよう. T(1) = 11, T(2) = 494, T(4) = 33554178, T(111) mod 10&sup{8}; = 13500401, そして T(10&sup{5};) mod 10&sup{8}; = 63259062 であることが確かめられている.

T(10&sup{11};) mod 10&sup{8}; を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-17 (日) 23:42:28