Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Ed Wall
Posts:
36
Registered:
12/3/04


Re: Combinatorics Problem
Posted:
Feb 25, 1996 1:03 AM


>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 NPComplete, 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 > Nmbers deleted
Hi Rex
Well, it took less than a second what with putting the stuff on the screen. However, I don't have the right answer it seems. Optimization probs are like that sometimes because of the algorithm. One problem might be I don't switch unless I improve an estimate. It would be interesting to see if this is indeed the problem, but probably I need to sit down and think about the math. Enclosed are my numbers.
Ed Wall
P.S. This was on an old 386 33Mhz.
First Set 50000048 983622 971689 962789 959667 933821 929619 918711 916610 902232 883615 875136 874892 843620 826754 795978 776007 768012 762929 747714 747146 732684 728239 723171 706320 675889 661992 659526 657999 630451 625483 603458 594598 591086 576808 566380 553768 541300 522265 514524 510891 490452 480863 479702 470791 455672 420380 405208 403834 387869 373825 371936 363255 353054 350076 323841 323287 306082 303653 291891 278911 273244 271445 270345 249402 242224 226486 220428 188895 160968 132459 124377 118006 98758 92364 90151 78736 49719 44789 34673 18569
Second Set 49999952 980623 973351 967401 948298 936671 926805 921325 911686 904135 883780 880661 878786 842729 819084 777567 776612 768280 766406 760202 746189 730590 727062 723825 722232 672489 661236 658188 651260 629646 610398 608278 600021 584669 583903 563398 554680 535084 534640 511926 510680 491163 489897 478824 470666 440091 426247 419923 402549 380315 376348 372344 369254 350464 341102 333189 320702 309478 301115 287872 282512 276728 271504 260305 260234 236846 234213 212595 194564 155635 152976 121418 114794 94912 90490 85026 83528 61794 43182 32701 8119



