To Warren, Could you expand on The answer is lower bounded by n!^F(n) * L(n)^(-(n-1)*n/2)? It seems like you're getting this as follows: Let X be the random variable whose value is a uniform choice of all sequences S that sum to LCM(1...n), and Y_k be a random k coloring of S. So your'e looking at E( X, Y_k | Y_k is suitable for X, k=1,...,n ). You seem to be assuming that Y_k is suitable for X are independent events for different k, but I don't think that that's true, even if you only consider k=floor(n/2) + 1, ..., n (which is all that's necessary). On Thu, Dec 21, 2017 at 9:45 AM, James Propp <jamespropp@gmail.com> wrote:
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) _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun