skrivan@ssc-vax.UUCP (10/17/84)
The following is a problem I have been carrying along for many years
with little or no progress. As I reach the prime years of my life
I want to know this problem's secret (from me) solution. Help!
PROBLEM: Consider a set N of n positive integers with largest element
X. There are m = 2**n subsets (empty set included). Form
the m sums of elements of these subsets.
What is the set N with smallest X such that the m sums
are unique?
The following are some of the known solutions:
n set
_ ___________________
1 {1}
2 {1,2}
3 {1,2,4} and {2,3,4}
4 {3,5,6,7}
5 {6,9,11,12,13}
As n increases, candidate sets N can be constructed with unique sums
of subsets. However, I don't know if they are the solution sets.
Of course, I would prefer a mathematical solution for the general case.
Jim Skrivandgc@ucla-cs.UUCP (10/28/84)
------------------------------------------------------------------------
PROBLEM: Consider a set N of n positive integers with largest
element X. There are m = 2**n subsets (empty set
included). Form the m sums of elements of these
subsets.
What is the set N with smallest X such that the m sums
are unique?
------------------------------------------------------------------------
This is a well-known difficult problem. Paul Erdos has offered a prize
to anyone who can prove that X grows no faster than (I believe)
n/log log n .
2
The best published results are due to Richard Guy of the Mathematics
Department of the University of Calgary in Canada and John Conway of
Cambridge University in England, who showed, as I recall, that X is less
than
n-3
2
when n is very large.
David G. Cantor
Arpa: dgc@ucla-locus.arpa
UUCP: ...!{cepu, ihnp4, randvax, sdcrdcf, trwspp, ucbvax}!ucla-cs!dgc