A small math challenge you might enjoy

challenge

#1

Given the following set of 200 integers, find a subset whose sum is 0.

596208
603974
-955870
-802782
-880316
-401853
972841
-909682
79880
-730928
-43417
-431636
-559710
-567685
-234490
773676
88462
963841
-809518
-616502
-837067
359224
841748
-323596
224909
113798
-781599
533934
365290
-905183
9833
-223729
977187
-451455
779312
968495
285905
345245
526486
183475
-979764
491732
-214236
-357200
-549154
-121113
90867
817330
-451866
259946
-296835
124773
-666142
380763
434391
384980
444747
-261290
-74710
-787244
-927369
529293
486790
66326
-144529
734768
-484047
34772
14754
264152
787937
-475741
78190
486550
302371
-427121
511654
-879483
-460391
907468
-765521
-733873
-832696
-835283
120420
-888154
-148270
973453
-44360
-885687
-551365
832592
-838027
837601
-252588
517128
-949572
306485
668241
797212
4709
570370
-353120
769010
-804371
-739455
106426
506023
279316
765124
-234492
370537
784721
207946
403569
-152865
327863
-683165
-681201
681159
-805442
-791392
-786444
-987881
-168337
669652
-712919
-621257
-782899
386507
517135
-918435
757947
-488241
-845300
797798
-529392
118103
73054
-496415
-524874
-40163
-699967
-842084
-397486
602290
-535517
-989038
512312
-728350
-901344
118716
946241
-906103
365993
260956
-101480
673371
359847
-353112
-36109
-976992
-415173
-413862
-218240
548815
649370
-973702
-572208
152247
534975
-942193
979719
825103
226945
810719
-114611
694559
716346
214886
-354803
983103
723919
-309713
-140933
-938565
258121
637593
927995
704288
879534
806438
309882
484520
618040
979629
225795
779804
-907552
-149786

#2

Fun challenge. Here you go:

-955870, -909682, -567685, -234490, 773676, 88462, 963841, 841748

I used the generating function described here, which describes a product polynomial enumerating possible subset sums. I then used Cauchy’s integral formula to get the coefficients numerically. Was very proud of just solving an NP-complete problem in O(log n) (lol).

Then I just tried just using a naive method of brute force with memoization, cutting off subsets whose sum is too big so I can’t use them again. Took the first 25 elements of the list and boom, just like that. Turns out Cauchy was overkill on this particular list xD Well, I guess that’s how programming goes - form over function, eh? :stuck_out_tongue:


#3

Boi


#4

Ok, that might not have made much sense. This is what’s called an “Np-complete” problem, meaning your usual algorithms don’t do much good and you have to resort to weirdness like above. But this is a fun problem for anyone to consider!

The obvious solution is just to check ever possible subset of the above list until one sums to 0. Can anyone think of any sort of improvement on this algorithm? Adding things is hard, so are there perhaps some subsets that we can throw away right off the bat without adding?


#5

Not sure if this is what you meant but the obvious logical rules that occur to me are:

  • A subset must include at least 1 positive & 1 negative number
  • Sum of negative numbers in the subset = sum of positive numbers
  • subset must include an even number of odd numbers

#6

Ah, it looks like I might have by accident made this challenge a bit too easy. The goal was for a fully impossible challenge.
Anyways, here’s a slightly shorter solution if you guys so desire: https://scratch.mit.edu/discuss/post/3285044/