Divide et impera asked to divide the set of integers from 1 to 15 into two subsets A & B,
so that the sum of the numbers in A equals the product
of the numbers in B.
Instead of an upper limit of 15, use n to stand for any positive integer.
Find, with proof for what values of n the task is possible?
Here are all the ways of accomplishing the task for n through 50. Only 1 (of course), 2 and 4 have no solution. For brevity, only sets B are shown:
3 b: 3
5 b: 1 2 4
6 b: 1 2 6
7 b: 1 3 6
8 b: 1 3 8
9 b: 1 4 8
10 b: 6 7
10 b: 1 4 10
10 b: 1 2 3 7
11 b: 1 5 10
12 b: 2 4 8
12 b: 1 5 12
13 b: 1 6 12
14 b: 2 4 11
14 b: 1 6 14
14 b: 1 3 5 6
15 b: 3 5 7
15 b: 1 9 11
15 b: 1 7 14
16 b: 3 5 8
16 b: 1 7 16
16 b: 1 4 5 6
17 b: 10 13
17 b: 1 8 16
17 b: 1 3 5 9
18 b: 1 8 18
19 b: 2 6 14
19 b: 1 9 18
19 b: 1 3 4 14
19 b: 1 2 7 12
20 b: 4 6 8
20 b: 1 13 14
20 b: 1 9 20
20 b: 1 2 3 4 8
21 b: 2 8 13
21 b: 1 10 20
21 b: 1 3 7 10
22 b: 1 10 22
22 b: 1 3 7 11
23 b: 1 11 22
23 b: 1 3 6 14
24 b: 5 7 8
24 b: 1 14 19
24 b: 1 11 24
24 b: 1 2 8 17
25 b: 1 12 24
25 b: 1 4 5 15
25 b: 1 2 7 21
26 b: 15 21
26 b: 3 6 18
26 b: 2 3 5 11
26 b: 1 12 26
26 b: 1 2 8 20
27 b: 3 4 5 6
27 b: 1 17 20
27 b: 1 13 26
28 b: 3 7 18
28 b: 1 13 28
29 b: 4 6 17
29 b: 2 8 25
29 b: 1 14 28
29 b: 1 2 3 4 17
30 b: 4 10 11
30 b: 3 6 24
30 b: 1 14 30
30 b: 1 5 8 11
30 b: 1 2 12 18
31 b: 3 12 13
31 b: 2 11 21
31 b: 1 15 30
31 b: 1 2 10 23
32 b: 7 8 9
32 b: 2 13 19
32 b: 2 3 7 12
32 b: 1 21 23
32 b: 1 15 32
33 b: 3 8 22
33 b: 3 4 5 9
33 b: 1 16 32
33 b: 1 4 6 22
33 b: 1 3 7 25
33 b: 1 3 6 29
34 b: 1 16 34
35 b: 2 3 5 20
35 b: 1 20 29
35 b: 1 17 34
35 b: 1 4 10 15
36 b: 22 28
36 b: 1 17 36
37 b: 21 31
37 b: 2 11 30
37 b: 1 18 36
37 b: 1 4 12 14
37 b: 1 4 5 33
38 b: 2 14 25
38 b: 1 18 38
38 b: 1 3 9 26
38 b: 1 2 3 4 5 6
39 b: 5 10 15
39 b: 4 11 17
39 b: 3 7 35
39 b: 2 6 7 9
39 b: 1 25 29
39 b: 1 19 38
39 b: 1 3 4 7 9
40 b: 8 9 11
40 b: 2 3 11 12
40 b: 1 19 40
40 b: 1 3 10 26
41 b: 3 8 34
41 b: 2 3 4 5 7
41 b: 1 20 40
41 b: 1 4 6 34
42 b: 4 8 27
42 b: 3 12 24
42 b: 1 20 42
43 b: 1 21 42
43 b: 1 6 8 19
43 b: 1 2 18 25
44 b: 8 10 12
44 b: 1 29 32
44 b: 1 21 44
44 b: 1 2 12 39
44 b: 1 2 5 6 16
44 b: 1 2 4 8 15
45 b: 27 36
45 b: 5 10 20
45 b: 4 8 31
45 b: 4 6 41
45 b: 3 4 6 14
45 b: 2 19 26
45 b: 2 6 7 12
45 b: 1 22 44
45 b: 1 5 6 33
45 b: 1 3 11 30
45 b: 1 3 4 7 12
45 b: 1 2 17 29
45 b: 1 2 7 8 9
45 b: 1 2 3 4 41
46 b: 1 22 46
46 b: 1 5 11 19
46 b: 1 4 10 26
47 b: 5 7 31
47 b: 2 5 10 11
47 b: 1 23 46
47 b: 1 5 6 36
48 b: 8 11 13
48 b: 5 12 19
48 b: 3 18 21
48 b: 3 13 29
48 b: 2 14 40
48 b: 2 13 43
48 b: 1 27 41
48 b: 1 23 48
48 b: 1 6 10 19
48 b: 1 2 3 4 6 8
49 b: 6 9 22
49 b: 4 5 6 10
49 b: 1 24 48
49 b: 1 7 10 17
49 b: 1 2 3 9 22
49 b: 1 2 3 4 5 10
50 b: 28 43
50 b: 4 11 28
50 b: 1 24 50
To ease counting, to see if any number is missing, just the first found solution is shown below, but the table is extended to n=500. Only 2 and 4 in addition to the trivial 1, remain without solution. (come to think of it, 2 is also trivial, leaving 4 as the only non-trivial case in the range examined found to be without a solution)
3 b: 3
5 b: 1 2 4
6 b: 1 2 6
7 b: 1 3 6
8 b: 1 3 8
9 b: 1 4 8
10 b: 6 7
11 b: 1 5 10
12 b: 2 4 8
13 b: 1 6 12
14 b: 2 4 11
15 b: 3 5 7
16 b: 3 5 8
17 b: 10 13
18 b: 1 8 18
19 b: 2 6 14
20 b: 4 6 8
21 b: 2 8 13
22 b: 1 10 22
23 b: 1 11 22
24 b: 5 7 8
25 b: 1 12 24
26 b: 15 21
27 b: 3 4 5 6
28 b: 3 7 18
29 b: 4 6 17
30 b: 4 10 11
31 b: 3 12 13
32 b: 7 8 9
33 b: 3 8 22
34 b: 1 16 34
35 b: 2 3 5 20
36 b: 22 28
37 b: 21 31
38 b: 2 14 25
39 b: 5 10 15
40 b: 8 9 11
41 b: 3 8 34
42 b: 4 8 27
43 b: 1 21 42
44 b: 8 10 12
45 b: 27 36
46 b: 1 22 46
47 b: 5 7 31
48 b: 8 11 13
49 b: 6 9 22
50 b: 28 43
51 b: 7 8 23
52 b: 8 12 14
53 b: 4 8 43
54 b: 2 21 34
55 b: 5 15 20
56 b: 8 13 15
57 b: 5 8 40
58 b: 3 5 7 16
59 b: 6 12 24
60 b: 8 14 16
61 b: 42 43
62 b: 7 8 34
63 b: 8 13 19
64 b: 8 15 17
65 b: 36 57
66 b: 4 20 27
67 b: 42 52
68 b: 8 16 18
69 b: 6 8 49
70 b: 6 14 29
71 b: 4 10 62
72 b: 8 17 19
73 b: 6 17 26
74 b: 5 16 34
75 b: 4 17 41
76 b: 10 12 24
77 b: 6 8 61
78 b: 45 66
79 b: 5 23 27
80 b: 10 11 29
81 b: 13 14 18
82 b: 45 73
83 b: 8 13 33
84 b: 8 20 22
85 b: 6 24 25
86 b: 6 12 51
87 b: 12 15 21
88 b: 9 13 33
89 b: 8 19 26
90 b: 5 10 80
91 b: 52 78
92 b: 8 22 24
93 b: 12 15 24
94 b: 57 76
95 b: 7 9 71
96 b: 8 23 25
97 b: 6 15 52
98 b: 15 16 20
99 b: 6 14 58
100 b: 14 17 21
101 b: 55 91
102 b: 70 73
103 b: 7 21 36
104 b: 10 11 49
105 b: 8 9 76
106 b: 13 18 24
107 b: 10 22 26
108 b: 8 26 28
109 b: 15 18 22
110 b: 70 85
111 b: 14 20 22
112 b: 8 27 29
113 b: 14 19 24
114 b: 14 16 29
115 b: 9 12 61
116 b: 12 14 40
117 b: 10 11 62
118 b: 12 20 29
119 b: 8 26 34
120 b: 8 29 31
121 b: 1 60 120
122 b: 66 111
123 b: 5 29 52
124 b: 8 30 32
125 b: 14 18 31
126 b: 8 18 55
127 b: 14 18 32
128 b: 13 18 35
129 b: 13 20 32
130 b: 11 24 32
131 b: 13 20 33
132 b: 8 32 34
133 b: 8 23 48
134 b: 11 24 34
135 b: 14 21 31
136 b: 76 120
137 b: 12 23 34
138 b: 87 108
139 b: 12 23 35
140 b: 13 26 29
141 b: 10 11 90
142 b: 15 16 42
143 b: 9 18 63
144 b: 19 21 26
145 b: 78 133
146 b: 8 16 83
147 b: 9 13 92
148 b: 8 36 38
149 b: 87 126
150 b: 6 39 48
151 b: 4 27 105
152 b: 11 25 42
153 b: 85 136
154 b: 6 29 68
155 b: 106 112
156 b: 8 38 40
157 b: 1 78 156
158 b: 13 20 48
159 b: 22 23 25
160 b: 9 20 71
161 b: 15 18 48
162 b: 13 14 72
163 b: 8 18 92
164 b: 14 16 60
165 b: 106 127
166 b: 4 7 17 29
167 b: 13 29 37
168 b: 8 41 43
169 b: 14 20 51
170 b: 91 157
171 b: 19 22 35
172 b: 16 25 37
173 b: 105 141
174 b: 8 27 70
175 b: 11 29 48
176 b: 20 25 31
177 b: 10 29 54
178 b: 12 24 55
179 b: 10 20 80
180 b: 12 19 71
181 b: 115 141
182 b: 9 18 102
183 b: 112 148
184 b: 9 11 170
185 b: 12 16 89
186 b: 4 24 179
187 b: 2 9 10 97
188 b: 108 162
189 b: 10 38 47
190 b: 10 15 120
191 b: 13 23 61
192 b: 17 31 35
193 b: 5 7 13 41
194 b: 14 21 64
195 b: 16 29 41
196 b: 8 48 50
197 b: 105 183
198 b: 13 26 58
199 b: 5 8 16 31
200 b: 15 29 46
201 b: 19 28 38
202 b: 15 20 68
203 b: 13 14 113
204 b: 11 43 44
205 b: 2 3 10 13 27
206 b: 13 24 68
207 b: 9 19 125
208 b: 15 37 39
209 b: 12 28 65
210 b: 115 190
211 b: 9 12 205
212 b: 12 24 78
213 b: 147 153
214 b: 6 32 119
215 b: 15 23 67
216 b: 13 23 78
217 b: 3 6 9 145
218 b: 7 9 14 27
219 b: 20 30 40
220 b: 150 160
221 b: 15 22 74
222 b: 16 20 77
223 b: 14 24 74
224 b: 9 23 121
225 b: 8 19 166
226 b: 120 211
227 b: 4 6 25 43
228 b: 17 34 45
229 b: 12 24 91
230 b: 12 29 76
231 b: 126 210
232 b: 150 178
233 b: 8 53 64
234 b: 26 31 34
235 b: 7 8 13 38
236 b: 8 58 60
237 b: 8 20 175
238 b: 3 50 188
239 b: 11 49 53
240 b: 19 37 41
241 b: 9 11 14 21
242 b: 18 37 44
243 b: 10 22 134
244 b: 8 60 62
245 b: 15 20 100
246 b: 18 29 58
247 b: 19 22 73
248 b: 10 41 75
249 b: 157 196
250 b: 147 211
251 b: 11 27 106
252 b: 10 26 122
253 b: 5 38 168
254 b: 10 31 104
255 b: 22 29 51
256 b: 9 23 158
257 b: 136 241
258 b: 12 38 73
259 b: 14 47 51
260 b: 8 64 66
261 b: 8 22 193
262 b: 160 213
263 b: 148 232
264 b: 13 14 191
265 b: 11 38 84
266 b: 183 192
267 b: 15 24 99
268 b: 14 27 95
269 b: 16 29 78
270 b: 14 31 84
271 b: 21 35 50
272 b: 21 41 43
273 b: 8 48 97
274 b: 12 15 208
275 b: 21 34 53
276 b: 19 34 59
277 b: 12 19 168
278 b: 8 38 127
279 b: 19 41 50
280 b: 29 33 41
281 b: 12 35 94
282 b: 171 231
283 b: 11 12 16 19
284 b: 19 36 59
285 b: 14 25 116
286 b: 28 34 43
287 b: 18 22 104
288 b: 12 36 96
289 b: 11 24 158
290 b: 153 273
291 b: 14 28 108
292 b: 14 29 105
293 b: 11 30 130
294 b: 8 31 174
295 b: 18 41 59
296 b: 16 33 83
297 b: 202 217
298 b: 8 26 213
299 b: 14 31 103
300 b: 162 276
301 b: 8 41 138
302 b: 10 48 95
303 b: 26 31 57
304 b: 178 258
305 b: 23 44 46
306 b: 9 18 288
307 b: 11 23 186
308 b: 23 43 48
309 b: 14 31 110
310 b: 11 42 104
311 b: 202 238
312 b: 192 252
313 b: 17 20 144
314 b: 175 280
315 b: 17 40 73
316 b: 13 18 213
317 b: 14 22 163
318 b: 20 46 55
319 b: 23 41 54
320 b: 29 31 57
321 b: 14 32 115
322 b: 16 27 120
323 b: 25 29 72
324 b: 20 25 105
325 b: 175 300
326 b: 23 34 68
327 b: 22 38 64
328 b: 15 52 69
329 b: 20 22 123
330 b: 18 21 144
331 b: 19 28 103
332 b: 8 82 84
333 b: 20 38 73
334 b: 14 18 221
335 b: 26 40 54
336 b: 14 29 139
337 b: 6 33 286
338 b: 16 47 76
339 b: 21 37 74
340 b: 21 34 81
341 b: 196 295
342 b: 22 35 76
343 b: 19 24 129
344 b: 28 45 47
345 b: 13 14 326
346 b: 223 267
347 b: 22 23 119
348 b: 12 24 210
349 b: 6 60 169
350 b: 19 26 124
351 b: 12 65 79
352 b: 8 87 89
353 b: 11 48 118
354 b: 22 38 75
355 b: 9 56 125
356 b: 20 22 144
357 b: 16 18 221
358 b: 252 253
359 b: 12 20 268
360 b: 11 39 151
361 b: 8 59 138
362 b: 190 343
363 b: 14 28 168
364 b: 12 40 138
365 b: 17 40 98
366 b: 28 38 63
367 b: 10 31 217
368 b: 22 44 70
369 b: 213 318
370 b: 19 34 106
371 b: 15 51 90
372 b: 10 32 216
373 b: 4 6 25 116
374 b: 35 40 50
375 b: 5 11 20 64
376 b: 8 93 95
377 b: 14 17 298
378 b: 241 295
379 b: 12 45 133
380 b: 15 18 267
381 b: 225 321
382 b: 12 24 253
383 b: 22 29 115
384 b: 16 32 144
385 b: 7 84 126
386 b: 262 283
387 b: 12 33 189
388 b: 15 23 218
389 b: 14 51 106
390 b: 14 30 181
391 b: 25 51 60
392 b: 14 20 274
393 b: 23 48 70
394 b: 273 283
395 b: 14 21 265
396 b: 33 41 58
397 b: 24 53 62
398 b: 8 43 230
399 b: 33 34 71
400 b: 252 316
401 b: 210 381
402 b: 262 307
403 b: 30 43 63
404 b: 10 29 281
405 b: 238 343
406 b: 217 378
407 b: 14 35 169
408 b: 13 37 173
409 b: 225 370
410 b: 14 66 91
411 b: 12 64 110
412 b: 8 102 104
413 b: 267 318
414 b: 26 34 97
415 b: 7 45 273
416 b: 38 43 53
417 b: 20 58 75
418 b: 12 21 346
419 b: 16 20 274
420 b: 16 37 149
421 b: 255 346
422 b: 30 33 90
423 b: 37 44 55
424 b: 36 49 51
425 b: 26 44 79
426 b: 43 44 48
427 b: 20 38 120
428 b: 22 35 119
429 b: 12 65 118
430 b: 14 21 314
431 b: 26 55 65
432 b: 25 45 83
433 b: 18 31 168
434 b: 34 36 77
435 b: 232 406
436 b: 28 43 79
437 b: 18 20 265
438 b: 26 52 71
439 b: 21 34 135
440 b: 36 39 69
441 b: 15 30 216
442 b: 231 421
443 b: 18 41 133
444 b: 31 43 74
445 b: 31 34 94
446 b: 252 393
447 b: 23 41 106
448 b: 15 69 97
449 b: 19 26 204
450 b: 19 62 86
451 b: 14 30 242
452 b: 15 52 131
453 b: 31 36 92
454 b: 15 24 286
455 b: 29 47 76
456 b: 23 34 133
457 b: 3 25 34 41
458 b: 10 69 152
459 b: 6 109 161
460 b: 15 63 112
461 b: 315 336
462 b: 20 29 184
463 b: 14 44 174
464 b: 30 57 63
465 b: 34 37 86
466 b: 13 48 174
467 b: 43 47 54
468 b: 15 83 88
469 b: 7 11 22 65
470 b: 26 34 125
471 b: 19 59 99
472 b: 258 430
473 b: 24 53 88
474 b: 20 27 208
475 b: 15 76 99
476 b: 18 31 203
477 b: 18 27 234
478 b: 19 64 94
479 b: 33 49 71
480 b: 35 54 61
481 b: 297 388
482 b: 22 38 139
483 b: 38 48 64
484 b: 36 44 74
485 b: 253 463
486 b: 34 44 79
487 b: 330 358
488 b: 19 57 110
489 b: 22 26 209
490 b: 26 44 105
491 b: 20 25 241
492 b: 16 86 88
493 b: 10 103 118
494 b: 36 53 64
495 b: 23 65 82
496 b: 19 37 175
497 b: 22 23 244
498 b: 20 31 200
499 b: 11 39 290
500 b: 13 46 209
DefDbl A-Z
Dim crlf$, tot, prod, a(), b(), sz, lmt, lastdone
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For sz = 2 To 500
lmt = sz * (sz + 1) / 2
ReDim a(sz), b(sz)
a(0) = 0: b(0) = 0
tot = 0: prod = 1
addOn 1
Next sz
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub addOn(wh)
a(0) = a(0) + 1
a(a(0)) = wh: tot = tot + wh
If wh = sz Then
If tot = prod Then
Text1.Text = Text1.Text & sz
' If sz <= 50 Then
' Text1.Text = Text1.Text & " a:"
' For i = 1 To a(0)
' Text1.Text = Text1.Text & Str(a(i))
' Next
' End If
Text1.Text = Text1.Text & " b:"
For i = 1 To b(0)
Text1.Text = Text1.Text & Str(b(i))
Next
Text1.Text = Text1.Text & crlf
DoEvents
lastdone = sz
End If
Else
If lastdone < sz Then addOn wh + 1
End If
tot = tot - wh
a(0) = a(0) - 1
If prod * wh <= lmt Then
b(0) = b(0) + 1
b(b(0)) = wh: prod = prod * wh
If wh = sz Then
If tot = prod Then
Text1.Text = Text1.Text & sz
' If sz <= 50 Then
' Text1.Text = Text1.Text & " a:"
' For i = 1 To a(0)
' Text1.Text = Text1.Text & Str(a(i))
' Next
' End If
Text1.Text = Text1.Text & " b:"
For i = 1 To b(0)
Text1.Text = Text1.Text & Str(b(i))
Next
Text1.Text = Text1.Text & crlf
DoEvents
lastdone = sz
End If
Else
If lastdone < sz Then addOn wh + 1
End If
prod = prod / wh
b(0) = b(0) - 1
End If
End Sub
|
|
Posted by Charlie
on 2015-08-26 12:58:28 |
Much data but no proof--computer exploration
