6 ms·

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

by Strilanc 11y ago

unlikelymordant 11y ago
Given the subsets it is easy to verify the subsets come from the set and their sum is the same. Finding them is hard.
- deleted 11y ago
  [deleted]
- deleted 11y ago
  [deleted]
- vog 11y ago
  I'm afraid you missed the point.
vog 11y ago
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 < 10^25, so the sum of all 90 numbers is < 90 * 10^25 < 10^27. So each sum of a subset is an integer in the range of 0 to 10^27-1. So we have ≤ 10^27 possible sum values. 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 https://en.wikipedia.org/wiki/Pigeonhole_principle
- deleted 11y ago
  [deleted]
- noobie 11y ago
  > The sum of all 90 numbers is < 2^89 Why? (Obviously you wouldn't compute it so what's the "trick"?)
  - SilasX 11y ago
    The sum of 90 numbers in this context is considered to be easy (esp relative to finding the sum of many possible subsets).
    - vog 11y ago
      That's true. However, it is also easy to estimate that sum rather than calculating it exactly, so I adjusted my proof accordingly.
- crystalmeph 11y ago
  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.
  - vog 11y ago
    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 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.
- harryjo 11y ago
  The number of partitions is 2^90 / 2, since each partition has 2 representations. (The rest of the proof still holds.)
  - vog 11y ago
    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 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.)
- Strilanc 11y ago
  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.)

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

unlikelymordant 11y ago

Given the subsets it is easy to verify the subsets come from the set and their sum is the same. Finding them is hard.

deleted 11y ago
[deleted]
deleted 11y ago
[deleted]
vog 11y ago
I'm afraid you missed the point.

vog 11y ago

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 < 10^25, so the sum of all 90 numbers is < 90 * 10^25 < 10^27. So each sum of a subset is an integer in the range of 0 to 10^27-1. So we have ≤ 10^27 possible sum values. 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 https://en.wikipedia.org/wiki/Pigeonhole_principle

deleted 11y ago
[deleted]
noobie 11y ago
> The sum of all 90 numbers is < 2^89 Why? (Obviously you wouldn't compute it so what's the "trick"?)
- SilasX 11y ago
  The sum of 90 numbers in this context is considered to be easy (esp relative to finding the sum of many possible subsets).
  - vog 11y ago
    That's true. However, it is also easy to estimate that sum rather than calculating it exactly, so I adjusted my proof accordingly.
crystalmeph 11y ago
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.
- vog 11y ago
  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 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.
harryjo 11y ago
The number of partitions is 2^90 / 2, since each partition has 2 representations. (The rest of the proof still holds.)
- vog 11y ago
  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 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.)
Strilanc 11y ago
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.)