From Warren Smith:
---------- Forwarded message ---------- From: Warren D Smith <warren.wds@gmail.com> Date: Thu, Dec 21, 2017 at 2:27 AM Subject: Re: [math-fun] Cutting a pie ... To: James Propp <jamespropp@gmail.com> OK, think I see how to rigorize my claim F(n) < K * n^2 / log(n). Specifically THEOREM: If K>1, then for all sufficiently large n F(n) < K*(n^2) / (2*ln(n)). PROOF: Essentially, here is the argument. Let L(n) = LCM(1,2,3,...,n) = exp([1+o(1)]*n). Choose a subset of {0,1,2,...,L(n)-1} of cardinality=F(n) at random. Sort it. Let S denote the F(n) consecutive-element differences [modulo L(n)] in that subset. Hence the elements of S sum to L(n), which will be the total size of the pie. Now consider all possible ways to k-color the elements of S. Do this for each k=2,3,...,n, the result being a "coloring tuple" (i.e the elements of the coloring tuple are: the 2-coloring, the 3-coloring, ..., the n-coloring) and we are considering the full set of all possible coloring tuples. If the k-coloring has the property that the k different monochromatic sums of S-elements all happen to be equal, then S provides a cake-cutting suitable for k players. If the full coloring tuple does that for k=2,3,...,n all simultaneously, then it was a suitable cake cutting. Ask: what is the expected number of coloring tuples that are thus-suitable? The answer is lower bounded by n!^F(n) * L(n)^(-(n-1)*n/2). Now: if this expectation exceeds 1, that proves a suitable coloring-tuple MUST EXIST, i.e. a suitable cake-cutting must exist. Taking logs, we see that happens if F(n)*log(n!) >= (n-1)*n/2 * n * [1+o(1)] That happens if F(n) >= [1+o(1)] * (n-1)*n/(2*log(n)) using natural log. Q.E.D. This is a nice application of "Erdos's method." -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)