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

質問

-------------------
区間[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.9

stomachman · ベストアンサー

さらに、解の構造の分析その２。

●以下の区画は解には全く現れない。つまり、これらの区画内に点を置くことは出来ない。
{2,3,11,12,15,17,18,19,24,25,27,40,42,43,44,46,47,50,51,53,54,55,57,70,72,73,78,79,80,82,85,86,94,95}

●すなわち、以下の62個の区画だけが解に使われる。
{1,4,5,6,7,8,9,10,13,14,16,20,21,22,23,26,28,29,30,31,32,33,34,35,36,37,38,39,41,45,48,49,52,56,58,59,60,61,62,63,64,65,66,67,68,69,71,74,75,76,77,81,83,84,87,88,89,90,91,92,93,96}

●全ての解を通して、c(n)が取りうる値（区画の番号）は以下のように限定されている。
c(1)∈{1,4,5,7,13,14,26,28,41,45,52,56,69,71,83,84,90,92,93,96}
c(2)∈{1,4,5,7,13,14,26,28,41,45,52,56,69,71,83,84,90,92,93,96}
c(3)∈{1,4,5,7,13,14,41,45,52,56,83,84,90,92,93,96}
c(4)∈{1,4,5,7,13,14,26,28,69,71,83,84,90,92,93,96}
c(5)∈{26,28,69,71}
c(6)∈{41,45,52,56}
c(7)∈{1,5,14,83,92,96}
c(8)∈{1,4,13,16,81,84,93,96}
c(9)∈{37,60}
c(10)∈{33,34,63,64}
c(11)∈{21,22,75,76}
c(12)∈{1,7,8,9,10,20,77,87,88,89,90,96}
c(13)∈{48,49}
c(14)∈{1,5,6,7,8,9,10,87,88,89,90,91,92,96}
c(15)∈{1,4,5,6,7,8,9,10,20,21,22,23,74,75,76,77,87,88,89,90,91,92,93,96}
c(16)∈{32,33,64,65}
c(17)∈{29,30,31,32,33,34,35,36,37,38,39,58,59,60,61,62,63,64,65,66,67,68}
　幾つかの特徴を挙げると、
・c(1)とc(2)は取りうる値の集合が同じ。この集合をAとすると
　c(3)、c(4)、c(5)、c(6)、c(7)の取りうる値の集合⊂A
・c(15)の取りうる値の集合をBとすると、c(11)、c(12)、c(14)の取りうる値の集合⊂B
・c(17)の取りうる値の集合をCとすると、c(9)、c(10)、c(16)の取りうる値の集合⊂C
・{48,49}はc(13)以外には現れず、c(13)はこれらの値しか取らない。
・{16,81}はc(8)以外には現れない。
・{23,74}はc(15)以外には現れない。
・{29,30,31,35,36,38,39,58,59,61,62,66,67,68}はc(17)以外には現れない。
（なお、対称性から、c(n)がpという値を取りうるのなら、c(n)はまた97-pをも取りうることは自明です。）

●念のため、区画の番号とその範囲の下界との対応を示します。
例えば区画の番号＝3と言えば、{x|r(3)＜x＜r(4)}という範囲を指している。
r(1) = 0
r(2) = 1/17
r(3) = 1/16
r(4) = 1/15
r(5) = 1/14
r(6) = 1/13
r(7) = 1/12
r(8) = 1/11
r(9) = 1/10
r(10) = 1/9
r(11) = 2/17
r(12) = 1/8
r(13) = 2/15
r(14) = 1/7
r(15) = 2/13
r(16) = 1/6
r(17) = 3/17
r(18) = 2/11
r(19) = 3/16
r(20) = 1/5
r(21) = 3/14
r(22) = 2/9
r(23) = 3/13
r(24) = 4/17
r(25) = 1/4
r(26) = 4/15
r(27) = 3/11
r(28) = 2/7
r(29) = 5/17
r(30) = 3/10
r(31) = 4/13
r(32) = 5/16
r(33) = 1/3
r(34) = 6/17
r(35) = 5/14
r(36) = 4/11
r(37) = 3/8
r(38) = 5/13
r(39) = 2/5
r(40) = 7/17
r(41) = 5/12
r(42) = 3/7
r(43) = 7/16
r(44) = 4/9
r(45) = 5/11
r(46) = 6/13
r(47) = 7/15
r(48) = 8/17
r(49) = 1/2
r(50) = 9/17
r(51) = 8/15
r(52) = 7/13
r(53) = 6/11
r(54) = 5/9
r(55) = 9/16
r(56) = 4/7
r(57) = 7/12
r(58) = 10/17
r(59) = 3/5
r(60) = 8/13
r(61) = 5/8
r(62) = 7/11
r(63) = 9/14
r(64) = 11/17
r(65) = 2/3
r(66) = 11/16
r(67) = 9/13
r(68) = 7/10
r(69) = 12/17
r(70) = 5/7
r(71) = 8/11
r(72) = 11/15
r(73) = 3/4
r(74) = 13/17
r(75) = 10/13
r(76) = 7/9
r(77) = 11/14
r(78) = 4/5
r(79) = 13/16
r(80) = 9/11
r(81) = 14/17
r(82) = 5/6
r(83) = 11/13
r(84) = 6/7
r(85) = 13/15
r(86) = 7/8
r(87) = 15/17
r(88) = 8/9
r(89) = 9/10
r(90) = 10/11
r(91) = 11/12
r(92) = 12/13
r(93) = 13/14
r(94) = 14/15
r(95) = 15/16
r(96) = 16/17
r(97) = 1

回答No.8

stomachman

今度は、
一番要素の数が少ない、c(1)=4　で始まる解の集合の構造を調べてみましたよ。
●分類
・定数なのは
c(1)=4
c(8)=13
c(9)=60
c(12)=20
c(13)=48
c(15)=1
ここまでは選択の余地なしです。
・以下の番号は任意に選ぶことができます。
c(11)∈{75,76}
c(16)∈{64,65}
c(10)∈{33,34}
c(14)∈{87,88,89,90,91,92,96}
c(5)∈{26,69}
・以下は他の番号の影響を受けます。
c(17)∈ if c(10)=34 then {29,30,31,32,33} else {34,35,36,37,38,39}
c(7)∈if c(14)=96 then {92,83} else {96,83}
c(6)=if c(5)=26 then 52 else 41
　　さらに以下のものは他にも整理の仕方があると思いますが、
c(3)∈if c(5)=26 then {41} else
　　　　　(if c(14)=96 then {83,52,92} else {83,52,96})
c(4)∈if c(5)=69 then {26} else
　　　　　(if c(14)=96 then {83,69,92} else {83,69,96})
c(2)∈if (c(3)=52 or c(4)=69) then
　　　　　(if c(14)=96 then {83,92} else {83,96})
　　　else
　　　　　(ifc(5)=69 then {52} else {69})
以上です。

●ところで、
c(11)∈{75,76}
c(16)∈{64,65}
c(14)∈{87,88,89,90,91,92}∪{96}
c(17)∈ if c(10)=34 then {29,30,31,32,33} else {34,35,36,37,38,39}
これら、引き続いた値の部分は、要するに区別する必要がない一つの連続した区間と考えることができます。
つまり
c(11)=(75～76)
c(16)=(64～65)
c(14)∈{(87～92), 96}
c(17)∈ if c(10)=34 then (29～33) else (34～39)
という風に考えて良い。ですから特に、c(11),c(16)は実質的には定数と同じです。
　かくて、定数（および、c(11),c(16)）と、
・c(2),c(3),c(4),c(5),c(6)の４通りのパターン
a) 69 41 ** 26 52
b) ** 41 69 26 52
c) 52 ** 26 69 41
d) ** 52 26 69 41
およびc(7)とc(17)の選択パターン４通り、これらの掛け算で、実質16通りということですね。
そのどれかに、任意に選べる他の番号の選択を組み合わせることで、全ての解が構成されます。

さて、これは一体何を意味しているのでしょう？
群だの環だの、代数構造がおでましになる予兆でしょうか？

回答No.7

stomachman

No.6　の鏡像の概念について、書き間違いがありましたので訂正します。

＞　（一方が解（r(c(n))+ε）なら他方（r(c(n))-ε）も解であることは自明。）

を次のように訂正。
＞（一方が解（r(c(n))+ε～r(c(n)+1)-ε）なら（r(97-c(n))+ε～r(97-c(n)+1)-ε）も解であることは自明。）

ただしr(97)=1とします。

これを分かりやすくするためには、あらかじめ
＞解のひとつは列 r(c(n))+ε (n=1,2,.....,17) で表すことができます。

という代わりに

＞解のひとつは範囲の列 （r(c(n))+ε～r(c(n)+1)-ε） (n=1,2,.....,17) で表すことができます。ここにε>0でε→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}
である。ごく限られた番号の組み合わせであることが分かります。

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

回答No.5

stomachman

No.4のやつは数列です。勿論１，２，３，…，１７分割の順ですよ。

プログラムは最初Visual Basicでちょいちょい、とやったらこれが思いのほか重くってですね、それで似てる言語のコンパイラは？って探したらFortranがありましたんで、そっちに書き換えて走らせました。（その際に再帰呼び出しrecursionをtail mergeという方法でループに変換しています。）

　ともあれ、力ずくじゃあ、数学の問題の答にはなってないでしょう。ここにupするのはどうかと思います。

回答No.4

stomachman

えっと、たとえば列：
0 7/13 11/13 4/15 12/17 5/12 12/13 2/15 8/13 1/3 10/13 1/5 8/17 16/17 1/15 11/17 6/17
（いや、丁度切れ目に来るのがお気に召さなければ、それぞれに1/1000位加えた物）というのは、題意を満たしているでしょうか？

　実はこれ、力ずくで探索した結果です。
　何をやったかと申しますと…

　「切れ目」に来るのは（n/m）（0≦n＜m, 1≦m≦17）という形の有理数だけです。そのうち、既約のものだけ数えますと、96個あります。
最後に１７分割したときに各区画に１個づつ入る訳ですから、この９６個（或いはそれにごく小さい値を加えた物）の中から１７個を、題意に合うように選べばよい。
　そういう条件で、深さ優先探索(search)をやるプログラムをちょいちょいと書いて走らせたんです。

　解はもの凄く沢山出たのですが、上記の例はその最初の物。
　これが題意を満たしているなら、解があることは確かめられたことになり、あとはどうエレガントに構成するか、という問題でして、oodaiko先生ってば宜しくお願いいたします。

お礼

回答ありがとうございます．
これからやってみようと思っていますが，17つの点が
それぞれ何分割した時に書いた点なのかまで教えてい
ただけると更に嬉しいのですが．．．
それとも既に左から並べてある値が最初，2等分，3等分
．．．という風になっているのでしょうか．

それからプログラムを作って解いていただいた様なので
すが，C 言語で書かれたのでしょうか？
だとしたらそのプログラムもここに掲載してくれると大
変助かります．

色々要求を書いてしまって申し訳ありませんが，よろし
かったらコメントしておいてください．

回答No.3

stomachman

B(x,m) = {t| 0≦t≦1} - {t| [mx]/m≦t＜ ([mx]+1)/m}
（ここに[]はガウスの記号、つまり[a]はaを越えない最大の整数）
と定義したとき、
最初の点x(1)は{t| 0≦t≦1}から選ぶ。k+1番目の点x(n+1)は
x(k+1)∈∩(j=1,...,k) （∩(m=k+1,...,17) B(x(j),m)）
から選ぶ。この途中のプロセスで右辺がφ（空集合）になったらダメ。
そのような列 x(1),x(2),....,x(17)を作れという問題だと思います。

これって、{t| 0≦t≦1} と言いながら実は高々{t|∃n(0≦n≦17! ∧ t=n/17!)}という有限集合から１７個の要素を選ぶ問題と考えて良いのは自明でしょうから、それで代数学の問題に帰着するのかな？

で、答えはですね。分かりません。

回答No.2

oodaiko

＞点が２つ入ってしまう区間ができてしまい
あーなるほど。私は漠然と
「このプロセスの各段階において点の無い区間はただ１つだけであり、その他の区間には必ず１つだけ点が含まれる」
という条件が自然に満たされるものだと思い込んでしまいましたが、それは正しくなかったですね。私が書いた
＞点の無い区間を選び（そのような区間はこのプロセスから考えて
＞１つしかあり得ませんが）
という文も間違いでした。f(^^;;

それで御質問の意味がわかりました。

つまり

このプロセスのすべての段階において、
「点の無い区間はただ１つだけであり、かつ（というよりこの条件を満たせば必然的にですが）その他の区間にはすべて１づつ点が含まれている」
という条件を満足するような（１７個の）点列の例を求めよ。

ということですね。

回答は今考え中ですが、他の回答者の方が私と同じ勘違いをされるといけないので（←そんな早とちりをするのは私だけか(^^;; とりあえず確認の意味でアップしました

回答No.1

oodaiko

問題の意味が不明です。

＞点の無い区間に１つだけ点を書く
＞区間の境界上には点は書いてはいけない
この２つの条件をいっしょにするとつまり
「点の無い区間を選び（そのような区間はこのプロセスから考えて
１つしかあり得ませんが）そこから
1/2,1/3,2/3,1/4,2/4,3/4,1/5,2/5,…,16/17
以外の任意の位置を１つ選んでそこに点を書く」
ということでよいのでしょうか

＞１７等分までしたときに適当な点の値を答えろ
「点の値」というのは[0,1]区間における点の座標という意味ですね。
「適当な点」とはどの点のことでしょうか
１.で最初に書いた点のことでしょうか。これは任意なので
答えようがないと思いますが。
（他の点にしても多少の制約があるとはいえ任意なので
「点の値」など答えようがありません）

「点の値」というのはまさか「点の個数」の意味ではないですよね。
（それなら１７しかありませんが）

文字数の制約のため内容を詳しく書けなかったのであれば
（補足欄にはいくらでも書けますので）問題のきちんとした記述をお願いします。

補足

内容不明で誠に申し訳ありませんでした。
私自身この問題の内容がまだしっかりと
把握できてないものでして・・・。

さて、捕捉ですが以下のような捕捉をさせ
て頂きます。

＞（略）
＞以外の任意の位置を１つ選んでそこに点を書く」ということでよいのでしょうか
はい、その通りです。

＞（略）
＞「点の値」など答えようがありません）
１．の最初の点から最後の１７等分したときの最後の１点まで
点の位置は境界上でなければ様々な組合せであると考えられ
るので，その中の１つでも分かりましたらお教えして頂きた
いのです．

例えば，最初の[0, 1] 区間の0.2 に点を書いたとします，それを
２等分しますと[0, 0.5] [0.5, 1.0] という区間に分かれるわけ
ですから，0.6 に点を書きます．
次に３等分すると [0, 0.333][0.333, 0.666][0.666, 1.000] と
なりますので（割り切れないのですが．．．）[0.666, 1.000]
区間内の 0.8 に点を書いて行く．．．

このようにして１７等分までしていって欲しいのです．
自分でも何回も挑戦したのですが，いつも途中で点の無い区間や
点が２つ入ってしまう区間ができてしまい失敗してしまいました．

というわけで，以上の捕捉で理解してもらえたでしょうか．

非常に分かりにくい説明で申し訳ありませんが，宜しくお願いし
ます．