|
| |
|
|
A259544
|
|
Minimum greatest integer in a set of n positive integers whose nonempty subsets all have distinct arithmetic means.
|
|
3
|
| |
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Let a set of integers be called "of different average" if any two distinct, nonempty subsets of it have distinct arithmetic means. E.g., the set {1,2,5} is of different average because 1 != 2 != 5 != (1+2)/2 != (1+5)/2 != (2+5)/2 != (1+2+5)/3.
In order for a set to be of different average it is obvious that all its elements must be different. Also, if a set is of different average and a constant k is added to all the terms, the resulting set will also be of different average. Because of this, in order to study such sets it is convenient to select an arbitrary first element, say 1. Therefore the terms of this sequence are defined as: the least a_n such that the set 1 = a_1 < a_2 < a_3 < ... < a_n is of different average.
The set {1,2,4,...,2^(n-1)} satisfies that any natural number can only be written in one way as a sum of elements of the set (each element being allowed to enter only once into the sum), so it is a good candidate as a different average set, and it is so up to 1,2,4,8,16,32, but it fails for 1,...,64, since (4+8+16+64)/4 = (1+2+16+32+64)/5 = 23. Other than by brute force, this can easily be found by noting that the number 23, written in binary notation: 10111, has four ones, hence 4 times the number obviously has four ones too, while 5 times the number = 1110011 has five ones, and those are the subsets.
Conjecture: The only term that is < 2^(n-1) is a(4)=7.
It may be proved that, for n>1, a(n) < 4^(n-1):
Suppose we already have a set of n-1 numbers satisfying the property. If an element a_n is added, 2^n possible sets can be formed, hence fewer than 2^n * 2^n / 2 = 4^n/2 pairs of sets. If a certain value of a_n gives the same average for two such subsets, any other value will yield different averages. It is easy to see that only half the pairs need be considered; hence there is at least one value of a_n < 4^(n-1) that yields different averages for all pairs of subsets.
If more set pairs are excluded, viz. sets that both include a_n and that either have the same number of elements (because the set a_1,...,a_(n-1) is presumed to already satisfy the property) or the set having more elements has a lower average than the other with a_n excluded from both (a_n will eventually be greater than all the other a_i; if not, interchange the a_n found with one of the a_i and "run" the reasoning again), the 4^(n-1) bound may be improved slightly. Note that the latter property of set pairs is transitive, in the sense that if any such pair satisfies the property, the pair formed by adding a_n to both sets also satisfies the property.
What is lim_sup a(n)^(1/n)? The upper bound above proves it is <=4.
Conjecture: lim a(n)/2^n = infinity. (Note that this is weaker than lim_inf a(n)^(1/n) > 2.)
Does lim a(n)^(1/n) exist?
A259545 provides the values of N such that all k>=N can be the greatest element of a different average set of n elements.
A set of different average with n elements has A001405(n) ~ 2^n * sqrt(2/(Pi*n)) subsets of size floor(n/2) which must have different sums, so the largest such sum is at least A001405(n), and thus the largest element is at least A001405(n)*2/n. This shows that lim inf a(n)^(1/n) >= 2. - Robert Israel, Aug 02 2015
a(10) <= 1303, as shown by the example {1, 43, 151, 235, 421, 981, 1093, 1161, 1266, 1303}. - Robert Israel, Jan 20 2016
a(10) <= 1252, as shown by the example {1, 76, 181, 211, 293, 727, 1126, 1196, 1216, 1252}. - Robert Israel, Jan 25 2016
Changing this sequence's requirement of "distinct arithmetic means" to "distinct sums" gives sequence A276661. - Jon E. Schoenfield, Nov 05 2016
|
|
|
LINKS
|
Javier Múgica, medias.c. A program for finding a(n). medias10.c. The same as the previous program, except that set up for checking a particular value for 10-element different average sets.
|
|
|
FORMULA
|
a(n) < 4^(n-1) for n > 1, see comments.
|
|
|
EXAMPLE
|
The 15 averages of 1 to 4 elements in the set {1, 2, 5, 7} (or alternately {1, 3, 6, 7}) are all different, so a(4) <= 7. There are no such sets of 4 positive integers with all members less than 7, so in fact a(4) = 7.
The set providing the last term at present in the sequence, viz. 396 = a(9), is {1, 13, 21, 51, 151, 327, 336, 342, 396} (or, by symmetry, {1, 55, 61, 70, 246, 346, 376, 384, 396}).
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more,hard,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
