Partition-related sequence

[franktaw at netscape.net]

a(5) = 9, and a(6) = 11.  This means that my conjecture that A002088 is 
optimal is wrong.

9 can be achieved for n = 5 with the partition [3,4,5,6,6,7,8,9,12].  
This
partitions for k = 5 into [12], [3,9], [4,8], [5,7], and [6,6]; for k = 
4 into
[3,12], [6,9], [7,8], and [4,5,6]; and for k = 3 into [8,12], [5,6,9], 
and
[3,4,6,7].

(Note that it is only necessary to consider k > floor(n/2), since any 
sub-
partition for 2k can be changed into a partition of k by arbitrarily 
combining
pairs.)

To achieve 11 parts with n = 6, note that in the given partition for n 
= 5,
k = 3, one of the parts ([3,4,6,7]) can be split in half.  We can then 
split
one number in each of the other two parts so that they can be split in
half: the 12 must be split into 10 and 2, and we can choose one of
splitting 9 into 4 and 5, 6 into 1 and 5, or 5 into 1 and 4.  
Arbitrarily taking
the first of these, we get [2,3,4,4,5,5,6,6,7,8,10] as a solution.

To show that 9 and 11 are minimal, we first establish a general lower
bound a(n) >= 2n-2.  This is a bit easier to explicate using the 
fractional
form of the problem, which I will use for the remainder of this note.
(A multiset of positive fractions, such that for k = 1..n, it is 
possible to
partition them into k submultisets, each summing to 1/k.  This is 
easily
converted to a multiset of integers by multiplying by the lcm of the
divisors; and conversely by dividing by the sum of the multiset.)  The
proof is pretty trivial:

Because the multiset can be partitioned into n parts, each totaling 
1/n, it
follows that no fraction can be greater than 1/n.  In particular, each 
part
must be less than 1/(n-1), so the partition into n-1 parts must have at
least 2 numbers in each part, for a total of at least 2(n-1), as 
claimed.

This immediately shows that David's values for n = 2, 3, and 4 are 
optimal.
(And of course a(1) = 1 is obvious.)

I can then almost prove that for n > 4, 2n-1 is a lower bound.  The
necessary lemma is that in any partition into 2(n-1) = 2n-2 parts, all 
the
parts must be integer multiples of 1/(n(n-1)).  But for n > 4, the 
split into
n-2 parts is then impossible, since (1/(n-2))/(1/(n(n-1))) = 
(n(n-1))/(n-2)
= n + n/(n-2) is not an integer when n > 4.

To achieve 2n-2 parts, the partition into n-1 parts must consist 
entirely of
parts of size 2, and the partition into n parts must include at least 
two
parts of size 1.  A part of size one must be [1/n].  Looking at the 
partition
into n-2 parts, this forces the same number of fractions of size 
1/(n(n-1)).
In the simplest case, where there are only 2 parts of size 1, the 
remaining
parts of the partition into n parts must consist of parts of size 2, so 
we
are now forced to have two fractions (n-2)/(n(n-1)).  This continues
back and forth until we wind up with determining the last 2 parts as
1/(2n) for n odd and 1/(2(n-1)) for n even.

When there are m > 2 parts of size 1 in the partition into n parts, we 
first
need to choose what the remaining part sizes will be.  There are then
forced to be m fractions 1/(n(n-1)).  Filling these in to the partition 
of
size n, at least 2 parts will be filled to all but one number; the 
remaining
numbers in these parts are then determined and are multiples of
1/(n(n-1)).  They are also too small to make up a part in the n-1 
partition,
so two more multiples of 1/(n(n-1)) are determined there.  These are
too big to fit into 1 part in the n partition, so now two more 
fractions
are determined.  Continuing back and forth this way should determine 
all
the fractions.  If it is ever possible to use the two fractions thus 
generated
to fill a part, the process stops with some values still undetermined; 
this is
the point that I am unable to prove.

I have, however, examined all cases for n = 5 and n = 6, and found that
9 and 11 are not possible for them.  Together with the examples given
above, this shows that a(5) = 9 and a(6) = 11.

Searching for 2,4,6,9,11 in the OEIS gives 16 matches, none of which
are in any way related to this question.  So the sequence is not there.

Franklin T. Adams-Watters

-----Original Message-----
From: David Wilson <davidwwilson at comcast.net>

What I am looking for is a multiset of integers that can be partitioned 
into
k equal-sum multisets for k = 1, 2, 3, ..., n.

a(1) = 1 with optimal multiset [1] having partitions [[1]]
a(2) = 2 with optimal multiset [1 1] which partitions into [[1 1]] and 
[[1] [1]]
a(3) = 4 with optimal multiset [1 1 2 2] with partitions
   [[1 1 2 2]],  [[1 2][1 2]]  and  [[1 1] [2] [2]]
a(4) = 6 with optimal multiset [1 1 2 2 3 3] and partitions
    [[1 1 2 2 3 3]],  [[1 1 2 2] [3 3]],  [[1 3] [1 3] [2 2]]  and  [[1 
2] [1 2] [3] [3]]

I don't think you can do better for n = 1..4.

a(5) <= 10 with candidate optimal multiset [3 3 4 4 5 5 6 6 12 12]. 
This
multiset can be partitioned into 1, 2, 3, 4 or 5 equal-sum sets. I 
don't
know if there is a better set, but I doubt a(5) = 7 is achievable.

________________________________________________________________________
More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com



Dear Yasutoshi,  Before I add that sequence to the OEIS,
could you please tell me how G_n is defined?  The rule
is not clear to me!  G_1 and G_2 have 4-fold symmetry,
but G_3 does not.

Thanks






Dear prime aficionados: Any ideas why A049591 and A105399 are essentially the
perhaps also in A105792...
Is A133387 essentially a stuttering version which resumes one of these
after removal of duplicates?

Richard
http://www.strw.leidenuniv.nl/~mathar