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

Question

-------------------
区間[0, 1]において，
１．区間内の適当な所に点（・）を書く．
２．[0, 1]の区間を２等分し，各々の区間に点がはいるような点を１つ書く．
    （ただし，１で書いた点はそのままなので，点の無い方の区間に書く）
３．[0, 1]の区間を３等分し，点の無い区間に１つだけ点を書く．
．．．．．
．．．．．
１７．[0, 1]の区間を１７等分し，点の無い区間に１つだけ点を書く．

（例）    
|       .|         . |
0.0     0.250.5     0.751.0

↓↓↓↓↓↓↓↓（２等分から３等分）

|       .  |   .    |    . |
0.0     0.25   0.52     0.751.0

上の様なことを区間が１７等分まで繰り返して下さい．
--------------------

以上のようにして，区間を１７等分までしたときに適当な点の値を答えろ
という問題がありました，どうしても分からなかったのでだれか，解答
できる人がいましたら，是非値を教えて欲しいのですが．
また，条件がもう１つありまして，区間の境界上には点は書いてはいけない
ようになっています．

詳しい解説なんかも書いてもらえるとともてもありがたいです．
宜しくお願いします．

stomachman · Accepted Answer

さらに、解の構造の分析その２。

●以下の区画は解には全く現れない。つまり、これらの区画内に点を置くことは出来ない。
{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

oodaiko · Answer

問題の意味が不明です。

＞点の無い区間に１つだけ点を書く
＞区間の境界上には点は書いてはいけない 
この２つの条件をいっしょにするとつまり
「点の無い区間を選び（そのような区間はこのプロセスから考えて
１つしかあり得ませんが）そこから
1/2,1/3,2/3,1/4,2/4,3/4,1/5,2/5,…,16/17
以外の任意の位置を１つ選んでそこに点を書く」
ということでよいのでしょうか

＞１７等分までしたときに適当な点の値を答えろ
「点の値」というのは[0,1]区間における点の座標という意味ですね。
「適当な点」とはどの点のことでしょうか
１.で最初に書いた点のことでしょうか。これは任意なので
答えようがないと思いますが。
（他の点にしても多少の制約があるとはいえ任意なので
「点の値」など答えようがありません）

「点の値」というのはまさか「点の個数」の意味ではないですよね。
（それなら１７しかありませんが）

文字数の制約のため内容を詳しく書けなかったのであれば
（補足欄にはいくらでも書けますので）問題のきちんとした記述をお願いします。

oodaiko · Answer

＞点が２つ入ってしまう区間ができてしまい
あーなるほど。私は漠然と
「このプロセスの各段階において点の無い区間はただ１つだけであり、その他の区間には必ず１つだけ点が含まれる」
という条件が自然に満たされるものだと思い込んでしまいましたが、それは正しくなかったですね。私が書いた
＞点の無い区間を選び（そのような区間はこのプロセスから考えて
＞１つしかあり得ませんが）
という文も間違いでした。f(^^;;

それで御質問の意味がわかりました。

つまり

このプロセスのすべての段階において、
「点の無い区間はただ１つだけであり、かつ（というよりこの条件を満たせば必然的にですが）その他の区間にはすべて１づつ点が含まれている」
という条件を満足するような（１７個の）点列の例を求めよ。

ということですね。

回答は今考え中ですが、他の回答者の方が私と同じ勘違いをされるといけないので（←そんな早とちりをするのは私だけか(^^;; とりあえず確認の意味でアップしました

stomachman · Answer

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!)}という有限集合から１７個の要素を選ぶ問題と考えて良いのは自明でしょうから、それで代数学の問題に帰着するのかな？

で、答えはですね。分かりません。

stomachman · Answer

えっと、たとえば列：
07/1311/134/1512/175/1212/132/158/131/310/131/58/1716/171/1511/176/17
（いや、丁度切れ目に来るのがお気に召さなければ、それぞれに1/1000位加えた物）というのは、題意を満たしているでしょうか？


　実はこれ、力ずくで探索した結果です。
　何をやったかと申しますと…

　「切れ目」に来るのは（n/m）（0≦n＜m, 1≦m≦17）という形の有理数だけです。そのうち、既約のものだけ数えますと、96個あります。
最後に１７分割したときに各区画に１個づつ入る訳ですから、この９６個（或いはそれにごく小さい値を加えた物）の中から１７個を、題意に合うように選べばよい。
　そういう条件で、深さ優先探索(search)をやるプログラムをちょいちょいと書いて走らせたんです。

　解はもの凄く沢山出たのですが、上記の例はその最初の物。
　これが題意を満たしているなら、解があることは確かめられたことになり、あとはどうエレガントに構成するか、という問題でして、oodaiko先生ってば宜しくお願いいたします。

stomachman · Answer

No.4のやつは数列です。勿論１，２，３，…，１７分割の順ですよ。

プログラムは最初Visual Basicでちょいちょい、とやったらこれが思いのほか重くってですね、それで似てる言語のコンパイラは？って探したらFortranがありましたんで、そっちに書き換えて走らせました。（その際に再帰呼び出しrecursionをtail mergeという方法でループに変換しています。）

　ともあれ、力ずくじゃあ、数学の問題の答にはなってないでしょう。ここにupするのはどうかと思います。

stomachman · Answer

どういう数列が解になるのか。何かヒントになればと思って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)の形で書くと
15283266941921360337520489646434
となります。

[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}
である。ごく限られた番号の組み合わせであることが分かります。

う～ん。やっぱりプログラムをシェアしなくては無理かなあ。

stomachman · Answer

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。

としておくべきでした。

stomachman · Answer

今度は、
一番要素の数が少ない、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) 6941**2652
b) **41692652
c) 52**266941
d) **52266941
およびc(7)とc(17)の選択パターン４通り、これらの掛け算で、実質16通りということですね。
そのどれかに、任意に選べる他の番号の選択を組み合わせることで、全ての解が構成されます。

さて、これは一体何を意味しているのでしょう？
群だの環だの、代数構造がおでましになる予兆でしょうか？

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

問題の意味が不明です。

この回答への補足

＞点が２つ入ってしまう区間ができてしまい

B(x,m) = {t| 0≦t≦1} - {t| [mx]/m≦t＜ ([mx]+1)/m}

えっと、たとえば列：

No.4のやつは数列です。

どういう数列が解になるのか。

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

今度は、

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

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

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