|
|
A201052
|
|
a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.
|
|
4
|
|
|
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
In the count 2^c of the cardinality of subsets of a set with cardinality c, the empty set - with sum 0 - is included; 2^c is just the row sum of the c-th row in the Pascal triangle.
|
|
LINKS
|
|
|
EXAMPLE
|
Numbers n and an example of a subset of {1..n} exhibiting the maximum cardinality c=a(n):
1, {1}
2, {1, 2}
3, {1, 2}
4, {1, 2, 4}
5, {1, 2, 4}
6, {1, 2, 4}
7, {3, 5, 6, 7}
8, {1, 2, 4, 8}
9, {1, 2, 4, 8}
10, {1, 2, 4, 8}
11, {1, 2, 4, 8}
12, {1, 2, 4, 8}
13, {3, 6, 11, 12, 13}
14, {1, 6, 10, 12, 14}
15, {1, 6, 10, 12, 14}
16, {1, 2, 4, 8, 16}
17, {1, 2, 4, 8, 16}
18, {1, 2, 4, 8, 16}
For examples of maximum-cardinality subsets at values of n where a(n) > a(n-1), see A096858. - Jon E. Schoenfield, Nov 28 2013
|
|
MAPLE
|
# is any subset of L uniquely determined by its total weight?
iswts := proc(L)
local wtset, s, c, subL, thiswt ;
# the weight sums are to be unique, so sufficient to remember the set
wtset := {} ;
# loop over all subsets of weights generated by L
for s from 1 to nops(L) do
c := combinat[choose](L, s) ;
for subL in c do
# compute the weight sum in this subset
thiswt := add(i, i=subL) ;
# if this weight sum already appeared: not a candidate
if thiswt in wtset then
return false;
else
wtset := wtset union {thiswt} ;
end if;
end do:
end do:
# All different subset weights were different: success
return true;
end proc:
# main sequence: given grams 1 to n, determine a subset L
# such that each subset of this subset has a different sum.
wts := proc(n)
local s, c, L ;
# select sizes from n (largest size first) down to 1,
# so the largest is detected first as required by the puzzle.
for s from n to 1 by -1 do
# all combinations of subsets of s different grams
c := combinat[choose]([seq(i, i=1..n)], s) ;
for L in c do
# check if any of these meets the requir, print if yes
# and return
if iswts(L) then
print(n, L) ;
return nops(L) ;
end if;
end do:
end do:
print(n, "-") ;
end proc:
# loop for weights with maximum n
for n from 1 do
wts(n) ;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|