Philosophy Now Forum

You can read about it in the Scientific American, it´s by Brian Hayes.

If we have a big number of numbers how to divide them so that the two groups are equal ?

It seems that the algorithm for this has not been found yet.

My suggestion:

Make a sum of all numbers, divide in half.
If the number is straight then good, if not then it´s not too bad.
Let´s call this number the aim number.

Then add the first two numbers and try to find if any of the remaining numbers fills the gap between this preliminary sum and the aim number.
If not, add one more and see again.

It´s not perfect yet, but what do you think ?
It´s better than the greedy algorithm, isn´t it ?

5, 24, 598, 6, 29, 30

Sum: 692
half: 346

5 + 24 = 26
gap between 26 and 346 = 320

but 598 is sticking out as too big

An extra algorithm should find out that there is no solution because one number is bigger than the half of all of them.

Some points:

It would be good if you can provide a link to that article.

You have to be more specific. When you say to divide up the list of numbers so that the groups are equal, equal in what way? Also 5 + 24 = 29, not 26.

PhilX

I don´t know how to provide a link but if you google "the easiest hard problem Scientific American" you will get it. It worked for me yesterday.

Even without reading the article I put everything in a nutshell for you.

You are right about 24 plus 5. But the idea is still clear I hope.

We did partition when we were young: two strongest bullies picked their teams by taking the best players first, one by one. That´s the greedy algorithm: it takes the largest numbers first, the both sets taking turns.

Equal in number if you add the numbers in both sets.

Example: there is a whole lot of assets differing in value, how to distribute them among two parties equally ?

duszek wrote:I don´t know how to provide a link but if you google "the easiest hard problem Scientific American" you will get it. It worked for me yesterday.

Even without reading the article I put everything in a nutshell for you.

You are right about 24 plus 5. But the idea is still clear I hope.

We did partition when we were young: two strongest bullies picked their teams by taking the best players first, one by one. That´s the greedy algorithm: it takes the largest numbers first, the both sets taking turns.

Equal in number if you add the numbers in both sets.

Example: there is a whole lot of assets differing in value, how to distribute them among two parties equally ?

Have you ever tried to work this out by computer? Not hard to understand, but could be tedious.

PhilX

In number or total values?

Total values, yes, that must be the correct term, thank you.

So on one side we can have

25, 125, 50

and on the other 195 and 5.

The problem seems to be that a computer program needs to try all combinations and that means that the number of tries rises exponentially. So a computer is stuck for an eternity.

I would start by calculating the half of the total value of all integers and then I would check if any integer is higher than this.