[math-fun] A variant of the muffin problem
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
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
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
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
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
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
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
Yoav clarifies his solution as follows: “I'm talking about the limit cycle, not the entire orbit. The limit cycle is by itself a solution to the puzzle, but maybe not using the exact same process. One way you can make it into a solution is, say, break the first four chocolates into morsels of sizes w, 1-w, x, 1-x, y, 1-y, z, and 1-z and repeat with the next four and so on; give the first four students chocolates of sizes w+3(1-x), x+2(1-y), y+2(1-z), and z+2(1-w), and repeat with the next four students and so on, using the oldest piece of each size always.” Does anyone think that 15(ϕ-1)/23 can be improved upon? Jim On Wed, Aug 19, 2020 at 1:19 PM James Propp <jamespropp@gmail.com> wrote:
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 > > >
Sorry, I left out one of the intervening emails from Yoav, which may clarify his method. He wrote: "I use the following iterative map: f(x) = { 1 - (phi - x)/3 if phi-x > 1.2 1 - (phi - x)/2 if phi-x <= 1.2 If 0.4 <= x <= 0.6, then so is f(x). This is a formalization of the process I was describing in the previous tweets: you have a piece of size x that you have to use, so you look at how much you have to add to it to make up phi, and you either make it up with two or three equal pieces and put their complements in the reserve. Then these complements are the next size x you have to deal with. When I iterated f numerically I saw it converged to a cycle of length 4, and by inspection I saw that three of the iterations in the cycle fell in the "/2" branch and the fourth was in the "/3" branch. The equation I gave is just x = f(w), y = f(x), z = f(y), w = f(z) using this branch information." I just applied Yoav's method to the case where all the students are supposed to get Sqrt[2] ounces of chocolate, iterating the map f(x) = { 1 - (Sqrt[2] - x)/3 if Sqrt[2]-x > 1.2 1 - (Sqrt[2] - x)/2 if Sqrt[2]-x <= 1.2 Instead of a 4-cycle I found a fixed point, namely 2 - Sqrt[2]. That is, for this case, Yoav's approach gives us what we would get from Evan's approach. (We split each piece of size 1 into a piece of size Sqrt[2] - 1 and a piece of size 2 - Sqrt[2], and then give each student two pieces of size Sqrt[2] - 1 and one piece of size 2 - Sqrt[2], with no piece smaller than Sqrt[2] - 1 = 0.414...) I looked at the limit cycles for maps of the form f(x) = { 1 - (c - x)/3 if c-x > 1.2 1 - (c - x)/2 if c-x <= 1.2 empirically (where c is the number of ounces of chocolate each student is supposed to get) and found lots of variety in the sizes of orbits: 1, 2, 3, 4, 5, 6, 7, ... Looks complicated! But I don't know if those complexities will affect the solution of my problem for general values of c. Jim Propp On Mon, Aug 24, 2020 at 11:39 AM James Propp <jamespropp@gmail.com> wrote:
Yoav clarifies his solution as follows:
“I'm talking about the limit cycle, not the entire orbit. The limit cycle is by itself a solution to the puzzle, but maybe not using the exact same process. One way you can make it into a solution is, say, break the first four chocolates into morsels of sizes w, 1-w, x, 1-x, y, 1-y, z, and 1-z and repeat with the next four and so on; give the first four students chocolates of sizes w+3(1-x), x+2(1-y), y+2(1-z), and z+2(1-w), and repeat with the next four students and so on, using the oldest piece of each size always.”
Does anyone think that 15(ϕ-1)/23 can be improved upon?
Jim
On Wed, Aug 19, 2020 at 1:19 PM James Propp <jamespropp@gmail.com> wrote:
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 >> >> >> > >
I suspect you should adjust the map depending on the value of c. Let n=floor(2c) and ⍴=n(n-1)/(2n-1) and use the mapf(x) = { 1 - (c - x)/n if c-x > ⍴ 1 - (c - x)/(n-1) if c-x <= ⍴This doesn't change anything when c=sqrt[2] because in either case you want to give each student three pieces. I'm guessing you will continue to see the variety in the sizes of the orbits. Richard On Monday, August 24, 2020, 04:35:15 PM PDT, James Propp <jamespropp@gmail.com> wrote: Sorry, I left out one of the intervening emails from Yoav, which may clarify his method. He wrote: "I use the following iterative map:f(x) = { 1 - (phi - x)/3 if phi-x > 1.2 1 - (phi - x)/2 if phi-x <= 1.2If 0.4 <= x <= 0.6, then so is f(x). This is a formalization of the process I was describing in the previous tweets: you have a piece of size x that you have to use, so you look at how much you have to add to it to make up phi, and you either make it up with two or three equal pieces and put their complements in the reserve. Then these complements are the next size x you have to deal with. When I iterated f numerically I saw it converged to a cycle of length 4, and by inspection I saw that three of the iterations in the cycle fell in the "/2" branch and the fourth was in the "/3" branch. The equation I gave is just x = f(w), y = f(x), z = f(y), w = f(z) using this branch information." I just applied Yoav's method to the case where all the students are supposed to get Sqrt[2] ounces of chocolate, iterating the mapf(x) = { 1 - (Sqrt[2] - x)/3 if Sqrt[2]-x > 1.2 1 - (Sqrt[2] - x)/2 if Sqrt[2]-x <= 1.2Instead of a 4-cycle I found a fixed point, namely 2 - Sqrt[2]. That is, for this case, Yoav's approach gives us what we would get from Evan's approach. (We split each piece of size 1 into a piece of size Sqrt[2] - 1 and a piece of size 2 - Sqrt[2], and then give each student two pieces of size Sqrt[2] - 1 and one piece of size 2 - Sqrt[2], with no piece smaller than Sqrt[2] - 1 = 0.414...) I looked at the limit cycles for maps of the formf(x) = { 1 - (c - x)/3 if c-x > 1.2 1 - (c - x)/2 if c-x <= 1.2empirically (where c is the number of ounces of chocolate each student is supposed to get) and found lots of variety in the sizes of orbits: 1, 2, 3, 4, 5, 6, 7, ... Looks complicated! But I don't know if those complexities will affect the solution of my problem for general values of c. Jim Propp On Mon, Aug 24, 2020 at 11:39 AM James Propp <jamespropp@gmail.com> wrote: Yoav clarifies his solution as follows: “I'm talking about the limit cycle, not the entire orbit. The limit cycle is by itself a solution to the puzzle, but maybe not using the exact same process. One way you can make it into a solution is, say, break the first four chocolates into morsels of sizes w, 1-w, x, 1-x, y, 1-y, z, and 1-z and repeat with the next four and so on; give the first four students chocolates of sizes w+3(1-x), x+2(1-y), y+2(1-z), and z+2(1-w), and repeat with the next four students and so on, using the oldest piece of each size always.” Does anyone think that 15(ϕ-1)/23 can be improved upon? Jim On Wed, Aug 19, 2020 at 1:19 PM James Propp <jamespropp@gmail.com> wrote: 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, 069, 43, 1.60465, 061, 38, 1.60526, 053, 33, 1.60606, 045, 28, 1.60714, 037, 23, 1.6087, 066, 41, 1.60976, 029, 18, 1.61111, 050, 31, 1.6129, 021, 13, 1.61538, 055, 34, 1.61765, -1/149634, 21, 1.61905, 047, 29, 1.62069, -1/58060, 37, 1.62162, 013, 8, 1.625, 070, 43, 1.62791, -1/34457, 35, 1.62857, -1/28044, 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
You can beat 15(ɸ-1)/23 by including pieces of size 1/2 in one of the steps: give each set of four students chocolates of sizes w+3(1-x), x+1/2+(1-y), y+2(1-z), and z+2(1-w). This results in a smallest piece (1-x) of size (16ɸ-17)/22 which is slightly larger than 0.404. Richard On Monday, August 24, 2020, 08:43:37 AM PDT, James Propp <jamespropp@gmail.com> wrote: Yoav clarifies his solution as follows: “I'm talking about the limit cycle, not the entire orbit. The limit cycle is by itself a solution to the puzzle, but maybe not using the exact same process. One way you can make it into a solution is, say, break the first four chocolates into morsels of sizes w, 1-w, x, 1-x, y, 1-y, z, and 1-z and repeat with the next four and so on; give the first four students chocolates of sizes w+3(1-x), x+2(1-y), y+2(1-z), and z+2(1-w), and repeat with the next four students and so on, using the oldest piece of each size always.” Does anyone think that 15(ϕ-1)/23 can be improved upon? Jim On Wed, Aug 19, 2020 at 1:19 PM James Propp <jamespropp@gmail.com> wrote: 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, 069, 43, 1.60465, 061, 38, 1.60526, 053, 33, 1.60606, 045, 28, 1.60714, 037, 23, 1.6087, 066, 41, 1.60976, 029, 18, 1.61111, 050, 31, 1.6129, 021, 13, 1.61538, 055, 34, 1.61765, -1/149634, 21, 1.61905, 047, 29, 1.62069, -1/58060, 37, 1.62162, 013, 8, 1.625, 070, 43, 1.62791, -1/34457, 35, 1.62857, -1/28044, 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
To clarify (for those who are only half-following the action), Richard is replacing the system of equations w+3(1-x) = *x+2(1-y) *= y+2(1-z) = z+2(1-w) = ɸ by the system of equations w+3(1-x) = *x+1/2+(1-y) =* y+2(1-z) = z+2(1-w) = ɸ and obtaining a slightly larger value of min(w,x,y,z,1-w,1-x,1-y,1-z). Here ɸ denotes (1+sqrt(5))/2; in a much earlier email (the one about Evan Romer's solution) I used (1+sqrt(5))/2. Sorry for sowing any confusion. (And apologies in advance if anything I'm writing here is wrong or misleading!) Jim On Tue, Aug 25, 2020 at 7:30 AM Richard Chatwin <rchatwin1@yahoo.com> wrote:
You can beat 15(ɸ-1)/23 by including pieces of size 1/2 in one of the steps: give each set of four students chocolates of sizes w+3(1-x), x+1/2+(1-y), y+2(1-z), and z+2(1-w). This results in a smallest piece (1-x) of size (16ɸ-17)/22 which is slightly larger than 0.404.
Richard
On Monday, August 24, 2020, 08:43:37 AM PDT, James Propp < jamespropp@gmail.com> wrote:
Yoav clarifies his solution as follows:
“I'm talking about the limit cycle, not the entire orbit. The limit cycle is by itself a solution to the puzzle, but maybe not using the exact same process. One way you can make it into a solution is, say, break the first four chocolates into morsels of sizes w, 1-w, x, 1-x, y, 1-y, z, and 1-z and repeat with the next four and so on; give the first four students chocolates of sizes w+3(1-x), x+2(1-y), y+2(1-z), and z+2(1-w), and repeat with the next four students and so on, using the oldest piece of each size always.”
Does anyone think that 15(ϕ-1)/23 can be improved upon?
Jim
On Wed, Aug 19, 2020 at 1:19 PM James Propp <jamespropp@gmail.com> wrote:
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
I should also explain that we are limiting ourselves to dissections that involve splitting each original piece of chocolate into exactly two morsels, because once you have a piece divided into three morsels, the smallest can be no larger than 1/3, and even Evan Romer’s solution beats that. (Actually, how do we know the optimal solution won’t involve leaving some of the original pieces unsplit?) Also, we may assume WLOO* that each new piece of size phi is made of 3 or 4 morsels. For if a new piece of size phi were made of 5 or more morsels, the smallest of them would be of size at most phi/5 ~ .32, while if a new piece were made of just 2 morsels, the larger of the two would be of size at least phi/2 ~ .8 and its complementary morsel(s) from the original piece it came from would be of size at most ~.2; either way, an unacceptably small morsel would be involved. Jim * Without Loss Of Optimality. (Is that a thing?) On Aug 25, 2020 at 11:37 AM James Propp <jamespropp@gmail.com> wrote:
To clarify (for those who are only half-following the action), Richard is replacing the system of equations
w+3(1-x) = *x+2(1-y) *= y+2(1-z) = z+2(1-w) = ɸ
by the system of equations
w+3(1-x) = *x+1/2+(1-y) =* y+2(1-z) = z+2(1-w) = ɸ
and obtaining a slightly larger value of min(w,x,y,z,1-w,1-x,1-y,1-z).
Here ɸ denotes (1+sqrt(5))/2; in a much earlier email (the one about Evan Romer's solution) I used (1+sqrt(5))/2. Sorry for sowing any confusion. (And apologies in advance if anything I'm writing here is wrong or misleading!)
Jim
On Tue, Aug 25, 2020 at 7:30 AM Richard Chatwin <rchatwin1@yahoo.com> wrote:
You can beat 15(ɸ-1)/23 by including pieces of size 1/2 in one of the steps: give each set of four students chocolates of sizes w+3(1-x), x+1/2+(1-y), y+2(1-z), and z+2(1-w). This results in a smallest piece (1-x) of size (16ɸ-17)/22 which is slightly larger than 0.404.
Richard
On Monday, August 24, 2020, 08:43:37 AM PDT, James Propp < jamespropp@gmail.com> wrote:
Yoav clarifies his solution as follows:
“I'm talking about the limit cycle, not the entire orbit. The limit cycle is by itself a solution to the puzzle, but maybe not using the exact same process. One way you can make it into a solution is, say, break the first four chocolates into morsels of sizes w, 1-w, x, 1-x, y, 1-y, z, and 1-z and repeat with the next four and so on; give the first four students chocolates of sizes w+3(1-x), x+2(1-y), y+2(1-z), and z+2(1-w), and repeat with the next four students and so on, using the oldest piece of each size always.”
Does anyone think that 15(ϕ-1)/23 can be improved upon?
Jim
On Wed, Aug 19, 2020 at 1:19 PM James Propp <jamespropp@gmail.com> wrote:
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
Evan's solution beats g(m/s) for 3/2 < m/s < 8/5. On this range g(m/s) = m/4s < 2/5 but Evan's solution has smallest piece of size 2 - m/s > 2/5. On 5/3 < x < 2, it's better to give all students 4 pieces, i.e., divide each piece of chocolate into one piece of size (x - 1)/2 and one piece of size (3 - x)/2, then give each arriving student pieces (x - 1)/2, (x - 1)/2, (x - 1)/2, and (3 - x)/2. This solution beats g(m/s) for 9/5 < m/s < 2. On this range g(m/s) = 1 - m/3s < 2/5 but this solution has smallest piece of size (m/s - 1)/2 > 2/5. Richard On Wednesday, August 19, 2020, 05:10:35 AM PDT, 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
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Jim, I suspect the following is true: for any irrational y there exist rationals a/b and c/d such that a/b < y < c/d and g(r) is continuous on the rationals on the open interval (a/b, c/d). For /phi, we have 76/47 < /phi < 34/21 and on the interval (76/47, 34/21) the value of g(r) is given by (19 - 9r)/11. Also, g(8/5) = 2/5 and for all 2/5 < r < 2, g(r) > 2/5 except for some r close to 2. Richard Sent from my iPhone
On Aug 17, 2020, at 8: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
participants (2)
-
James Propp -
Richard Chatwin