[seqfan] a nice sequence related to cake cutting

Max Alekseyev maxale at gmail.com
Sun Dec 6 21:30:17 CET 2015


SeqFans,

I'd like to draw your attention to a nice sequence https://oeis.org/A265286
(currently in a draft form) concerning the minimal number of pieces (of
varying sizes) one need to cut a cake to be able to equally distribute them
among k guest for any k=1,2,...,n.

Here is an example for n=5, when the minimum is A265286(5)=9. Taking the
cake size equal 1, the pieces can be taken of sizes {1/60, 1/30, 1/20,
1/12, 7/60, 2/15, 1/6, 1/5, 1/5} so that for k=1,2,...,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 ]

Extension and improvements are welcome.

P.S. I have a MILP-program (actually, even two such programs) for this
problem, which I described at
http://mathoverflow.net/questions/214477/minimal-possible-cardinality-of-a-a-1-a-k-distributable-multiset
but it's not efficient for large n.

Regards,
Max



More information about the SeqFan mailing list