All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Divide et impera part two (Posted on 2015-08-26) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Much data but no proof--computer exploration | Comment 1 of 2
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information