[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

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

1578.0. "Unique sums and minimal totals" by ULTIMA::GARYB (There's no game like the present...) Thu Mar 05 1992 21:46

Recently I stumbled across a curious problem while pondering about pattern
matching.  Given a number N, construct a set S of N positive integers such that
all subsets of S have unique sums and the sum of S is as small as possible.

One obvious set of numbers to try is 2^0..2^(N-1) whose sum is 2^N - 1. But
sets with smaller totals can be found.

A number of questions arise such as what's the best method for finding the set
S and what sorts of upper and lower bounds can be calculated that are more
interesting than 2^N - 1?

I have a vague feeling that this problem is a redressing of something I've
seen before but I can't put my finger on it.

-Gary

T.R	Title	User	Personal Name	Date	Lines
1578.1		CLT::TRACE::GILBERT	Ownership Obligates	`Fri Mar 06 1992 19:00`	1
	Perhaps you're reminded of Golomb Rulers, note 382.
1578.2	Misquoted problem, methinks	TRACE::GILBERT	Ownership Obligates	`Sun Mar 08 1992 21:36`	11
	>Given a number N, construct a set S of N positive integers such that >all subsets of S have unique sums and the sum of S is as small as possible. >One obvious set of numbers to try is 2^0..2^(N-1) whose sum is 2^N - 1. But >sets with smaller totals can be found. The set S = {2^0,..,2^(N-1)} looks pretty good to me. Suppose there is some other set S' of N positive integers whose subsets have 2^N unique sums (we allow the empty subset with sum 0). The largest sum is >= 2^N-1, otherwise the pigeonhole principle would say they're not all unique. But the largest sum is just the sum of the elements in S'. So, the sum of S' >= 2^N-1 = sum of S. Thus, there are no sets with smaller sums.
1578.3		ULTIMA::GARYB	There's no game like the present...	`Tue Mar 24 1992 17:28`	12
	>>Given a number N, construct a set S of N positive integers such that >>all subsets of S have unique sums and the sum of S is as small as possible. >>One obvious set of numbers to try is 2^0..2^(N-1) whose sum is 2^N - 1. But >>sets with smaller totals can be found. > >The set S = {2^0,..,2^(N-1)} looks pretty good to me. Suppose there is some Yes, you're right. Actually all I care about are small subsets of S having unique sums. Small means subsets with sizes <= M and M is small in relation to N (10*M <= N). -Gary