|
| |
|
|
A265286
|
|
Minimal number of pieces of a cake such that they can be distributed equally among k guests for any k=1,2,...,n.
|
|
0
|
| |
|
|
|
OFFSET
|
1,2
|
|
|
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
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
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,more,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Values a(1)-a(9) are established at dxdy.ru (see link)
|
|
|
STATUS
|
approved
|
| |
|
|
