| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
From: ROLL::USENET "USENET Newsgroup Distributor" 1-NOV-1984 00:44
To: HARE::STAN
Subj: USENET net.puzzle newsgroup articles
Newsgroups: net.puzzle
Path: decwrl!decvax!mcnc!akgua!sdcsvax!sdcrdcf!trwrba!cepu!ucla-cs!dgc
Subject: Re: Sums of Subsets Problem
Posted: Sun Oct 28 10:09:19 1984
------------------------------------------------------------------------
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: [email protected]
UUCP: ...!{cepu, ihnp4, randvax, sdcrdcf, trwspp, ucbvax}!ucla-cs!dgc
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 174.1 | I don't get it | GUMDRP::HAINSWORTH | Shoes and ships and sealing wax | Fri Apr 17 1987 17:49 | 22 |
I think I'm not reading the problem right, so I'd like to request
clarification.
n
The way I see it, if the 2 subsets must have unique sums, then
the smallest possible set of SUMS is going to be
n
SUMS(N) = { 0,1,2,3,...2 -1 }
A set that produces this set of sums is
n-1
N = { 1,2,4,8...2 }
n-1
With X = 2 . It would help me greatly in visualizing this problem
if someone could show me a better set (one with a smaller X value)
for some reasonably small value of n.
Thanks!
John
| |||||
| 174.2 | CLT::GILBERT | eager like a child | Fri Apr 17 1987 18:36 | 9 | |
Who said you wanted the smallest possible set of SUMS?
You considered { 1,2,4,8,16,32 }. Consider the set { 4,b,c,d,e,31 },
which generates unique sums. Sure, some sums may be *larger* than 63,
but the point is to minimize X, the largest value in the set.
P.S. It took me a while to finally understand the problem, and I've yet
to find some example that improves on the X = 2^(n-1) approach, but I
thought the above would help.
| |||||
| 174.3 | CLT::GILBERT | eager like a child | Fri Apr 17 1987 20:06 | 16 | |
For n = 1, 2, 3, 4, 5, and 6, the following sets minimize X (the largest
element in the set).
{ 1 }
{ 1,2 }
{ 1,2,4 }
{ 2,3,4 }
{ 3,5,6,7 }
{ 3,6,11,12,13 }
{ 6,9,11,12,13 }
{ 11,17,20,22,23,24 }
| |||||
| 174.4 | MUNICH::CLINCH | Life begins at... (muffled thump) | Tue Apr 21 1987 07:12 | 7 | |
Answer {1}
(The one is the smallest positive integer and the sum 1 is unique)
So what is wrong with my understanding of the problem?
Simon.
| |||||
| 174.5 | CLT::GILBERT | eager like a child | Tue Apr 21 1987 11:45 | 2 | |
The number of elements in the set is given; it's the members of
the set that must be chosen.
| |||||