Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Easiest Hard Problem (2002)

americanscientist.org

Post reply on HN
Print view View original

21–30 of 34 posts

Re: The Easiest Hard Problem (2002)

#21

Post by crystalmeph »

vog wrote: post #5
Strilanc wrote: post #3

Earlier quoted context omitted.

Why is it easy to prove that this particular set of numbers can be broken into equal subsets?

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

Regarding item 1, yes there are 2^90 ways to choose one subset, but since you are comparing two separate subsets, those subsets can't overlap (or else you could just choose the same subset twice!), so it seems like there should be "more" to this calculation? Am I missing something here?

Edit: wait I think I've got it:

Each subset implicitly also chooses it's counter subset, e.g. if you choose the subset consisting of the first 45 numbers, you've also therefore said the other subset consists of the last 45 numbers. Since there are more of these "dual subsets" than possible sums, the pigeonhole principle yadda-yadda.

Re: The Easiest Hard Problem (2002)

#22

Post by harryjo »

phkahler wrote: post #18

Here's an interesting partitioning problem: Split the first N primes into 2 groups such that the difference of products is as small as possible but not 1. If this number is less than the square of the Nth prime, it will be prime. For example: split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7. split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5)…

What's the largest example you have verified?

Re: The Easiest Hard Problem (2002)

#23

Post by harryjo »

vog wrote: post #5
Strilanc wrote: post #3

Earlier quoted context omitted.

Why is it easy to prove that this particular set of numbers can be broken into equal subsets?

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

The number of partitions is 2^90 / 2, since each partition has 2 representations. (The rest of the proof still holds.)

Re: The Easiest Hard Problem (2002)

#24

Post by harryjo »

vog wrote: post #9
malnourish wrote: post #7

At first his language was a little confusing -- when I saw "set" and then saw two 2s listed in his set. Are "set" and "multiset" often this interchangeable?

No, they aren't. This is just sloppy wording in the article. The concept of sets is deeply established in mathematics and when you talk about multisets rather than sets you have to state this explicitly.

In this, case, it's trivial to word the problem a "sets of objects, each with integer size, partition into sets of equal sum size". It is still polite to state that explicitly outside of the sample data, though.

Re: The Easiest Hard Problem (2002)

#25

Post by vog »

crystalmeph wrote: post #21
vog wrote: post #5

Earlier quoted context omitted.

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

Regarding item 1, yes there are 2^90 ways to choose one subset, but since you are comparing two separate subsets, those subsets can't overlap (or else you could just choose the same subset twice!), so it seems like there should be "more" to this calculation? Am I missing something here? Edit: wait I think I've got it: Each subset implicitly also chooses it's counter subset, e.g. if you choose the subset consisting of…

I'm think you misunderstood the question.

You are not forced to use all numbers. (And in fact, my explicit solution doesn't use all numbers.) There is no restriction that the union of both subsets must be equal to the full set. Note that this restriction would change the question dramatically. See also: https://news.ycombinator.com/item?id=10023098

Also note that it is allowed for both chosen subsets to overlap. In fact, the proof just says that two different (i.e. not entirely equal) subsets with the same sum exist.

However, once you have a pair of different overlapping subsets of the same sum, you can simply remove the intersection from both sets. Both sums decrease by the same amount. You then get a pair of two disjoint sets that have the same sum.

Re: The Easiest Hard Problem (2002)

#26

Post by vog »

harryjo wrote: post #23
vog wrote: post #5

Earlier quoted context omitted.

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

The number of partitions is 2^90 / 2, since each partition has 2 representations. (The rest of the proof still holds.)

You misunderstood the question. This is not about partitions. The union of the subsets is not required to be the full set. See also: https://news.ycombinator.com/item?id=10023034

And no, I don't think the proof would not work when requiring the two subsets to form a partition. Also note that for partitions, the number of sums would be one, as the only possible sum is half of the sum of all numbers. (And the problem would be unsolvable if the sum of all numbers was odd, but all numbers were still integers.)

Re: The Easiest Hard Problem (2002)

#28

Post by Strilanc »

vog wrote: post #5
Strilanc wrote: post #3

Earlier quoted context omitted.

Why is it easy to prove that this particular set of numbers can be broken into equal subsets?

You just have to compare the number of subsets with the number of possible sum values. 1) There are 90 numbers, so we have 2^90 subsets. 2) All numbers are Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum. BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

Ah, of course.

(I didn't realize you were allowed to use each number in both subsets, so I have no idea if I would have figured it out or not on my own.)

Re: The Easiest Hard Problem (2002)

#30

Post by phkahler »

harryjo wrote: post #22
phkahler wrote: post #18

Here's an interesting partitioning problem: Split the first N primes into 2 groups such that the difference of products is as small as possible but not 1. If this number is less than the square of the Nth prime, it will be prime. For example: split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7. split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5)…

What's the largest example you have verified?

>> What's the largest example you have verified?

I don't recall. I don't think I went beyond the use of 32bit integers (or was it 64) when I first looked at it, so not very large. The intermediate products can get quite big quickly. I do remember using a binary number to represent group membership of each prime, and seeing a pattern that broke down after only a few primes.

Post reply on HN