After reading the blog dxdy discussion, I've implemented the following: My MIP (mixed integer programming) setup is a lot like what Veit has suggested -- I do have extra relations to break symmetries (which is rather important since the symmetry group is huge). What I've added, is exhausting over all possible partitions (just the numbers not the sets -- I allow the MIP to find the placement) -- so if we have a putative value of f(n) = k, we look for partitions of k into m parts for each n/2 +1 <= m <= n, and only look at those whose parts are >=2 if m < n. For every combination of such I add sum constraints to insure that the number of parts corresponds to the assumed partition. In addition for the partitions for m=n, if a part has size 1 -- we know that a corresponding piece has size 1/n. Doing this can get lots of solutions -- at most 1 for each combination of partitions (most of them fail). I've found a few solutions for n=5 and n=6 which have denominator 2*LCM. Victor On Wed, Dec 20, 2017 at 4:56 PM, Veit Elser <ve10@cornell.edu> wrote:
On Dec 19, 2017, at 1:01 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Victor, I can't remember if you managed to put a lower bound on the LCM of the denominators. The Russian group discussed this as well, and found some optimal solutions for n=5 that required a common denominator of 120 rather than 60. But n=5 does have some solutions based on 60ths. My intuition is that there will always be optimal solutions based on a common denominator of LCM(1..n). But I can't come close to proving it.
I just recently started thinking about this and wondered if, for the case that the denominator is LCM(1..n), one could express feasibility just in terms of linear equations for 0/1 variables. Here’s what I've come up with so far, but I don’t guarantee I haven’t overlooked something!
m = LCM(1..n)
My 0/1 variables have four indices: x[i,j,k,p]
i = 1..m labels the “atoms” of the pizza j = 2..n labels the “partition” (j = 3 means we serve three mathematicians) k = 1..j labels the parts of partition j p = 1..P labels the pizza pieces
The smallest P that gives a feasible point is f(n).
Here is the interpretation of the variables:
x[i,j,k,p] = 1 if atom i belongs to piece p and in partition j lies in part k; x[i,j,k,p] = 0 otherwise.
There are three kinds of equations:
1) for all (j,k,p) and all pairs (i,i’) : x[i,j,k,p] = x[i',j,k,p]
2) for all (i,j) : sum_(k,p) x[i,j,k,p] = 1
3) for all (j,k) : sum_(i,p) x[i,j,k,p] = m/j
Roughly speaking, 1) says that all the atoms of a piece act the same way, 2) says every atom appears exactly once in each partition, and 3) says the partitions have equal size.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun