This email sent to me by Warren Smith a few days ago may be of interest (especially the discussion of the inequalities that govern what Warren calls "variant 1"). ---------- Forwarded message ---------- From: *Warren D Smith* <warren.wds@gmail.com> Date: Friday, December 15, 2017 Subject: Cutting a pie to share equally among up to n people To: jamespropp@gmail.com On 12/15/17, James Propp <jamespropp@gmail.com> wrote:
Suppose we want to make cuts in a circular pie (the usual kind of cut, from the center to a point on the perimeter) in such a way that, for every k between 1 and n, the pieces can be divided equally among k people, each of whom gets the same amount of pie.
How many cuts are needed?
--it is better to think of one the perimeter of the circle not its interior. Call your version variant 1. Variants of this problem: 2. suppose the k people all have different preferences (Amy likes pepperoni 3 times as much as she likes onions, Tom hates both but likes mushrooms...) and we want the divvying out of the pie to be equal in the views of all people simultaneously. And what if 3. we merely want it to be "envy free" i.e. each person regards own part as at least as good as any rival's? These variants especially #3, probably would be important if they could be solved; worth publishing. Variant 1: trivial upper bound is n!. Somewhat better upper bound is LCM(1,2,3,...,n) which grows like exp(n) roughly, while n! is superexponential. But neither bound is best possible: for n=3 4=3+1 cuts work, 6 are not needed. Ok, a much better upper bound is 1+2+...+n=(n+1)*n/2. Still better is (n-1)*n/2+1. Still better is n + SUM(k=2..n-1) [(k-1) if no multiple of k exists that is <=n, otherwise 0] which is equivalent to 1 + SUM(k=ceiling(n/2)..n) (k-1) which equals (n+2)(3n-4)/8+1 is n=even and 3(n-1)(n+1)/8+1 if n=odd. But this still is not best possible since with n=4 cutting into 3 pieces of measure 1/4, and 3 of measure 1/12 each, works. For variant 2, n=2, Amy "moves her knives" in such a way that knife #1 is at angle theta, while knife #2 provides a fair cut into 2 (in Amy's view) pieces. Bob calls out "now" whenever Amy's knives are also fair in his judgement. Then they cut. A solution must exist by some kind of intermediate value theorem, i.e. Bob will not remain silent. For variant 2, n=3, Amy's "knife space" is now a periodic curve in a 3-dimensional rather than 2-dimensional space of knife-angular positions. Hence it in general will not intersect Bob's curve. Hence variant 2 is unsolvable for any n>=3. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)