The Easiest Hard Problem (2002)
americanscientist.org
The Easiest Hard Problem (2002)
1–10 of 34 posts
Re: The Easiest Hard Problem (2002)
#2This reminds me of a challenge at the Free University Berlin. A lecturer gave the following list of numbers to his students. The task was to find two different subsets that have the same sum:
http://www.inf.fu-berlin.de/lehre/WS07/mafi1/90zahlen.txt
His point was: It it simple to prove that those subsets must exist, but it is very hard to compute them. To make his point even more clear, he offered some prize money if anyone found an explicit solution.
A friend told me about that challenge, and I tried. With a lot of conceptual work, programming, optimization and some luck I was finally able find such a solution (and received the prize):
(Sorry, German language, but the solution is readable, I guess :-))
Re: The Easiest Hard Problem (2002)
#3This reminds me of a challenge at the Free University Berlin. A lecturer gave the following list of numbers to his students. The task was to find two different subsets that have the same sum: http://www.inf.fu-berlin.de/lehre/WS07/mafi1/90zahlen.txt His point was: It it simple to prove that those subsets must exist, but it is very hard to compute them. To make his point even more clear, he offered some prize money if…
Why is it easy to prove that this particular set of numbers can be broken into equal subsets?
Re: The Easiest Hard Problem (2002)
#4This reminds me of a challenge at the Free University Berlin. A lecturer gave the following list of numbers to his students. The task was to find two different subsets that have the same sum: http://www.inf.fu-berlin.de/lehre/WS07/mafi1/90zahlen.txt His point was: It it simple to prove that those subsets must exist, but it is very hard to compute them. To make his point even more clear, he offered some prize money if…
Why is it easy to prove that this particular set of numbers can be broken into equal subsets?
Given the subsets it is easy to verify the subsets come from the set and their sum is the same. Finding them is hard.
Re: The Easiest Hard Problem (2002)
#5This reminds me of a challenge at the Free University Berlin. A lecturer gave the following list of numbers to his students. The task was to find two different subsets that have the same sum: http://www.inf.fu-berlin.de/lehre/WS07/mafi1/90zahlen.txt His point was: It it simple to prove that those subsets must exist, but it is very hard to compute them. To make his point even more clear, he offered some prize money if…
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
Re: The Easiest Hard Problem (2002)
#6Re: The Easiest Hard Problem (2002)
#7At 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?
Re: The Easiest Hard Problem (2002)
#8Earlier 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
[deleted]
Re: The Easiest Hard Problem (2002)
#9At 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.