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)
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
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
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
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
On 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
I ran a “divide and concur” solver on the f(5) problem. It manages to break symmetry just by choice of the random initial point (the iteration rule is deterministic). Here are the solutions (x 60), with counts, for 50 trials: {1, {1, 2, 3, 3, 7, 8, 12, 12, 12}} {1, {1, 2, 3, 4, 6, 9, 11, 12, 12}} {1, {1, 2, 3, 4, 7, 8, 11, 12, 12}} {1, {1, 2, 3, 5, 6, 9, 10, 12, 12}} {1, {2, 3, 3, 5, 6, 7, 10, 12, 12}} {1, {2, 3, 4, 5, 7, 8, 9, 10, 12}} {1, {3, 4, 5, 6, 6, 7, 8, 9, 12}} {4, {1, 2, 4, 5, 7, 8, 10, 11, 12}} {4, {1, 3, 4, 6, 6, 8, 9, 11, 12}} {5, {1, 3, 3, 4, 5, 9, 11, 12, 12}} {5, {1, 3, 3, 5, 7, 8, 9, 12, 12}} {6, {1, 3, 4, 5, 7, 8, 9, 11, 12}} {9, {1, 2, 3, 5, 7, 8, 10, 12, 12}} {10, {1/2, 5/2, 7/2, 11/2, 13/2, 17/2, 19/2, 23/2, 12}} Together with Victor’s denominator-240 solution that makes at least 15 solutions. My method does not assume a given denominator, and is quite different from what I sketched in my previous email (which turned out to be flawed). For n=5, f(5)=9, the variables form a real-valued tensor of shape 4x9x2x3x4x5 (so 4320 numbers). In each iteration, two constraint projections are applied to this tensor, designed so that a tensor is a solution iff it is fixed by both projections. -Veit
The sharp-eyed among you may have noted that my denominator 240 solution for f(5) was spurious, since it has 10 parts and not 9. In the meantime I got my cplex program to use their populate feature (find all solutions by exhausting the tree), and it got 18. I noticed that they are the same as found by user "Grizzly" on dxdy. I'm having cplex find all solutions for f(6), but it's taking a while. The f(5) solutions are (after multiplying by 60): (1, 5, 6, 11, 13, 17, 19, 23, 24)/2 1, 2, 3, 3, 7, 8, 12, 12, 12 1, 2, 3, 4, 6, 9, 11, 12, 12 1, 2, 3, 4, 7, 8, 11, 12, 12 1, 2, 3, 5, 6, 9, 10, 12, 12 1, 2, 3, 5, 7, 8, 10, 12, 12 1, 2, 4, 5, 7, 8, 10, 11, 12 1, 3, 3, 4, 5, 9, 11, 12, 12 1, 3, 3, 4, 6, 8, 11, 12, 12 1, 3, 3, 5, 7, 8, 9, 12, 12 1, 3, 4, 5, 7, 8, 9, 11, 12 1, 3, 4, 6, 6, 8, 9, 11, 12 2, 3, 3, 4, 7, 8, 9, 12, 12 2, 3, 3, 5, 6, 7, 10, 12, 12 2, 3, 4, 5, 7, 8, 9, 10, 12 2, 3, 5, 6, 6, 7, 9, 10, 12 3, 3, 4, 5, 6, 7, 8, 12, 12 3, 4, 5, 6, 6, 7, 8, 9, 12 On Sat, Dec 23, 2017 at 1:07 PM, Veit Elser <ve10@cornell.edu> wrote:
On 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
I ran a “divide and concur” solver on the f(5) problem. It manages to break symmetry just by choice of the random initial point (the iteration rule is deterministic). Here are the solutions (x 60), with counts, for 50 trials:
{1, {1, 2, 3, 3, 7, 8, 12, 12, 12}} {1, {1, 2, 3, 4, 6, 9, 11, 12, 12}} {1, {1, 2, 3, 4, 7, 8, 11, 12, 12}} {1, {1, 2, 3, 5, 6, 9, 10, 12, 12}} {1, {2, 3, 3, 5, 6, 7, 10, 12, 12}} {1, {2, 3, 4, 5, 7, 8, 9, 10, 12}} {1, {3, 4, 5, 6, 6, 7, 8, 9, 12}} {4, {1, 2, 4, 5, 7, 8, 10, 11, 12}} {4, {1, 3, 4, 6, 6, 8, 9, 11, 12}} {5, {1, 3, 3, 4, 5, 9, 11, 12, 12}} {5, {1, 3, 3, 5, 7, 8, 9, 12, 12}} {6, {1, 3, 4, 5, 7, 8, 9, 11, 12}} {9, {1, 2, 3, 5, 7, 8, 10, 12, 12}} {10, {1/2, 5/2, 7/2, 11/2, 13/2, 17/2, 19/2, 23/2, 12}}
Together with Victor’s denominator-240 solution that makes at least 15 solutions.
My method does not assume a given denominator, and is quite different from what I sketched in my previous email (which turned out to be flawed).
For n=5, f(5)=9, the variables form a real-valued tensor of shape 4x9x2x3x4x5 (so 4320 numbers). In each iteration, two constraint projections are applied to this tensor, designed so that a tensor is a solution iff it is fixed by both projections.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The sharp-eyed among you may have noted that my denominator 240 solution for f(5) was spurious, since it has 10 parts and not 9. The f(5) solutions are (after multiplying by 60):
(1, 5, 6, 11, 13, 17, 19, 23, 24)/2 If you’re trying to catch us asleep again, then you've failed. That 6 should be a 7.
-Veit P.S. Does your software let you know how many solutions there are for each partition? If so, it could explain the rather non-uniform rates that divide-and-concur finds them.
Veit, You're right, I mistranscribed it. My software is running on our "inside" system with no connection to the internet, so I have to retype things. The run for f(6) just finished with 32 solutions, 3 of which have denominator 120 and the rest denominator 60. Cplex actually found 227 solutions for f(5) -- but that was counting a solution as different if it had different partitions (aka colorings) for division into 3, 4 and 5. For f(6) it found 7947 solutions before ignoring which way they were partitioned into 4,5,6 pieces. So you might have fun trying to reassemble the 18 into essentially different ways. After New Year's I'll write some programs to give finer statistics about them. Victor PS. To Warren. I had already put a feature in my program to restrict the partitions considered at various levels. For the full f(6) it took a 2563 seconds to find all solutions. But, when I restricted the 6-partition to (1,1,1,2,3,3) (since the value of f(6) is 11), it took only 13 seconds to find 3780 solutions satisfying that partition). On Fri, Dec 29, 2017 at 5:03 PM, Veit Elser <ve10@cornell.edu> wrote:
The sharp-eyed among you may have noted that my denominator 240 solution for f(5) was spurious, since it has 10 parts and not 9. The f(5) solutions are (after multiplying by 60):
(1, 5, 6, 11, 13, 17, 19, 23, 24)/2 If you’re trying to catch us asleep again, then you've failed. That 6 should be a 7.
-Veit
P.S. Does your software let you know how many solutions there are for each partition? If so, it could explain the rather non-uniform rates that divide-and-concur finds them. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Warren, I took your suggestion with f(5): restricting the 5 partition to (1,1,1,3,3), and it found 72 solutions in less than 1 second, as opposed to finding all 227 in 48.27 seconds. On Fri, Dec 29, 2017 at 5:30 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Veit, You're right, I mistranscribed it. My software is running on our "inside" system with no connection to the internet, so I have to retype things. The run for f(6) just finished with 32 solutions, 3 of which have denominator 120 and the rest denominator 60. Cplex actually found 227 solutions for f(5) -- but that was counting a solution as different if it had different partitions (aka colorings) for division into 3, 4 and 5. For f(6) it found 7947 solutions before ignoring which way they were partitioned into 4,5,6 pieces. So you might have fun trying to reassemble the 18 into essentially different ways. After New Year's I'll write some programs to give finer statistics about them.
Victor
PS. To Warren. I had already put a feature in my program to restrict the partitions considered at various levels. For the full f(6) it took a 2563 seconds to find all solutions. But, when I restricted the 6-partition to (1,1,1,2,3,3) (since the value of f(6) is 11), it took only 13 seconds to find 3780 solutions satisfying that partition).
On Fri, Dec 29, 2017 at 5:03 PM, Veit Elser <ve10@cornell.edu> wrote:
The sharp-eyed among you may have noted that my denominator 240 solution for f(5) was spurious, since it has 10 parts and not 9. The f(5) solutions are (after multiplying by 60):
(1, 5, 6, 11, 13, 17, 19, 23, 24)/2 If you’re trying to catch us asleep again, then you've failed. That 6 should be a 7.
-Veit
P.S. Does your software let you know how many solutions there are for each partition? If so, it could explain the rather non-uniform rates that divide-and-concur finds them. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
James Propp -
Veit Elser -
Victor Miller