2009年6月22日

A. 笑わない数学者の問題

まだ確定していない予想はここに書く。

3. 笑わない数学者の問題
2. 笑わない数学者の問題
笑わない数学者の問題

なんとなく見えてきた。これは Pn が問題児なんじゃない。

Pn を決めると、 P3 から Pn-1 までの値の範囲が決定する ( P1 と P2 は固定なので影響しない )。特に Pn-1 の値の範囲には強い影響力がある。

また、 Pn = ( n*(n-1)/2 - x ) の 「x の値」が大事。x の値に応じて、同じ Pnに対して、 2x 組のパターンが発生する。

で、x が決まったときに Pn の周りにどのように数字を配置できるのかを突き詰めていくと、x ごとに有効な n の範囲が出てくる。また、その n が成り立つための拘束条件も出てきて、Pn周りのボールの何個かが確定する。そこから先は n ごとの探索になるが、ここまでは「nとは関係なく」求められる。そういう問題なのだろう。

だから 「n を与えられたときに解を求める」という探索戦略を使うと、いったん x の範囲を求めることになり、その後各 x について解を探すことになるが、これは「与えられた n 以外についての解」を大量に探索することになる。その次の n を与えるとこれまた同じような x の範囲について同じような探索をする必要があり…ここが大量に存在する重複した計算部分なのだろう。これは x ごとに n を求めた look up table をまず用意して、次に n ごとにその lookup table を探索するべきなんだ。