I just found a solution to the f(5) problem with denominator 240 (4 times the lcm). This seems to be new: pieces = [2,9,14,17,21,27,31,34,39,46]/240 decompositions: 1/3: (17/120+23/120, 7/120+9/80+13/80, 1/120+3/80+17/240+31/240) 1/4: (7/80+13/80, 7/120+23/120, 3/80+17/240+17/120, 1/120+9/80+31/240) 1/5: (7/80+9/80, 17/240+31/240, 7/120+17/120, 3/80+13/80, 1/120 + 23/120) On Fri, Dec 22, 2017 at 12:31 PM, Victor Miller <victorsmiller@gmail.com> wrote:
I meant this to go to the whole list:
I just finished digesting the proof of a lower bound 2n-1 for n > 4 by user "Null" (really!). It contains an interesting idea, which he uses in other lower bound arguments.
Here's the simplest argument, though I see how to generalize it a bit.
Consider the complete bipartite graph with n nodes on the left and n-1 on the right. For every realizable set of pieces label the edge (i,j) with the multi set of piece sizes that contribute to node i on the left and node j on the right. If the corresponding multiset is empty, delete the edge. If v is a node (on either side), the sum of the weights on all the edges incident to v must be 1/n if v is on the left and 1/(n-1) if v is on the right. Suppose that there are only 2n-2 pieces. The first assertion is that the graph is connected: Let c be a connected component with m_1 vertices on the left and m_2 on the left. Then, by the above remark we have m_1/n = m_2/(n-1). But, it's easy to see that this implies that m_1 = n, and m_2 = n-1. We have a connected graph with 2n-1 nodes and 2n-2 edges, so it must be a tree, and there is exactly one piece on each edge. This implies that all of the piece sizes are uniquely determined -- label each vertex by the total remaining weight (at the beginning 1/n on the left and 1/(n-1) on the right). If a vertex is a leaf, then the weight on the one edge incident to it is equal to its weight. Then delete that edge and reduce the weight of the vertex on the other side. Keep doing this until you've exhausted the graph. Since all denominators involved are either n or n-1 at the beginning, all resulting weights must be of the form s/(n(n-1)). Now consider the multi-partite graph as above, except that now we throw in the n-2 group. Since all of the weights are of the form s/(n(n-1)) we must then have 1/(n-2) = t/(n(n-1)) for some integer t. Clear denominators to get t(n-2) = n(n-1). Rearranging, this gives t = n+1 + 2/(n-2), so n=3 or 4 are the only possibilities.
The poster Null considered a larger part of the multipartite graph to get the fact that f(7) > 13: since the original graph now would have 2n-1 edges, and is connected, there must be one cycle -- he makes the weight on a cycle breaking edge an unknown, and then analyzes the linear equations that he gets.
On Thu, Dec 21, 2017 at 4:36 PM, Victor Miller <victorsmiller@gmail.com> wrote:
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