More from Yoav: “I just tried this out numerically, and it converges to a 4-cycle given by the solution to w+3(1-x) = x+2(1-y) = y+2(1-z) = z+2(1-w) = ϕ. The smallest piece is of size 15(ϕ-1)/23 = 0.403.“ Jim Propp On Wed, Aug 19, 2020 at 10:23 AM James Propp <jamespropp@gmail.com> wrote:
Yoav Kallus (on Twitter) writes:
“Assuming your reserve only has pieces of size between 0.4 and 0.6 you can repeat this process: take a piece x from the reserve; if ϕ-x>1.2, make 3 new pieces of size (ϕ-x)/3, combine with x to give to a student, and store their complements in the reserve. Ifϕ-x<=1.2, make 2 new pieces of size (ϕ-x)/2, combine with x to give to a student, and store their complements in the reserve. Start this process e.g. by giving a student four ϕ/4 pieces and storing the 4 complements. Use the reserve fifo, so you end up using everything.”
So we can get all the pieces to have size at least 0.4.
Can we do better?
Jim Propp
On Wed, Aug 19, 2020 at 8:09 AM James Propp <jamespropp@gmail.com> wrote:
Actually, a few sips of coffee just made me realize that I didn't actually lose my bet (at least not yet), since my challenge was to find a solution in which the largest smallest piece is 0.4 or larger. Evan's solution comes close but falls short.
I won't presume to make any pronouncements with this little coffee inside me, but it now seems to me fairly likely that the Ethel-and-Lucy problem is just plain different from the muffin problem. Can anyone come up with a pair m,s where the Ethel-and-Lucy variant is genuinely different from the original problem? That is, can anyone find a pair where Ethel and Lucy can come up with a scheme that beats g(m/s)?
Jim
On Wed, Aug 19, 2020 at 7:21 AM James Propp <jamespropp@gmail.com> wrote:
I’m glad none of you accepted my bet, because I was wrong! Evan Romer points out that for any x between 1 and 2 we can divide each chocolate of size 1 into a piece of size x-1 and a piece of size 2-x and then reassemble them to form infinitely many pieces of size (x-1)+(x-1)+(2-x) = x. In assembly line terms, the holding area will get more and more crowded, but every piece added to it will eventually get handed to a student.
In the case x = 1.618.., the smallest piece has size 1-x = 0.382..., which is smaller than 0.4.
As a reward for his cleverness, I’m giving Evan infinitely many nights in the master suite of the Hilbert hotel.
Can one do even better than Evan’s solution?
Jim
On Mon, Aug 17, 2020 at 12:35 PM James Propp <jamespropp@gmail.com> wrote:
Here are some relevant data. For tabulated values of f(m,s) with m/s between 1.60 and 1.63, I give m, s, m/s, and the difference f(m,s) - m/4s (sorted in order of m/s). For many pairs the difference is 0 but others it's negative, meaning that there is no way to cut the muffins so that each piece has size at least m/4s.
8, 5, 1.6, 0 69, 43, 1.60465, 0 61, 38, 1.60526, 0 53, 33, 1.60606, 0 45, 28, 1.60714, 0 37, 23, 1.6087, 0 66, 41, 1.60976, 0 29, 18, 1.61111, 0 50, 31, 1.6129, 0 21, 13, 1.61538, 0 55, 34, 1.61765, -1/1496 34, 21, 1.61905, 0 47, 29, 1.62069, -1/580 60, 37, 1.62162, 0 13, 8, 1.625, 0 70, 43, 1.62791, -1/344 57, 35, 1.62857, -1/280 44, 27, 1.62963, 0
Given the absence of positive values in the last column, I'd be willing to bet that for the Ethel and Lucy problem with x = 1.618..., there's no way to get all the pieces to be smaller than x/4 = 0.4045... But I would not stake any money on whether 0.4045... is actually achievable by some apportionment protocol, aye or nay; it's too close to call.
Jim
On Mon, Aug 17, 2020 at 11:51 AM James Propp <jamespropp@gmail.com> wrote:
I just checked the data Bill sent me for the muffin function f(m,s). There are seven pairs (m,s) with m/s between 1.60 and 1.61, and for all of them we have f(m,s) = m/4s. But this linear behavior fails when we get to m/s = 55/34, just shy of the golden ratio, and for the five pairs (m,s) with m/s between 1.61 and 1.62, the values of f(m,s) don't fit a line. So I don't have a guess for what happens for the Ethel-and-Lucy problem when x is the golden ratio.
On the other hand, for all m,s with m/s between 1.61 and 1.63, f(m,s) is bigger than 0.4, so I think that the answer to my question "is there a way for Ethel to divide the 1-ounce chocolates into smaller morsels, and for Lucy to distribute the morsels, so that every morsel gets eaten, and every student gets exactly ϕ ounces of chocolate, and no morsel is less than 0.4 ounces?" is "yes".
Jim
On Mon, Aug 17, 2020 at 10:04 AM James Propp <jamespropp@gmail.com> wrote:
From https://mathenchant.wordpress.com/2020/08/16/the-muffin-curse/ (slightly adapted):
Imagine an infinite supply of 1-ounce chocolates rolling off an assembly line that's staffed by two immortal and indefatigable employees (call them Ethel and Lucy) who have to feed an infinite line of students. When a new chocolate arrives, Ethel cuts it up and puts pieces into an infinitely large holding area; meanwhile, Lucy takes pieces from the holding area and hands them out to students. All the chocolate pieces must be handed out to students, and each student must get exactly *x* ounces of chocolate. If Lucy and Ethel want the smallest piece any student gets to be as large as possible, what goal should they shoot for, as a function of *x*? I'm pretty sure that when *x* is rational, this is just the muffin problem discussed in this forum back in 2008. But what happens when *x* is irrational? If, say, *x* is the golden ratio ϕ = (1 + sqrt(5))/2 = 1.618..., is there a way for Ethel to divide the 1-ounce chocolates into smaller morsels, and for Lucy to distribute the morsels, so that every morsel gets eaten, and every student gets exactly ϕ ounces of chocolate, and no morsel is less than 0.4 ounces?
It may be relevant to mention that for the original muffin problem, f(m,s) (defined as the maximum possible size of the smallest piece among all ways of distributing m muffins among s students) has the property that f(m,s) = g(m/s) for a certain function g that is NOT continuous as a function from the rationals to the rationals (here I am using the epsilon-delta definition of continuity, which makes sense even when the domain of a function is the rationals). So g(.) does not admit an extension to an everywhere-continuous function from the reals to itself (in case you were hoping, as I was, that this would be the answer). There may be some sort of semicontinuous extension at work here.
I chose 0.4 because if we let s and m be consecutive Fibonacci numbers, then g(m/s) seems to be converging to something slightly larger than 0.4.
Here's Richard Chatwin's article:
Richard Chatwin, An optimal solution for the muffin problem, https://arxiv.org/pdf/1907.08726.pdf.
Jim Propp