|
%I #84 Sep 22 2020 17:16:25
%S 1,2,4,6,9,11,14,16,19
%N Minimal number of pieces of a cake such that they can be distributed equally among k guests for any k=1,2,...,n.
%C 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.
%C 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
%C a(n) <= a(n-1) + n - A032742(n).
%C Bounds for later terms: a(10)<=22, a(11)<=28, a(12)<=30, a(13)<=42, a(14)<=49 (see dxdy.ru link).
%C For n>=5, a(n) >= 2n-1. This bound holds even if we restrict k to {n-2,n-1,n} only.
%C 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
%H Glinka et al., <a href="http://mathoverflow.net/questions/214477/minimal-possible-cardinality-of-a-a-1-a-k-distributable-multiset">Minimal possible cardinality of a (a1,...,ak)-distributable multiset</a>, Mathoverflow, 2015.
%H Multiple authors, <a href="http://dxdy.ru/topic102739.html">Discussion at dxdy.ru</a> (in Russian)
%e 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:
%e k=1: 1/60 + 1/30 + 1/20 + 1/12 + 7/60 + 2/15 + 1/6 + 1/5 + 1/5 [ = 1 ]
%e k=2: 1/60 + 1/30 + 1/20 + 1/12 + 7/60 + 1/5 = 2/15 + 1/6 + 1/5 [ = 1/2 ]
%e k=3: 1/60 + 7/60 + 1/5 = 1/30 + 1/20 + 1/12 + 1/6 = 2/15 + 1/5 [ = 1/3 ]
%e k=4: 1/60 + 1/30 + 1/5 = 1/20 + 1/5 = 1/12 + 1/6 = 7/60 + 2/15 [ = 1/4 ]
%e k=5: 1/60 + 1/20 + 2/15 = 1/30 + 1/6 = 1/12 + 7/60 = 1/5 = 1/5 [ = 1/5 ]
%e 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.
%e Examples corresponding to the formulation in terms of multisets described in the comments:
%e n=1: {1},
%e n=2: (1,1)/2,
%e n=3: {1,1,2,2}/6,
%e n=4: {1,1,1,3,3,3}/12,
%e n=5: {1,2,3,5,7,8,10,12,12}/60 (as above),
%e n=6: {2,2,3,4,4,5,5,7,8,10,10}/60
%e n=7: {1,11,15,19,21,25,29,31,35,39,41,45,49,59}/420,
%e n=8: {17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88}/840,
%e n=9: {21,56,69,85,95,101,115,119,120,130,150,155,160,161,165,179,185,195,259}/2520.
%Y Cf. A002944, A003418.
%K nonn,nice,more,hard
%O 1,2
%A _Max Alekseyev_, Dec 06 2015
%E Values a(1)-a(9) are established at dxdy.ru (see link)
%E Edited by _N. J. A. Sloane_, Jan 25 2016
|
