代数学の問題なんですが．．．

質問

-------------------
区間[0, 1]において，
１．区間内の適当な所に点（・）を書く．
２．[0, 1]の区間を２等分し，各々の区間に点がはいるような点を１つ書く．
（ただし，１で書いた点はそのままなので，点の無い方の区間に書く）
３．[0, 1]の区間を３等分し，点の無い区間に１つだけ点を書く．
．．．．．
．．．．．
１７．[0, 1]の区間を１７等分し，点の無い区間に１つだけ点を書く．

（例）
| . | . |
0.0 0.25 0.5 0.75 1.0

↓↓↓↓↓↓↓↓（２等分から３等分）

| . | . | . |
0.0 0.25 0.52 0.75 1.0

上の様なことを区間が１７等分まで繰り返して下さい．
--------------------

以上のようにして，区間を１７等分までしたときに適当な点の値を答えろ
という問題がありました，どうしても分からなかったのでだれか，解答
できる人がいましたら，是非値を教えて欲しいのですが．
また，条件がもう１つありまして，区間の境界上には点は書いてはいけない
ようになっています．

詳しい解説なんかも書いてもらえるとともてもありがたいです．
宜しくお願いします．

回答No.6

stomachman

どういう数列が解になるのか。何かヒントになればと思ってupします。

[1] 準備
　96個の既約分数(n/m) （0≦n＜m, 1≦m≦17）を小さい順に並べた列をr(i) (i=1,2,...,96) とします。さらに
V(i,j) = [r(i) j ]　　（[x]はxを越えない最大の整数）
とします。
　とりあえずV(i,j)の表をExcelか何かで作ってみてくださいな。（[x]はExcelでは=INT(x)です。）
　さて、|r(i)-r(i+1)|の最小値は約1/300です。そこで、適当な定数ε（0＜ε≪1/300）を決めれば、解のひとつは列 r(c(n))+ε (n=1,2,.....,17) で表すことができます。
　従って単に番号c(n)(n=1,2,.....,17) だけ示せば、具体的な数列が決まります。たとえばNo.4の解はc(n)の形で書くと
1 52 83 26 69 41 92 13 60 33 75 20 48 96 4 64 34
となります。

[2]色塗りの原理
　そこで、まずn=1を見ますと、c(1)=1なので、V(1,j) (j=1,2,....,17)のマス目一行分のマス目を例えば赤で塗ります。
　n>1については、c(n)はどの列jについても、j≧nならV(1,j)≠V(c(n),j)でなくてはなりません。そこでV(i,j)の表のうち、選べない領域を同じ色（赤）で塗ってみましょう。するとこの場合、V(1,1)～V(96,1)の一列全部、V(1,2)～V(48,2)、V(1,3)～V(32,3)、… V(1,16)～V(2,16)、V(1,17)が全部赤に塗られることになります。

　n=2を見ると、c(2)=52ですから、V(52,j) (j=2,3,.....,17)のマス目を例えば青で塗ります。さらにj=2,3,....,17について、V(52,j)と同じ値を持つマス目V(i,j)を青で塗ります。色を塗る部分は赤くない。これはつまり、V(52,j) ≠V(1,j) (j=2,3,.....,17)になっているという意味です。
　このようにして色を塗っていくと、V(i,j)の表のあらゆるマス目に全部色が付きます。これは、「0～1の範囲をj等分したとき、どの区画にも１個の点が入る」という条件と同じ意味です。

[3] VOIDについて
　解を探す上でポイントになるアイデアとして、"VOID"というものを考えました。（この概念なしにプログラムを作っても遅くてたまらない。）
　解ではない列c'(n) (n=1,2,....,17)について色を塗っていくと、
(1) 既に色を塗ってある所に塗り重ねてしまう。
(2) 島状に色の塗ってない部分（VOID）ができる。
などが生じます。
　ここでVOIDというのは、色が塗ってなくて、しかも周囲が色が塗られたマス目で囲まれている部分です。(2)が生じると後はどうやっても(1)が起こるので、(2)を検出すれば探索を早く打ち切ることができる。

　そこで、プログラムを作る際には以下のようにしました。
(1) c(n)をn=1,2,....,17の順に決めていく。
(2) 既に色が塗ってある所にはc(n)を置かない。
(3) c(n)を仮に置いてみて、VOIDが発生したら、そこには置かない。
(4) c(n)が上記(2)(3)の条件をクリアしたら、c(n+1)の置き場所を探す。
(5) c(n)を置く所がなくなったら、c(n-1)を置くところからやり直す。（バックトラック）
(6) c(17)を置けたら、解が見つかった。解を記録し、c(16)を置くところからやり直す。（バックトラック）

[4] 結果の性質
　このやりかたで、全部で70万9632個の解が見つかりました。
これは鏡像を含んだ数です。鏡像とは、すなわち
c(n)(n=1,2,...,17) 　を　97-c(n)　(n=1,2,...,17)　に置き換える操作のことです。（一方が解（r(c(n))+ε）なら他方（r(c(n))-ε）も解であることは自明。）

これらをc(1)の値で分類しますと、
c(1)=1のものが　 94688個　（r(c(1))=0）
c(1)=4のものが　 2464個　（r(c(1))=1/15）
c(1)=5のものが　 6336個　（r(c(1))=1/14）
c(1)=7のものが　 9856個　（r(c(1))=1/12）
c(1)=13のものが　19712個　（r(c(1))=2/15）
c(1)=14のものが　44352個　（r(c(1))=1/7）
c(1)=26のものが　44352個　（r(c(1))=4/15）
c(1)=28のものが　44352個　（r(c(1))=2/7）
c(1)=41のものが　44352個　（r(c(1))=5/12）
c(1)=45のものが　44352個　（r(c(1))=5/11）
c(1)=52のものが　44352個　（r(c(1))=7/13）
c(1)=56のものが　44352個　（r(c(1))=4/7）
c(1)=69のものが　44352個　（r(c(1))=12/17）
c(1)=71のものが　44352個　（r(c(1))=8/11）
c(1)=83のものが　44352個　（r(c(1))=11/13）
c(1)=84のものが　19712個　（r(c(1))=6/7）
c(1)=90のものが　 9856個　（r(c(1))=10/11）
c(1)=92のものが　 6336個　（r(c(1))=12/13）
c(1)=93のものが　 2464個　（r(c(1))=13/14）
c(1)=96のものが　94688個　（r(c(1))=16/17）
です。他の番号はc(1)にはなり得ない。
また、c(1)=14～83は解の数が全て同じであることは興味深いですね。

一例として、c(1)=45のもののc(1)～c(17)を並べてみますと、全て
45 a b c 28 56 d e 37 f g h 49 i j k h
というパターンです。ここで、
a∈{71,84,90,93,96}
b∈{1,5,14}
c∈{71,84,90,93,96}
d∈{1,5,14}
e∈{81,84,93,96}
f∈{63,64}
g∈{21,22}
h∈{77,87,88,89,90,96}
i∈{1,5,6,7,9,10}
j∈{74,75,76,77,87,88,89,90,91,92,93,96}
k∈{32,33}
h∈{58,59,60,61,62,63,64,65,66,67,68}
である。ごく限られた番号の組み合わせであることが分かります。

う～ん。やっぱりプログラムをシェアしなくては無理かなあ。