A265286 Minimal number of pieces of a cake such that they can be distributed equally among k guests for any k=1,2,...,n.

1, 2, 4, 6, 9, 11, 14, 16, 19

Offset: 1

Author

Max Alekseyev, Dec 06 2015

Keywords

• nonn
• nice
• more
• hard

Comments

An equivalent formulation in terms of integers: after multiplying by the LCM of the denominators, a(n) is the minimal cardinality M of a multiset S of positive integers which can be partitioned into k multisets with equal sums for all k = 1, ..., n.

A subsidiary problem: Look at all the multisets S for a given value of n that have M = a(n) elements, and let g(n) denote the minimal value of the largest element of any such S. The initial values of g(n) for n=1..6 are 1, 1, 2, 3, 12, 10, which suggests that g(n) might equal A002944(n) = lcm{1..n}/n. Multisets associated with these values of g(n) are {1}, {1,1}, {1,1,2,2}, {1,1,1,3,3,3}, {1,2,3,5,7,8,10,12,12}, {2,2,3,4,4,5,5,7,8,10,10}. - Max Alekseyev and N. J. A. Sloane, Jan 25 2016

a(n) <= a(n-1) + n - A032742(n).

Bounds for later terms: a(10)<=22, a(11)<=28, a(12)<=30, a(13)<=42, a(14)<=49 (see dxdy.ru link).

For n>=5, a(n) >= 2n-1. This bound holds even if we restrict k to {n-2,n-1,n} only.

We could also ask about the smallest piece in any of the multisets S. For n=6, the minimum smallest piece in an 11-piece solution is 1/120, as in [1/120, 1/40, 1/30, 7/120, 3/40, 11/120, 13/120, 1/8, 17/120, 1/6, 1/6]. But this is a different question from finding g(n). - Max Alekseyev, Jan 24 2016

Examples

			For n=5, the minimal number of pieces is 9. Taking the cake size to be 1, a set of possible pieces is {1/60, 1/30, 1/20, 1/12, 7/60, 2/15, 1/6, 1/5, 1/5}, so that for 1 <= k <= 5 guests we have the following partitions:
k=1: 1/60 + 1/30 + 1/20 + 1/12 + 7/60 + 2/15 + 1/6 + 1/5 + 1/5 [ = 1 ]
k=2: 1/60 + 1/30 + 1/20 + 1/12 + 7/60 + 1/5 = 2/15 + 1/6 + 1/5 [ = 1/2 ]
k=3: 1/60 + 7/60 + 1/5 = 1/30 + 1/20 + 1/12 + 1/6 = 2/15 + 1/5 [ = 1/3 ]
k=4: 1/60 + 1/30 + 1/5 = 1/20 + 1/5 = 1/12 + 1/6 = 7/60 + 2/15 [ = 1/4 ]
k=5: 1/60 + 1/20 + 2/15 = 1/30 + 1/6 = 1/12 + 7/60 = 1/5 = 1/5 [ = 1/5 ]
Another solution for n=5 is {1/120, 1/24, 7/120, 11/120, 13/120, 17/120, 19/120, 23/120, 1/5}. Notice that denominators here are not bounded by A003418(5)=60.
Examples corresponding to the formulation in terms of multisets described in the comments:
n=1: {1},
n=2: (1,1)/2,
n=3: {1,1,2,2}/6,
n=4: {1,1,1,3,3,3}/12,
n=5: {1,2,3,5,7,8,10,12,12}/60 (as above),
n=6: {2,2,3,4,4,5,5,7,8,10,10}/60
n=7: {1,11,15,19,21,25,29,31,35,39,41,45,49,59}/420,
n=8: {17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88}/840,
n=9: {21,56,69,85,95,101,115,119,120,130,150,155,160,161,165,179,185,195,259}/2520.
		

Links

• Glinka et al., Minimal possible cardinality of a (a1,...,ak)-distributable multiset, Mathoverflow, 2015.
• Multiple authors, Discussion at dxdy.ru (in Russian)

Crossrefs

Cf. A002944, A003418.

Extensions

Values a(1)-a(9) are established at dxdy.ru (see link)

Edited by N. J. A. Sloane, Jan 25 2016