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