Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Education » math-teach

Topic: Errors, Approximations and Combinatorics
Replies: 8   Last Post: Feb 22, 1996 11:41 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ed Wall

Posts: 36
Registered: 12/3/04
Re: Errors, Approximations and Combinatorics
Posted: Feb 22, 1996 11:41 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

> Rex said,
> I have proposed to him that I will give him 200 numbers (say 5 or 6
> digit numbers). His job is to put the numbers into 2 sets such that
> the sums of the numbers in the two sets are equal (or a close as
> possible). Is there an algorithm that will allow Shane to do this, or
> is the only method brute force? If the latter, I reckon Shane's
> Pentium could have more than 200C100 loops to run through, which is a
> very big number.
> I've been thinking about this problem in my "down time" all day and I
> think I have a fairly easy solution. Please tell me if I am being
> naive or stupid.
> First let me qualify this by saying I am not a programmer and I have
> no idea how to get a computer to do this, but as a human, how about if
> I just start listing the numbers in two groups, trying to keep the
> running sum about equal, until I get all the numbers listed. Let's
> say when I get done group 1 has a sum that is 1238 more than group 2.
> Can't I then start on a new task of finding two numbers (one from each
> group) which differ by 619? If I switch those two the result will be
> two equal stacks. If I can't find two such numbers, I should at least
> be able to narrow the gap. I see that this might take a while and
> that I won't always be able to find numbers to narrow the gap, but I
> could at least keep it reasonable until I get a gap that can be fixed
> exactly. Yes this is inefficient, but is there a quicker way? And
> how about it hackers, can we write a program to do this?
> Sam Evers
> University of Alabama

Here is a hack in C. I could have done it in some other language, but I'm a bit
rusty in C right now. Note I make a simplification that one pile can essentially
be held larger and you need to introduce a zero number to one switch - sort of
like zen :-)

Some speed improvements would be to sort each pile so you could break out of
comparisons when obvious.

I think I understood Sam's logic and it seems that one could even show that
this thing might converge.

#include <stdio.h>

#define N 26

int n[N+1];
int sum1, sum2, max1, max2;
int set1[N+1], set2[N+1];

void main()
int i, j, s, min, tmin, newtmin;
int sitcheroo();

/* Set your numbers here. A kludge because I'm lazy. BTW these are the */
/* first 26 primes and if you put one in the set then you can get equal */
/* partitions */

n[1]=97; n[2]=89; n[3]=83; n[4]=79; n[5]=73; n[6]=71;
n[7]=67; n[8]=67; n[9]=61; n[10]=59; n[11]=53; n[12]=47;
n[13]=43; n[14]=41; n[15]=37; n[16]=31; n[17]=29; n[18]=23;
n[19]=19; n[20]=17; n[21]=13; n[22]=11; n[23]=7; n[24]=5;
n[25]=3; n[26]=2;

/* Assume n[1] is the largest number to be considered */


for (i=2;i<=N;i++) {
if (sum2 < sum1) {
sum2 = sum2 +n[i];
set2[max2++] = i;
else {
sum1 = sum1 + n[i];
set1[max1++] = i;

if (sum1 <sum2) {

/* Thus we can assume sum1 >= sum2 */
min = sum1 - sum2;
if (min!=0) {
tmin = min/2;

while (newtmin>tmin) {
printf("First Set %d\n",sum1);
for (i=1;i<max1;i++) printf("%d\n",n[set1[i]]);
printf("\n\nSecond Set %d\n",sum2);
for (i=1;i<max2;i++) printf("%d\n",n[set2[i]]);

int switcheroo(tmin)
int tmin;
int i, j, k, s, smax, temp;
int besti, bestj;

for (i=1;i<max1;i++) {
for (j=0;j<max2;j++) {
if (s>0) {
if (s<=tmin) {
if (s>smax) {
if (bestj==0) {
if (besti!=0) {
for (k=besti+1;k<max1;k++) set1[k-1]=set1[k];
else {

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum 1994-2015. All Rights Reserved.