-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path06p1a.htm
148 lines (133 loc) · 7.5 KB
/
06p1a.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
<HTML>
<HEAD>
<TITLE>和にならない分割</TITLE>
</HEAD>
<BODY>
<H1>和にならない分割</H1>
1,2,3 … N の数字を順番にk 個の集合のいずれかに入れていく。
そのとき、どの集合のどの３つの要素a,b,c をとっても、a+b=c の関係を満たさないよう
にする。
k=2,3,4に対して条件を満たす最大のNは既に求まっている。k=5に対して条件を満たす、
なるべく大きなN を見つける。
<P>ここでは集合A,B … E を考え、集合A から順に使用する。つまり1 は集合A に入れる。
また、各集合から見てA 寄りの集合を下位、E 寄りのものを上位と呼ぶこととする。つ
まり集合B は集合A よりも上位で集合C よりも下位となる。
<P>仮に設定したルール
<OL>
<LI>各集合に数字を入れる際には、可能な限り続けて入れるよう努める。
その集合を始めて使用する場合を例に説明すると下記のような工夫をする。
<PRE>
(a) N, N+1 … 2N
(b) N, N+2, N+3 … 2N, 2N+1 （ただしN≧2）
(c) N, N+1, N+3, N+4 … 2N-1, 2N, 2N+2 （ただしN≧3）
</PRE>
ただし、(b)の場合はN+1、(c)の場合はN+2 並びに2N+1 は当該集合よりも下位の集
合に入れなくてはならないものとする。
ここで示した(a),(b),(c)について、どのパターンが有利かは他の要素の格納状況による
ため、必ずしも一概には言えないが、(a)よりも(b)あるいは(c)の方が有利であるケースが
多いものと考えられる。
本来は、(a),(b),(c)のいずれを選択するかについてもプログラム自身に判断させて実行
させたいところであるが、今回は分割可能なパターンが複数存在する場合は、その情報
を画面に表示し、ユーザが手動で選択することとした。
<LI>下位の集合に限界まで詰め込んだら、上位の集合を使い始めることとする。
まずは、このルールに基づいてk=1,2,3 に対して分割を行ってみた。
<PRE>
k=1 集合A（1,2）
k=2 集合A（1,2,4,8）、集合B（3,5,6,7）
3 を入れる際に候補（3,4,5,6）,（3,5,6,7）より後者を選択
k=3 集合A（1,2,4,8,11,21）、集合B（3,5-7,19）、集合C（9,10,12-18,20）
9 を入れる際に候補（9-18）,（9,10,12-18,20）より後者を選択
</PRE>
</OL>
<P>この結果を検証すると、k=1並びにk=2では、最適解と合致しているが、k=3の場合は、下記に示す最適解を導き出すことはできなかった。
<PRE>
集合A（1,2,4,8,19,24）、集合B（3,5-7,11,21-23）、集合C（9,10,12-18,20）
</PRE>
これは、11を集合A,Bのどちらに格納した方が有利かによるが、現行のルールにはそれらを判断する基準を定義しておらず、より下位の集合Aに入れてしまったためである。
ただし、この解はk=3の場合に最適であるものの、k=4以降では最適解とは合致しない。
<P>k=4以降の評価を行うにあたっては下記を初期値（k=3での分割）として採用した。
<PRE>
集合A（1,2,4,8,11,22）、集合B（3,5-7,19,21,23）、集合C（9,10,12-18,20）
</PRE>
<P>k=4で導き出された結果
<PRE>
集合A（1,2,4,8,11,22,25,50,63）
集合B（3,5-7,19,21,23,51-53,64-66）
集合C（9,10,12-18,20,54-62）
集合D（24,26-49）
24を入れる際に（24-48）,（24,26-49）より後者を選択
</PRE>
<P>k=2,3,4では、ユーザによる手動での選択が各々１度入っている。
ただし、これは現行のルールで(a)(b)(c)を等価としたためであり、(b)あるいは(c)の方が(a)よりも優位であるとした場合には、この手動での選択なしに同等の結果が得られる。
<P>k=5で導き出された結果
<PRE>
集合A（1,2,4,8,11,22,25,50,63,69,135,140,150,178,191）
集合B（3,5-7,19,21,23,51-53,64-66,137-139,151-153,179-181）
集合C（9,10,12-18,20,54-62,141-149,182-190）
集合D（24,26-49,154-177）
集合E（67,68,70-134,136）
67を入れる際に（67-134）,（67,69-135）,（67,68,70-134,136）より（67,68,70-134,136）を選択
</PRE>
<P>ここで、現行のルールには反映されていないが、集合Dの（154-177）については（154,156-177,179）とし、155と178を集合Aに入れるという分割が可能である。
仮にルール化するとすれば、下記のようになる。
<PRE>
(b') 既にその集合が使われていて、その最初の要素（最小の数）をsとした場合、
s+1がその集合の要素で無い場合に限り(b)と同様の分割が可能
N,N+2,N+3 … N+s-1,N+s+1
</PRE>
<P>これを適用し、179までの分割に反映すると下記のようになる
<PRE>
集合A（1,2,4,8,11,22,25,50,63,69,135,140,150,155,178）
集合B（3,5-7,19,21,23,51-53,64-66,137-139,151-153）
集合C（9,10,12-18,20,54-62,141-149）
集合D（24,26-49,154,156-177,179）
集合E（67,68,70-134,136）
</PRE>
この結果を初期条件に180以降の分割を実行すると下記の結果が得られる。
<PRE>
集合A（1,2,4,8,11,22,25,50,63,69,135,140,150,155,178,183,193）
集合B（3,5-7,19,21,23,51-53,64-66,137-139,151-153,180-182,194-196）
集合C（9,10,12-18,20,54-62,141-149,184-192）
集合D（24,26-49,154,156-177,179）
集合E（67,68,70-134,136）
</PRE>
これは、既知の解196 (Journal of Recreational Mathematics 7(2) '74) と合致する。
参考までにこの結果を初期値としてk=6の評価を行うと568が得られた。
<PRE>
集合A（1,2,4,8,11,22,25,50,63,69,135,140,150,155,178,183,193,199,395,400,
410,438,451,519,532）
集合B（3,5-7,19,21,23,51-53,64-66,137-139,151-153,180-182,194-196,397-399,
411-413,439-441,520-522,557-559）
集合C（9,10,12-18,20,54-62,141-149,184-192,401-409,442-450,523-531,
560-568）
集合D（24,26-49,154,156-177,179,414-437,533-556）
集合E（67,68,70-134,136,452-518）
集合F（197,198,200-394,396）
197を入れる際に（197-394）, （197,198,200-394,396）より後者を選択
</PRE>
<P>ここで、集合Dの（414-437）については（414,416-437,439）とし、415と438を集合Aに入れるという分割が可能である。
<PRE>
集合A（1,2,4,8,11,22,25,50,63,69,135,140,150,155,178,183,193,199,395,400,
410,415,438）
集合B（3,5-7,19,21,23,51-53,64-66,137-139,151-153,180-182,194-196,397-399,
411-413）
集合C（9,10,12-18,20,54-62,141-149,184-192,401-409）
集合D（24,26-49,154,156-177,179,414,416-437,439）
集合E（67,68,70-134,136）
集合F（197,198,200-394,396）
</PRE>
この状態を初期条件に440以降の分割を実行すると下記の結果が得られる。
<PRE>
集合A（1,2,4,8,11,22,25,50,63,69,135,140,150,155,178,183,193,199,395,400,
410,415,438,443,453,524,537,571）
集合B（3,5-7,19,21,23,51-53,64-66,137-139,151-153,180-182,194-196,397-399,
411-413,440-442,454-456,525-527,572-574）
集合C（9,10,12-18,20,54-62,141-149,184-192,401-409,444-452,528-536,
562-570）
集合D（24,26-49,154,156-177,179,414,416-437,439,538-561）
集合E（67,68,70-134,136,457-523）
集合F（197,198,200-394,396）
</PRE>
<P>上記では574となっている。
</BODY>
</HTML>