Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site ucla-cs.ARPA
Path: utzoo!watmath!clyde!bonnie!akgua!sdcsvax!sdcrdcf!trwrba!cepu!ucla-cs!dgc
From: dgc@ucla-cs.UUCP
Newsgroups: net.puzzle
Subject: Re: Sums of Subsets Problem
Message-ID: <1872@ucla-cs.ARPA>
Date: Sun, 28-Oct-84 13:09:19 EST
Article-I.D.: ucla-cs.1872
Posted: Sun Oct 28 13:09:19 1984
Date-Received: Wed, 31-Oct-84 00:58:55 EST
References: <157@ssc-vax.UUCP>
Distribution: net
Organization: UCLA CS Dept.
Lines: 29

------------------------------------------------------------------------
        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