Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Re: Combinatorics Problem
Replies: 0

 Rex Boggs Posts: 80 Registered: 12/6/04
Re: Combinatorics Problem
Posted: Feb 24, 1996 6:51 PM

A question that I posed to a colleague, and passed onto the list, was the
task of splitting a set of 200 numbers into two sets that had the same sum.

I claimed that it is unsolvable, in practice, since there is no efficient
algorithm, other than testing a huge number of cases (I suggested on the
order of 200 C 100).

Two of the respondents have indicated that this problem is NP-Complete, and
hence the number of operations rises exponentially compared to the number of
values given. Given this, for a large enough set, the problem is
effectively unsolvable. So the question becomes, is 200 values sufficiently
large?

Here is the test.

The number below have a total of 10 000 000. Can you split it into two sets
that each have a sum of 5 000 000? I generated this list using Excel, so
there _is_ an answer, that currently only I know. Shane, me old mate, good
luck!

BTW, this whole thing arose out of a grade 8 problem on putting 9 songs onto
the two sides of a cassette tape.

Cheers

Rex

200 Random Numbers That Can Be Split Into Two Groups Whose Sum Is The Same

4370 278190 492847 743646
4838 278455 501173 744614
8119 278911 510680 746189
18569 282512 510891 747146
32701 287872 511926 747714
34673 291891 514524 760202
43182 301115 522265 762929
44789 303653 534640 766406
49719 306082 535084 768012
61794 309478 541300 768280
68197 315992 543029 771905
76169 317527 546654 775703
78736 320702 553768 776007
83528 323287 554680 776612
85026 323841 563398 777567
90151 333189 566380 795978
90490 341102 576808 819084
92364 350076 583903 826754
94912 350464 584669 842729
98758 353054 591086 843620
110027 357629 591360 855814
112239 358879 591489 866564
114794 363255 594598 874892
118006 369254 600021 875136
121418 371936 603458 878786
124377 372344 608278 880661
132459 373825 610398 883615
152976 376348 625483 883780
155635 380315 629646 902232
160968 387869 630451 904135
175309 389398 636461 904966
176790 395408 646510 905041
188895 402549 651260 911686
194564 403834 657999 916610
212595 405208 658188 918711
220428 419923 659526 921325
226486 420380 661236 926805
234213 426247 661992 929619
236846 440091 672489 933821
242224 455672 675889 936671
244845 467172 693522 938743
246521 468744 700272 944558
249402 470666 706320 948298
260234 470791 722232 959667
260305 478824 723171 962789
270345 479702 723825 967401
271445 480863 727062 971689
271504 489897 728239 973351
273244 490452 730590 980623
276728 491163 732684 983622