もやもやを解決して下さい。

 投稿者：ＧＡＩ  投稿日：2012年 3月29日(木)20時42分2秒
  開区間（０，１）
において、これを２等分するＰ２１＝（０，１／２）、Ｐ２２＝（１／２，１）
にそれぞれ含まれるように例えば、ｘ１∈Ｐ２１、ｘ２∈Ｐ２２
を任意に選ぶ。
次に（０，１）を３等分する区間の
Ｐ３１＝（０，１／３）、Ｐ３２＝（１／３，２／３）、Ｐ３３＝（２／３，１）
各部分にｘ１，ｘ２，ｘ３が含まれるようにｘ３を任意に選ぶ。
（選んだｘ１，ｘ２，ｘ３はそのまま値を変化させずにしておく。）
同様に、次に４等分する
Ｐ４１＝（０，１／４）、Ｐ４２＝（１／４，２／４），
Ｐ４３＝（２／４，３／４）、Ｐ４４＝（３／４，１）
各区間に一つずつｘ１，ｘ２，ｘ３，ｘ４が含まれるようにｘ４を任意に選ぶ。

この作業をいつまで続けられるかが疑問点なのです。




実際のやり方は例えば５等分までだと、
（０，１）区間で考えていると区間の境目が分数となるので、本質的に変わらない
（０，５！）＝（０，１２０）の区間に拡張し
２等分（０，６０）、（６０，１２０）
３等分（０，４０）、（４０，８０）、（８０，１２０）
４等分（０，３０）、（３０，６０）、（６０，９０）、（９０，１２０）
５等分（０，２４）、（２４，４８）、（４８，７２）、（７２，９６）、（９６，１２０）
と境目の座標を整数となるようにして考えると
たとえば
ｘ１＝１５、ｘ２＝１００、ｘ３＝４５、ｘ４＝６５、ｘ５＝７５
の点はこれを満たす一つの取り方になる。


現在１５等分の分割まで実際にｘ１，ｘ２，・・・、ｘ１５を配置することに成功しました。



そこで、この先の１６、１７等分の分割までの選び方を何方か挑戦してもらいたいんですが・・・
｛（０，１６！）（０，１７！）区間で考えています。｝
いつもあと少しのおしい所で完成せずにいます。


そしてこれが永遠に可能かというと、そうでは無いらしく１８等分以上の分割では点をどう自由に選んだとしても不可能であるらしいのです。


限界ぎりぎりの１７分割までは成功させたいと努力中なのですが未だ成功していません。このもやもやを解決して下さい。


 		 

Re: もやもやを解決して下さい。

 投稿者：山中和義  投稿日：2012年 3月31日(土)10時13分37秒
  > No.1841[元記事へ]

ＧＡＩさんへのお返事です。

> （０，５！）＝（０，１２０）の区間に拡張し

6等分の場合

開区間(0,60)
　 1 : {1,2,3,4,5,6,7,8,9}
　 2 : {11}
　 3 : {13,14}
　 4 : {16,17,18,19}
　 5 : {21,22,23}
　 6 : {25,26,27,28,29}
　 7 : {31,32,33,34,35}
　 8 : {37,38,39}
　 9 : {41,42,43,44}
　10 : {46,47}
　11 : {49}
　12 : {51,52,53,54,55,56,57,58,59}
とする。
各等分における区間は、
　 1 : 0  0  0  0  0
　 2 : 0  0  0  0  1
　 3 : 0  0  0  1  1
　 4 : 0  0  1  1  1
　 5 : 0  1  1  1  2
　 6 : 0  1  1  2  2
　 7 : 1  1  2  2  3
　 8 : 1  1  2  3  3
　 9 : 1  2  2  3  4
　10 : 1  2  3  3  4
　11 : 1  2  3  4  4
　12 : 1  2  3  4  5
となる。
よって、最初の値をその区間の代表として、その１つは、
　x1, x2, x3, x4, x5, x6
　 1, 51, 21, 31, 41, 11
とすればよい。



16等分の場合
　80個の区間に分割されるので、並びはPERM(80,16)の検証となる。

解
開区間(0, 720720)
1, 675676, 262081, 411841, 524161, 131041, 327601, 589681, 205921, 463321, 65521, 630631, 360361, 154441, 540541, 270271

　         2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 分割
　     1 : 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
　675676 : 1* 2  3  4  5  6  7  8  9 10 11 12 13 14 15
　262081 : 0  1* 1  1  2  2  2  3  3  4  4  4  5  5  5
　411841 : 1  1  2* 2  3  4  4  5  5  6  6  7  8  8  9
　524161 : 1  2  2  3* 4  5  5  6  7  8  8  9 10 10 11
　131041 : 0  0  0  0  1* 1  1  1  1  2  2  2  2  2  2
　327601 : 0  1  1  2  2  3* 3  4  4  5  5  5  6  6  7
　589681 : 1  2  3  4  4  5  6* 7  8  9  9 10 11 12 13
　205921 : 0  0  1  1  1  2  2  2* 2  3  3  3  4  4  4
　463321 : 1  1  2  3  3  4  5  5  6* 7  7  8  9  9 10
　 65521 : 0  0  0  0  0  0  0  0  0  1* 1  1  1  1  1
　630631 : 1  2  3  4  5  6  7  7  8  9 10*11 12 13 14
　360361 : 1  1  2  2  3  3  4  4  5  5  6  6* 7  7  8
　154441 : 0  0  0  1  1  1  1  1  2  2  2  2  3* 3  3
　540541 : 1  2  3  3  4  5  6  6  7  8  9  9 10 11*12
　270271 : 0  1  1  1  2  2  3  3  3  4  4  4  5  5  6*

と、1時間程度で、1つ目の解が見つかりました。

17等分は、3時間検索中で、まだ見つかっていません。
 		 

Re: もやもやを解決して下さい。

 投稿者：山中和義  投稿日：2012年 3月31日(土)15時40分2秒
  > No.1842[元記事へ]

ＧＡＩさんへのお返事です。

16等分は、1分程度。 17等分は、15分程度で1つ目の解が見つかります。
プログラムは、1つ目で停止するようになっています。
いくつか求める場合は、STOP文をコメントアウトしてください。

18等分は、1つ目と2つ目を固定したときに解は見つかりません。（1時間程度）


LET N=6 !n等分

!開区間をつくる数値を算出する
LET M=4 !N=1,2の場合
FOR i=3 TO N !最小公倍数ならすべての数で割り切れる
   LET M=LCM(M,i)
NEXT i
PRINT "開区間(0,";STR$(M);")"


DIM G(200) !開区間　x1,x2,…,xnの候補
LET S=0 !開区間の個数
LET FLG=0
FOR i=1 TO M !数値を区間に割り当てる
   FOR j=2 TO N
      IF MOD(i,M/j)=0 THEN EXIT FOR
   NEXT j
   IF j>N THEN !割り切れないなら、その区間に属する
      IF FLG=0 THEN !search left
         LET S=S+1 !最初の値をその区間の代表とする
         LET G(S)=i
         PRINT S;": {";STR$(i);

         LET FLG=1
      ELSE
      !PRINT ",";STR$(i); !←←←←←←←←←←
      END IF
   ELSE !割り切れるなら、区間の左端または右端である
      IF FLG=1 THEN PRINT "}" !find right

      LET FLG=0
   END IF
NEXT i
PRINT

FOR i=1 TO S !各数値の各等分における開区間
   PRINT i;":";
   FOR j=2 TO N !2,3,4,… 等分
      PRINT INT(G(i)/(M/j));
   NEXT j
   PRINT
NEXT i
PRINT


!実際に選んでみる
DIM P(N) !数値の並び　x1,x2,…,xn
DIM Q(S) !その数値の使用状況　0:未使用、1:使用中
MAT Q=ZER
!!FOR i=1 TO S !1つ目を選ぶ
!!   LET Q(i)=1 !仮に使用する
!!   LET P(1)=G(i)
!!   CALL try(2,P,Q, M,N,G,S) !2つ目以降
!!   LET Q(i)=0 !元に戻す
!!NEXT i
LET Q(1)=1 !1つ目を選ぶ
LET P(1)=G(1)
LET Q(S)=1 !2つ目を選ぶ
LET P(2)=G(S)
CALL try(3,P,Q, M,N,G,S) !3つ目以降

END


EXTERNAL SUB try(X,P(),Q(), M,N,G(),S) !バックトラック法で検証する
DIM H(0 TO X-1) !各区間の頻出度数
MAT H=ZER
FOR j=1 TO X-1 !各区間に分布するかどうか確認する
   LET t=INT(P(j)/(M/X)) !区間を算出する
   IF H(t)<>0 THEN EXIT FOR !1つずつ
   LET H(t)=1
NEXT j
IF j>X-1 THEN !既に選んだ数値x1,x2,…,xn-1で、条件を満たすなら

   FOR i=1 TO S !足らない区間（1つだけ）にxnを追加する
      IF Q(i)=0 THEN
         LET t=INT(G(i)/(M/X)) !区間を算出する
         IF H(t)=0 THEN !条件を満たすなら

            LET Q(i)=1 !仮に使用する
            LET P(X)=G(i)

            IF X=N THEN !すべて揃ったなら
               IF P(1)<P(N) THEN !対称性を考慮する
                  FOR k=1 TO N !結果を表示する
                     PRINT P(k);
                  NEXT k
                  PRINT

                  STOP !※1つのみ　←←←←←←←←←←
               END IF
            ELSE
               CALL try(X+1,P,Q, M,N,G,S) !次へ
            END IF

            LET Q(i)=0 !元に戻す

         END IF
      END IF
   NEXT i

END IF
END SUB


EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=a
END FUNCTION

EXTERNAL FUNCTION LCM(a,b) !最小公倍数
LET LCM=a/GCD(a,b)*b
END FUNCTION

 		 

戻る