I've managed to prove the following result: For a fixed n, there are only a finite number of optimal (smallest number of pieces) to the pie cutting problem, and they are all rational. It turns out that the proof is simple (given some basic facts about polytopes): There are only a finite number of colorings for m=floor(n/2) + 1, ..., n (aka partitions). Once one is fixed, a solution compatible with that coloring amounts to a system of linear equations, along with non-negativity. There are now 3 cases: 1) The system of linear equations is inconsistent -- in this case there is no solution 2) The system of linear equations is consistent but the affine solution subspace is disjoint from the non-negative orthant (all x_i >= 0) -- in this case there also is no solution. 3) The system of linear equations is consistent and the affine solution subspace has a non-void intersection with the nonnegative orthant, say P, which is a polytope. This is the solution space. Suppose that the rank of the system of equations is < k = f(n). In that case the standard results for convex polytopes, say that the vertices of P are obtained by making k-rank of the inequalites equalities (the resulting system might have no solutions, in which case it is rejected), and solving the full rank sysytem. However, all of the inequalities are of the form x_i >= 0, so making them an equality would 0 out one of the x's, which is impossible since we have an optimal solution. Thus the only alternative is that we have a full rank system with rational coefficents (in fact all 0/1), so there is a unique rational solution. It would be interesting (but looks rather hard, absent another idea) to figure out the number of optimal solutions (even for n=5). Victor On Fri, Dec 22, 2017 at 4:34 PM, Victor Miller <victorsmiller@gmail.com> wrote:
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