２分割の方法は？

 投稿者：GAI  投稿日：2015年 7月28日(火)11時47分42秒
  S1={1,2,3,4}の集合を
A={1,4}
B={2,3} に同数の集合に分割すると
1+4=2+3
が成立する。

S2={1,2,3,4,5,6,7,8}の集合を
A={1,4,6,7}
B={2,3,5,8} に分割すると
1+4+6+7=2+3+5+8
1^2+4^2+6^2+7^2=2^2+3^2+5^2+8^2
が同時に成立する。

S3={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}の集合を
A={1,4,6,7,10,11,13,16}
B={2,3,5,8, 9,12,14,15}に分割すると
1+4+6+7+10+11+13+16=2+3+5+8+9+12+14+15
1^2+4^2+6^2+7^2+10^2+11^2+13^2+16^2=2^2+3^2+5^2+8^2+9^2+12^2+14^2+15^2
1^3+4^3+6^3+7^3+10^3+11^3+13^3+16^3=2^3+3^3+5^3+8^3+9^3+12^3+14^3+15^3
がやはり同時に成立した。

そこで
S4={1,2,3,･･･,32}の集合を同数の２組A,Bに分け
各集合の要素の1,2,3,4乗の和同士が同時に等しくなる分け方を探そうとした。
ところが調べ方のアルゴリズムが非能率的である事やら、私のハードの性能が今ひとつなのか私のやり方では（総当たりを調べている。）メモリーが足りませんの返事が返り二進も三進も進めません。
この壁を越える方法があれば結果が知りたい。（不可能も含めて）
もし一般に成立するなら可能な限りS={1～2^n}の２分割例がわかれば知りたい。







 		 

Re: ２分割の方法は？

 投稿者：山中和義  投稿日：2015年 7月28日(火)12時33分2秒
  > No.3787[元記事へ]

GAIさんへのお返事です。

> S1={1,2,3,4}の集合を
> A={1,4}
> B={2,3} に同数の集合に分割すると
> 1+4=2+3
> が成立する。
>
> S2={1,2,3,4,5,6,7,8}の集合を
> A={1,4,6,7}
> B={2,3,5,8} に分割すると
> 1+4+6+7=2+3+5+8
> 1^2+4^2+6^2+7^2=2^2+3^2+5^2+8^2
> が同時に成立する。
>
> もし一般に成立するなら可能な限りS={1～2^n}の２分割例がわかれば知りたい。


#3520

 		 

Re: ２分割の方法は？

 投稿者：GAI  投稿日：2015年 7月29日(水)09時42分35秒
  山中和義さんへのお返事です。

HREF="#3520">#3520


そういえば一度目にしていましたね。
しかしその時はこの真意が読めず、読み過ごしていました。
またこのThue-Morse sequenceは以前パターンを繰り返さない語を作り出すときに利用した経験があった。
この配列がこの問題と繋がっているんですね。
でもこれって凄いですね。
1～2^nをこの２グループに分けると、こんなにも見事な法則が成り立つなんて奇跡のようだ。
（1～16までを全パターンの場合について一つずつチェックして、唯一の組合せを絞り出したので尚更この出来事が起こることが奇跡に感じられる。）

いろいろ調べていたら
A={1,29,30,58}
B={2,22,37,57}
C={3,19,40,56}
D={7,12,47,52}
の４組に対しては
各成分の1～3乗までの和が全て等しく

A={1,5,10,24,28,42,47,51}
B={2,3,12,21,31,40,49,50}
の２組に対しては
各成分の1～7乗までの和どうしが全て等しくなる組合せになっているという。
これはこれでまた凄い。
でもよくこんな組合せを探し出すものですね。

 		 

Re: ２分割の方法は？

 投稿者：山中和義  投稿日：2015年 7月29日(水)10時24分6秒
  > No.3789[元記事へ]

GAIさんへのお返事です。

> （1～16までを全パターンの場合について一つずつチェックして、唯一の組合せを絞り出したので尚更この出来事が起こることが奇跡に感じられる。）


前出の部分和のプログラムで、1乗,2乗,3乗,4乗が算出できます。
1乗,2乗,3乗は、2通り。 4乗は、5988通り
対称性(+から始めるか、-から始める)を考慮すれば半分です。
なお、5乗以上は配列が定義できませんので、確認できません。


LET K=4 !べき乗
LET M=2^(K+1) !1からmまで
PRINT M

LET X=0 !Σi^k
FOR i=1 TO M
   LET X=X+i^K
NEXT i
LET X=X/2 !その半分
PRINT X

DIM A(X)
MAT A=ZER

FOR i=1 TO M !ひとつずつ取り出す
   LET D=i^K
   FOR P=X-D TO 1 STEP -1 !部分和を求める
      IF A(P)>0 THEN
         LET T=P+D
         LET A(T)=A(T)+A(P)
      END IF
   NEXT P
   IF D<=X THEN LET A(D)=A(D)+1
NEXT i

PRINT A(X);"通り" !答え（場合の数）

END


実行結果

32
3623048
5988 通り


 		 

Re: ２分割の方法は？

 投稿者：GAI  投稿日：2015年 7月29日(水)18時08分51秒
  > No.3790[元記事へ]

山中和義さんへのお返事です。

>
> 前出の部分和のプログラムで、1乗,2乗,3乗,4乗が算出できます。
> 1乗,2乗,3乗は、2通り。 4乗は、5988通り
> 対称性(+から始めるか、-から始める)を考慮すれば半分です。
> なお、5乗以上は配列が定義できませんので、確認できません。
>

このプログラムで
k=3として走らせると
実行結果
16
9248
2 通り
が返ってきますが,
この２通りは
実質
1,4,6,7,10,11,13,16
2,3,5,8, 9,12,14,15
を返していると思われますが、これらは互いに補集合にあるので
S={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
を２グループに分ける方法はただ一つの
A={1,4,6,7,10,11,13,16}
B={2,3,5,8, 9,12,14,15}
でしかないと言う意味と解釈できる。
実際
1^r+4^r+6^r+7^r+10^r+11^r+13^r+16^r=2^r+3^r+5^r+8^r+9^r+12^r+14^r+15^r
r=1-> 68=68
r=2-> 745=745
r=3-> 9248=9248
(r=4-> 122692≠121156)
で、これが唯一の組合せである。

ところが
k=4 で実行すると
5988　通り
が返ってきますがこのことは
5988/2=2994 通りの組合せが可能で、その内の一つが
A={1,4,6,7,10,11,13,16,18,19,21,24,25,28,30,31};
B={2,3,5,8,9,12,14,15,17,20,22,23,26,27,29,32};
が含まれていると解釈することになるのでしょうか？
確かにこの組合せは
r=1-> 264=264
r=2-> 5720=5720
r=3-> 139392=139392
r=4-> 3623048=3623048
(r=5-> 98024064≠98146944)
で条件を全て満たしています。
でも感覚的に他に2993通りもあるとは思えないんですが、もしわかれば実際にどんな組合せがあるのか知りたいです。


 		 

Re: ２分割の方法は？

 投稿者：山中和義  投稿日：2015年 7月29日(水)19時57分36秒
  > No.3791[元記事へ]

GAIさんへのお返事です。

> でも感覚的に他に2993通りもあるとは思えないんですが、もしわかれば実際にどんな組合せがあるのか知りたいです。



PRINT +1^4-2^4-3^4-4^4-5^4-6^4-7^4-8^4-9^4-10^4+11^4+12^4-13^4-14^4+15^4-16^4+17^4-18^4+19^4+20^4  &
&    -21^4-22^4-23^4+24^4+25^4-26^4-27^4-28^4+29^4+30^4+31^4-32^4

PRINT +1^4-2^4-3^4-4^4-5^4-6^4-7^4-8^4-9^4-10^4+11^4+12^4+13^4+14^4-15^4+16^4+17^4+18^4-19^4+20^4  &
&    +21^4+22^4-23^4-24^4+25^4-26^4+27^4-28^4+29^4-30^4-31^4+32^4

PRINT +1^4-2^4-3^4-4^4-5^4-6^4-7^4-8^4-9^4-10^4+11^4+12^4+13^4+14^4+15^4-16^4+17^4-18^4+19^4-20^4  &
&    +21^4+22^4-23^4-24^4-25^4+26^4-27^4+28^4+29^4-30^4-31^4+32^4

PRINT +1^4-2^4-3^4-4^4-5^4-6^4-7^4-8^4+9^4-10^4-11^4+12^4-13^4-14^4+15^4+16^4+17^4+18^4+19^4+20^4  &
&    +21^4-22^4+23^4+24^4-25^4-26^4+27^4+28^4-29^4-30^4-31^4+32^4

PRINT +1^4-2^4-3^4-4^4-5^4-6^4-7^4-8^4+9^4-10^4+11^4-12^4+13^4-14^4+15^4-16^4-17^4-18^4-19^4-20^4  &
&    -21^4+22^4-23^4-24^4+25^4+26^4-27^4-28^4+29^4+30^4+31^4-32^4

!など

END


#3518 の最後のプログラムを

OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=32
LET M=4 !※4乗

PUBLIC NUMERIC F(3000) !f(x)=x^m
LET S=0 !Σk^m

  :
  :

として、実行してください。


4乗の関係式ですので、1乗,2乗,3乗は満たしません。(満たす場合もある)


たとえば、1乗でも1から8までの整数を使用すれば、7通りあります。


PRINT +1^1-2^1-3^1+4^1-5^1+6^1+7^1-8^1
PRINT +1^1-2^1-3^1+4^1+5^1-6^1-7^1+8^1
PRINT +1^1-2^1+3^1-4^1-5^1+6^1-7^1+8^1
PRINT +1^1+2^1-3^1-4^1-5^1-6^1+7^1+8^1
PRINT +1^1+2^1-3^1+4^1+5^1+6^1-7^1-8^1
PRINT +1^1+2^1+3^1-4^1+5^1-6^1+7^1-8^1
PRINT +1^1+2^1+3^1+4^1-5^1-6^1-7^1+8^1
END


 		 

Re: ２分割の方法は？

 投稿者：GAI  投稿日：2015年 7月30日(木)07時02分58秒
  > No.3792[元記事へ]

山中和義さんへのお返事です。

>
> 4乗の関係式ですので、1乗,2乗,3乗は満たしません。(満たす場合もある)
>
>
> たとえば、1乗でも1から8までの整数を使用すれば、7通りあります。
>
>
> PRINT +1^1-2^1-3^1+4^1-5^1+6^1+7^1-8^1
> PRINT +1^1-2^1-3^1+4^1+5^1-6^1-7^1+8^1
> PRINT +1^1-2^1+3^1-4^1-5^1+6^1-7^1+8^1
> PRINT +1^1+2^1-3^1-4^1-5^1-6^1+7^1+8^1
> PRINT +1^1+2^1-3^1+4^1+5^1+6^1-7^1-8^1
> PRINT +1^1+2^1+3^1-4^1+5^1-6^1+7^1-8^1
> PRINT +1^1+2^1+3^1+4^1-5^1-6^1-7^1+8^1
> END

分かりました。
4乗に限ったものなんですね。
しかもS={1,2,3,･･･,32}
を同数に分けるのではなく、任意の数の２組に分ける方法での集計なんですね。
例
A={1,11,12,15,17,19,20,24,25,29,30,31}
B={2,3,4,5,6,7,8,9,10,13,14,16,18,21,22,23,26,27,28,32}

ですから例えば
S={1,2,3,･･･,64}
をちょうど同数どうしの２組に分けて、その各成分が
1,2,3,4,5乗のそれぞれの和で全て等しくなる分け方はただ一つで
Thue Morse sequence(A010060)での{0,1}対応での２組
A={1,4,6,7,10,11,13,16,18,19,21,24,25,28,30,31,･･･,61,64}（参考　A026147）
B={2,3,5,8,9,12,14,15,17,20,22,23,26,27,29,32,･･･,62,63}　（参考　A181155）
のただ一組に限られると理解していいんですね。

実際この２組で確認したら
1乗->1040,1040
2乗->44720,44720
3乗->2163200,2163200
4乗->111612176,111612176
5乗->5998553600,5998553600
でバッチリでした。

これがどこまでも
S={1～2^n}なる集合を同数の２組に分けて、その要素での
1,2,3,･･･,(n-1)乗全てに渡る和どうしが等しくできるグループ分けが可能（A026147,A181155 利用）とはまったく驚きです。



 		 

戻る