[math-fun] Cutting a pie ...
The problem is usually expressed as one of dividing a cake (or pie) and distributing it so that no-one is in a position to complain about the size of their slice ... There's this ... https://www.scientificamerican.com/article/the-mathematics-of-cake-cutting/ ... and then there's this by Ian Stewart https://www.amazon.co.uk/How-Cut-Cake-Mathematical-Conundrums/dp/0199205906 However, the best solution I know of (which Ian Stewart confirmed he had not heard of) came from the 13-year-old son of a colleague of mine .... Everyone gets a knife and makes a cut in a circular cake which is standing on a turntable ... with the aim of making equal-size slices. The cake is then spun, and everyone gets the slice opposite them. [ In other words, the randomness takes the decision about who gets what away from the hungry mathematicians ] Guy
Guy: What if after pie-spinning, Alice thinks she got the worst piece and would prefer either Bob's or Carol's, while Bob and Carol would each prefer Alice's? Then everyone is unhappy, but Alice gets to trade with someone, and Bob and Carol fight with each other over which one she trades with. Seems unsatisfying. --Michael On Fri, Dec 15, 2017 at 10:23 AM, Guy Haworth <g.haworth@reading.ac.uk> wrote:
The problem is usually expressed as one of dividing a cake (or pie) and distributing it so that no-one is in a position to complain about the size of their slice ...
There's this ... https://www.scientificamerican.com/ article/the-mathematics-of-cake-cutting/
... and then there's this by Ian Stewart https://www.amazon.co.uk/How- Cut-Cake-Mathematical-Conundrums/dp/0199205906
However, the best solution I know of (which Ian Stewart confirmed he had not heard of) came from the 13-year-old son of a colleague of mine ....
Everyone gets a knife and makes a cut in a circular cake which is standing on a turntable ... with the aim of making equal-size slices.
The cake is then spun, and everyone gets the slice opposite them.
[ In other words, the randomness takes the decision about who gets what away from the hungry mathematicians ]
Guy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
What you characterize as a "best solution" purports to solve a much easier problem than the one discussed in the SA article The spin-the-cake algorithm is ill-defined; if we define the "places where the people are sitting" as n evenly-spaced points around the circle, it doesn't tell us what to do if to people are sitting in front of the same piece of cake after the spin. Even if you patch it up, the simplest way to do so being just having one person divide the cake, and a randomization procedure applied to decide who gets which piece, this solves only the problem "no-one is in a position to complain about the fairness of the procedure", a much simpler goal than the one being studied. This algorithm doesn't even satisfy the weaker criterion "each player believes that they have gotten at least 1 nth of the pie", a problem with a fairly simple solution (given below after spoiler space) that I first saw in a Martin Gardner Mathematical Games column in Scientific American decades ago. The more difficult criterion in the problem being discussed in the current SciAm article is that the division be "envy-free". That is, no player believes that his any other player's piece of cake is better than his own. The spinning algorithm also specifies that the players are to make their cuts "with the aim of making equal-sized pieces", which is another misunderstanding of how the criteria for an algorithm in this sort of problem are to be specified. Once the algorithm for cutting and distributing is specified, it then up to the players to cut and decide as they choose. That's why "one cuts and the other chooses" is a good algorithm, while "one player cuts, with the aim of making the pieces as equal as possible; then the same player chooses a piece" is a poor one; the non-cutter may feel the cutter has not honestly tried to make the pieces equal. The one cuts and the other chooses algorithm makes no requirement on the aims of players in doing the cutting and choosing, but each player is nonetheless satisfied that his piece is at least as big as the other, even if the other player makes his cutting and choosing decisions with the aim of making that not true. Solution to the n-player "at least 1 nth" problem, without the envy-free criteria. . . . . . . . . . . . . . Order the players 1 through n. The lowest-numbered player who has not yet been assigned a piece cuts a piece off of the pie (his best strategy will be to cut a piece he values as a fair slice). Then in order, each other player who has not yet been assigned a slice can either pass, or reduce the size of the proposed piece by cutting some off and returning it to the unassigned portion. The resulting piece is assigned to the last person to use the knife. Repeat until all players but one have been assigned a piece, and give what remains to the remaining player. (while I have numbered the players for definiteness, the consistency of ordering is not required for the correctness of the algorithm; the cutter and order of the other players may be chosen arbitrarily each round. Andy On Fri, Dec 15, 2017 at 10:23 AM, Guy Haworth <g.haworth@reading.ac.uk> wrote:
The problem is usually expressed as one of dividing a cake (or pie) and distributing it so that no-one is in a position to complain about the size of their slice ...
There's this ... https://www.scientificamerican.com/article/the-mathematics-of-cake-cutting/
... and then there's this by Ian Stewart https://www.amazon.co.uk/How-Cut-Cake-Mathematical-Conundrums/dp/0199205906
However, the best solution I know of (which Ian Stewart confirmed he had not heard of) came from the 13-year-old son of a colleague of mine ....
Everyone gets a knife and makes a cut in a circular cake which is standing on a turntable ... with the aim of making equal-size slices.
The cake is then spun, and everyone gets the slice opposite them.
[ In other words, the randomness takes the decision about who gets what away from the hungry mathematicians ]
Guy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
This version of cake-cutting reminds me of the Gift Exchange problem, see our paper in 'Lectronic J. Combin, *Analysis of the Gift Exchange Problem <http://neilsloane.com/doc/Moa10.pdf>*, 2017. Also arXiv:1701.08394 <http://arxiv.org/abs/1701.08394>, Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Fri, Dec 15, 2017 at 12:01 PM, Andy Latto <andy.latto@pobox.com> wrote:
What you characterize as a "best solution" purports to solve a much easier problem than the one discussed in the SA article
The spin-the-cake algorithm is ill-defined; if we define the "places where the people are sitting" as n evenly-spaced points around the circle, it doesn't tell us what to do if to people are sitting in front of the same piece of cake after the spin.
Even if you patch it up, the simplest way to do so being just having one person divide the cake, and a randomization procedure applied to decide who gets which piece, this solves only the problem "no-one is in a position to complain about the fairness of the procedure", a much simpler goal than the one being studied.
This algorithm doesn't even satisfy the weaker criterion "each player believes that they have gotten at least 1 nth of the pie", a problem with a fairly simple solution (given below after spoiler space) that I first saw in a Martin Gardner Mathematical Games column in Scientific American decades ago.
The more difficult criterion in the problem being discussed in the current SciAm article is that the division be "envy-free". That is, no player believes that his any other player's piece of cake is better than his own.
The spinning algorithm also specifies that the players are to make their cuts "with the aim of making equal-sized pieces", which is another misunderstanding of how the criteria for an algorithm in this sort of problem are to be specified. Once the algorithm for cutting and distributing is specified, it then up to the players to cut and decide as they choose. That's why "one cuts and the other chooses" is a good algorithm, while "one player cuts, with the aim of making the pieces as equal as possible; then the same player chooses a piece" is a poor one; the non-cutter may feel the cutter has not honestly tried to make the pieces equal. The one cuts and the other chooses algorithm makes no requirement on the aims of players in doing the cutting and choosing, but each player is nonetheless satisfied that his piece is at least as big as the other, even if the other player makes his cutting and choosing decisions with the aim of making that not true.
Solution to the n-player "at least 1 nth" problem, without the envy-free criteria.
. . . .
. . . . . . . . . Order the players 1 through n. The lowest-numbered player who has not yet been assigned a piece cuts a piece off of the pie (his best strategy will be to cut a piece he values as a fair slice). Then in order, each other player who has not yet been assigned a slice can either pass, or reduce the size of the proposed piece by cutting some off and returning it to the unassigned portion. The resulting piece is assigned to the last person to use the knife. Repeat until all players but one have been assigned a piece, and give what remains to the remaining player. (while I have numbered the players for definiteness, the consistency of ordering is not required for the correctness of the algorithm; the cutter and order of the other players may be chosen arbitrarily each round.
Andy
On Fri, Dec 15, 2017 at 10:23 AM, Guy Haworth <g.haworth@reading.ac.uk> wrote:
The problem is usually expressed as one of dividing a cake (or pie) and distributing it so that no-one is in a position to complain about the size of their slice ...
There's this ... https://www.scientificamerican.com/ article/the-mathematics-of-cake-cutting/
... and then there's this by Ian Stewart https://www.amazon.co.uk/How- Cut-Cake-Mathematical-Conundrums/dp/0199205906
However, the best solution I know of (which Ian Stewart confirmed he had not heard of) came from the 13-year-old son of a colleague of mine ....
Everyone gets a knife and makes a cut in a circular cake which is standing on a turntable ... with the aim of making equal-size slices.
The cake is then spun, and everyone gets the slice opposite them.
[ In other words, the randomness takes the decision about who gets what away from the hungry mathematicians ]
Guy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.) Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n? Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before? Jim On Fri, Dec 15, 2017 at 12:13 PM, Neil Sloane <njasloane@gmail.com> wrote:
This version of cake-cutting reminds me of the Gift Exchange problem, see our paper in 'Lectronic J. Combin, *Analysis of the Gift Exchange Problem <http://neilsloane.com/doc/Moa10.pdf>*, 2017. Also arXiv:1701.08394 <http://arxiv.org/abs/1701.08394>,
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Fri, Dec 15, 2017 at 12:01 PM, Andy Latto <andy.latto@pobox.com> wrote:
What you characterize as a "best solution" purports to solve a much easier problem than the one discussed in the SA article
The spin-the-cake algorithm is ill-defined; if we define the "places where the people are sitting" as n evenly-spaced points around the circle, it doesn't tell us what to do if to people are sitting in front of the same piece of cake after the spin.
Even if you patch it up, the simplest way to do so being just having one person divide the cake, and a randomization procedure applied to decide who gets which piece, this solves only the problem "no-one is in a position to complain about the fairness of the procedure", a much simpler goal than the one being studied.
This algorithm doesn't even satisfy the weaker criterion "each player believes that they have gotten at least 1 nth of the pie", a problem with a fairly simple solution (given below after spoiler space) that I first saw in a Martin Gardner Mathematical Games column in Scientific American decades ago.
The more difficult criterion in the problem being discussed in the current SciAm article is that the division be "envy-free". That is, no player believes that his any other player's piece of cake is better than his own.
The spinning algorithm also specifies that the players are to make their cuts "with the aim of making equal-sized pieces", which is another misunderstanding of how the criteria for an algorithm in this sort of problem are to be specified. Once the algorithm for cutting and distributing is specified, it then up to the players to cut and decide as they choose. That's why "one cuts and the other chooses" is a good algorithm, while "one player cuts, with the aim of making the pieces as equal as possible; then the same player chooses a piece" is a poor one; the non-cutter may feel the cutter has not honestly tried to make the pieces equal. The one cuts and the other chooses algorithm makes no requirement on the aims of players in doing the cutting and choosing, but each player is nonetheless satisfied that his piece is at least as big as the other, even if the other player makes his cutting and choosing decisions with the aim of making that not true.
Solution to the n-player "at least 1 nth" problem, without the envy-free criteria.
. . . .
. . . . . . . . . Order the players 1 through n. The lowest-numbered player who has not yet been assigned a piece cuts a piece off of the pie (his best strategy will be to cut a piece he values as a fair slice). Then in order, each other player who has not yet been assigned a slice can either pass, or reduce the size of the proposed piece by cutting some off and returning it to the unassigned portion. The resulting piece is assigned to the last person to use the knife. Repeat until all players but one have been assigned a piece, and give what remains to the remaining player. (while I have numbered the players for definiteness, the consistency of ordering is not required for the correctness of the algorithm; the cutter and order of the other players may be chosen arbitrarily each round.
Andy
On Fri, Dec 15, 2017 at 10:23 AM, Guy Haworth <g.haworth@reading.ac.uk> wrote:
The problem is usually expressed as one of dividing a cake (or pie) and distributing it so that no-one is in a position to complain about the size of their slice ...
There's this ... https://www.scientificamerican.com/ article/the-mathematics-of-cake-cutting/
... and then there's this by Ian Stewart https://www.amazon.co.uk/How- Cut-Cake-Mathematical-Conundrums/dp/0199205906
However, the best solution I know of (which Ian Stewart confirmed he had not heard of) came from the 13-year-old son of a colleague of mine ....
Everyone gets a knife and makes a cut in a circular cake which is standing on a turntable ... with the aim of making equal-size slices.
The cake is then spun, and everyone gets the slice opposite them.
[ In other words, the randomness takes the decision about who gets what away from the hungry mathematicians ]
Guy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think f(4) has to be 6. Consider that 1/4 + 1/4 + 1/4 + 1/4 must be possible. If f(4) is 5, then that means three of those 1/4 are indivisible, and the fourth is divisible once, into two fractions that sum to 1/4. So even if those two fractions are added to two of the other 1/4 values, it still leaves one bare 1/4 (and the other two couldn't both be increased to 1/3 anyway). With 6 values, it's easy: 1/12, 1/12, 1/12, 1/4, 1/4, 1/4 works. Tom James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
This is so similar in feel to the "muffin problem" that we talked about a couple of years ago, that I am convinced there must be a relationship between the problems. But I can't recall the original formulation of the muffin problem. I think we can use reasoning like Tom Karzes's to show that f(5) > 7. Five fifths must be possible, and if we have only 7 pieces, then when the five fifths are arranged, there can be only two internal divisions. If those are in the same fifth, then we can't achieve four quarters; if they are in different fifths, then the three atomic fifths must be combined with 1/20 to get to 1/4, and there's no way to generate the required three 1/20 pieces. On Fri, Dec 15, 2017 at 12:50 PM, Tom Karzes <karzes@sonic.net> wrote:
I think f(4) has to be 6. Consider that 1/4 + 1/4 + 1/4 + 1/4 must be possible. If f(4) is 5, then that means three of those 1/4 are indivisible, and the fourth is divisible once, into two fractions that sum to 1/4. So even if those two fractions are added to two of the other 1/4 values, it still leaves one bare 1/4 (and the other two couldn't both be increased to 1/3 anyway).
With 6 values, it's easy: 1/12, 1/12, 1/12, 1/4, 1/4, 1/4 works.
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The formulation of the muiffin problem was: you have m muffins (of equal size) and n people. You want to divide the muffins so that each person gets an equal share. In the original problem one sought such a division so that the smallest piece was as large as possible. In modifications of it, one looked at the sequence of piece sizes ordered from smallest to largest, and then one wanted the lexicographically largest such sequence (i.e. among all the sequences with largest smallest piece, one wanted to maximize the size of the next largest piece, etc.) On Fri, Dec 15, 2017 at 1:00 PM, Allan Wechsler <acwacw@gmail.com> wrote:
This is so similar in feel to the "muffin problem" that we talked about a couple of years ago, that I am convinced there must be a relationship between the problems. But I can't recall the original formulation of the muffin problem.
I think we can use reasoning like Tom Karzes's to show that f(5) > 7. Five fifths must be possible, and if we have only 7 pieces, then when the five fifths are arranged, there can be only two internal divisions. If those are in the same fifth, then we can't achieve four quarters; if they are in different fifths, then the three atomic fifths must be combined with 1/20 to get to 1/4, and there's no way to generate the required three 1/20 pieces.
On Fri, Dec 15, 2017 at 12:50 PM, Tom Karzes <karzes@sonic.net> wrote:
I think f(4) has to be 6. Consider that 1/4 + 1/4 + 1/4 + 1/4 must be possible. If f(4) is 5, then that means three of those 1/4 are indivisible, and the fourth is divisible once, into two fractions that sum to 1/4. So even if those two fractions are added to two of the other 1/4 values, it still leaves one bare 1/4 (and the other two couldn't both be increased to 1/3 anyway).
With 6 values, it's easy: 1/12, 1/12, 1/12, 1/4, 1/4, 1/4 works.
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oh -- in that case my statement was wrong. The current problem shows no concern with the size of the smallest piece. I tried once or twice to show that f(5) > 8; I still think that's true but I don't have a good demonstration. If this intuition is right, then it's either 9 or 10. On Fri, Dec 15, 2017 at 1:28 PM, Victor Miller <victorsmiller@gmail.com> wrote:
The formulation of the muiffin problem was: you have m muffins (of equal size) and n people. You want to divide the muffins so that each person gets an equal share. In the original problem one sought such a division so that the smallest piece was as large as possible. In modifications of it, one looked at the sequence of piece sizes ordered from smallest to largest, and then one wanted the lexicographically largest such sequence (i.e. among all the sequences with largest smallest piece, one wanted to maximize the size of the next largest piece, etc.)
On Fri, Dec 15, 2017 at 1:00 PM, Allan Wechsler <acwacw@gmail.com> wrote:
This is so similar in feel to the "muffin problem" that we talked about a couple of years ago, that I am convinced there must be a relationship between the problems. But I can't recall the original formulation of the muffin problem.
I think we can use reasoning like Tom Karzes's to show that f(5) > 7. Five fifths must be possible, and if we have only 7 pieces, then when the five fifths are arranged, there can be only two internal divisions. If those are in the same fifth, then we can't achieve four quarters; if they are in different fifths, then the three atomic fifths must be combined with 1/20 to get to 1/4, and there's no way to generate the required three 1/20 pieces.
On Fri, Dec 15, 2017 at 12:50 PM, Tom Karzes <karzes@sonic.net> wrote:
I think f(4) has to be 6. Consider that 1/4 + 1/4 + 1/4 + 1/4 must be possible. If f(4) is 5, then that means three of those 1/4 are indivisible, and the fourth is divisible once, into two fractions that sum to 1/4. So even if those two fractions are added to two of the other 1/4 values, it still leaves one bare 1/4 (and the other two couldn't both be increased to 1/3 anyway).
With 6 values, it's easy: 1/12, 1/12, 1/12, 1/4, 1/4, 1/4 works.
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I believe f(5) is at most 10. Here's a 10-value solution for n=5: 3 * 1/5 2 * 1/12 4 * 1/20 1 * 1/30 These can be combined as: 5: 1/5 1/5 1/5 4 * 1/20 2 * 1/12 + 1/30 4: 1/5 + 1/20 1/5 + 1/20 1/5 + 1/20 2 * 1/12 + 1/20 + 1/30 3: 1/5 + 1/12 + 1/20 1/5 + 1/12 + 1/20 1/5 + 2 * 1/20 + 1/30 Since 2 is a factor of 4, it's obtainable by grouping pairs from the 4-slice solution. Can anyone improve this? Tom Tom Karzes writes:
I think f(4) has to be 6. Consider that 1/4 + 1/4 + 1/4 + 1/4 must be possible. If f(4) is 5, then that means three of those 1/4 are indivisible, and the fourth is divisible once, into two fractions that sum to 1/4. So even if those two fractions are added to two of the other 1/4 values, it still leaves one bare 1/4 (and the other two couldn't both be increased to 1/3 anyway).
With 6 values, it's easy: 1/12, 1/12, 1/12, 1/4, 1/4, 1/4 works.
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
I believe an upper bound for f(n) is given by https://oeis.org/A092249 which can be interpreted as the number of segments resulting from slicing the interval [0, 1] into 2, 3, ... n uniform segments. Clearly this satisfies all of the required sums. The first several values are: 1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,... Note that this is also https://oeis.org/A002088 but without the initial zero entry. The question is, is it ever possible to do better than this? Tom James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
If I've been following the bidding up until now, we still don't know whether f(5) is 8, 9, or 10. On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> wrote:
I believe an upper bound for f(n) is given by https://oeis.org/A092249 which can be interpreted as the number of segments resulting from slicing the interval [0, 1] into 2, 3, ... n uniform segments. Clearly this satisfies all of the required sums. The first several values are:
1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,...
Note that this is also https://oeis.org/A002088 but without the initial zero entry.
The question is, is it ever possible to do better than this?
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
That's right. It's definitely one of 8, 9, or 10. I suspect it's 10, but I can't prove it isn't 8 or 9. Tom Allan Wechsler writes:
If I've been following the bidding up until now, we still don't know whether f(5) is 8, 9, or 10.
On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> wrote:
I believe an upper bound for f(n) is given by https://oeis.org/A092249 which can be interpreted as the number of segments resulting from slicing the interval [0, 1] into 2, 3, ... n uniform segments. Clearly this satisfies all of the required sums. The first several values are:
1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,...
Note that this is also https://oeis.org/A002088 but without the initial zero entry.
The question is, is it ever possible to do better than this?
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
I believe I can prove that f(5) is not 8, which leaves either 9 or 10. Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 must be the sum of exactly two smaller component fractions (since the largest possible component fraction is 1/5). Now enumerate the possible component breakdown in the 5 * 1/5 case. The possibilities are: (a) 2, 2, 2, 1, 1 (b) 3, 2, 1, 1, 1 (c) 4, 1, 1, 1, 1 These are all of the ways to divide 5 values into 8 components. In each case, consider what values are required in order to combine these 8 values into 4 * 1/4. In case (a), exactly two of the component values are 1/5. That means two others must be 1/20 in order to make 1/4. 1/5 - 1/20 is 3/20. So we have two instances of (3/20 + 1/20) and two instances of (1/5). That leaves a single pair of values. After pairing (1/5 + 1/20) twice to get 2 * 1/4, we are left needing 2 * 1/4 out of 2 * 3/20 and two other values, which must therefore be 2 * 1/10 since (3/20 + 1/10) is 1/4. So for case (a) we have: 2 * 1/5, 2 * 3/20, 2 * 1/10, 2 * 1/20 In case (b), exactly three of the component values are 1/5. That means that three others must be 1/20 in order to make 1/4. So three other values must 1/20 in other to make 1/4. The only way to get 3 * 1/20 out of the remaining five components, three of which sum to 1/5 and two others of which sum to 1/5, is for one to be (1/10 + 1/20 + 1/20) and the other to be (3/20 + 1/20). So for case (b) we have: 3 * 1/5, 1 * 3/20, 1 * 1/10, 3 * 1/20 In case (c), exactly four of the component values are 1/5. That means that four others must be 1/20 in order to make 1/4. So for case (c) we have: 4 * 1/5, 4 * 1/20 That covers all possible ways to make both 5 * 1/5 and 4 * 1/4 out of 8 component values. However, so far this has completely ignored the need to make 3 * 1/3 from the component values. But this is clearly impossible, since in all cases the LCM of the denominators of the components is 20, and x/20 cannot be 1/3 for integer x. So this rules out f(5) being 8, leaving only 9 and 10 as candidates. It may be possible to rule out 9 using a similar but more convoluted argument, but I have not attempted to do so. Tom Tom Karzes writes:
That's right. It's definitely one of 8, 9, or 10. I suspect it's 10, but I can't prove it isn't 8 or 9.
Tom
Allan Wechsler writes:
If I've been following the bidding up until now, we still don't know whether f(5) is 8, 9, or 10.
On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> wrote:
I believe an upper bound for f(n) is given by https://oeis.org/A092249 which can be interpreted as the number of segments resulting from slicing the interval [0, 1] into 2, 3, ... n uniform segments. Clearly this satisfies all of the required sums. The first several values are:
1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,...
Note that this is also https://oeis.org/A002088 but without the initial zero entry.
The question is, is it ever possible to do better than this?
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
Tom, at first I thought I saw a gap in this logic, but then I realized that in the 4 * 1/4 assembly, all of the quarters must be divided into exactly two pieces. Having realized that lemma, I reread your reasoning and everything made sense. It feels like the LCM machinery you bring in at the very end might be leveraged to carry more of the proof. Now we just have to show f(5) != 9. On Sun, Dec 17, 2017 at 10:41 AM, Tom Karzes <karzes@sonic.net> wrote:
I believe I can prove that f(5) is not 8, which leaves either 9 or 10.
Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 must be the sum of exactly two smaller component fractions (since the largest possible component fraction is 1/5).
Now enumerate the possible component breakdown in the 5 * 1/5 case. The possibilities are:
(a) 2, 2, 2, 1, 1 (b) 3, 2, 1, 1, 1 (c) 4, 1, 1, 1, 1
These are all of the ways to divide 5 values into 8 components.
In each case, consider what values are required in order to combine these 8 values into 4 * 1/4.
In case (a), exactly two of the component values are 1/5. That means two others must be 1/20 in order to make 1/4. 1/5 - 1/20 is 3/20. So we have two instances of (3/20 + 1/20) and two instances of (1/5). That leaves a single pair of values. After pairing (1/5 + 1/20) twice to get 2 * 1/4, we are left needing 2 * 1/4 out of 2 * 3/20 and two other values, which must therefore be 2 * 1/10 since (3/20 + 1/10) is 1/4. So for case (a) we have:
2 * 1/5, 2 * 3/20, 2 * 1/10, 2 * 1/20
In case (b), exactly three of the component values are 1/5. That means that three others must be 1/20 in order to make 1/4. So three other values must 1/20 in other to make 1/4. The only way to get 3 * 1/20 out of the remaining five components, three of which sum to 1/5 and two others of which sum to 1/5, is for one to be (1/10 + 1/20 + 1/20) and the other to be (3/20 + 1/20). So for case (b) we have:
3 * 1/5, 1 * 3/20, 1 * 1/10, 3 * 1/20
In case (c), exactly four of the component values are 1/5. That means that four others must be 1/20 in order to make 1/4. So for case (c) we have:
4 * 1/5, 4 * 1/20
That covers all possible ways to make both 5 * 1/5 and 4 * 1/4 out of 8 component values. However, so far this has completely ignored the need to make 3 * 1/3 from the component values. But this is clearly impossible, since in all cases the LCM of the denominators of the components is 20, and x/20 cannot be 1/3 for integer x.
So this rules out f(5) being 8, leaving only 9 and 10 as candidates. It may be possible to rule out 9 using a similar but more convoluted argument, but I have not attempted to do so.
Tom
Tom Karzes writes:
That's right. It's definitely one of 8, 9, or 10. I suspect it's 10, but I can't prove it isn't 8 or 9.
Tom
Allan Wechsler writes:
If I've been following the bidding up until now, we still don't know whether f(5) is 8, 9, or 10.
On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> wrote:
I believe an upper bound for f(n) is given by https://oeis.org/A092249 which can be interpreted as the number of segments resulting from slicing the interval [0, 1] into 2, 3, ... n uniform segments. Clearly this satisfies all of the required sums. The first several values are:
1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,...
Note that this is also https://oeis.org/A002088 but without the initial zero entry.
The question is, is it ever possible to do better than this?
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hi Allan, Yes, I had mentioned the fact that each 1/4 must be the sum of exactly two components at the very beginning, then didn't mention it again: Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 must be the sum of exactly two smaller component fractions (since the largest possible component fraction is 1/5). I also had the same thought about using the LCM restriction earlier to further contrain the component sizes. I think it's safe to say that at least three of the component fractions must have a factor of 3 in their denominator (when reduced to lowest-terms), since each of the three 1/3 sums must contain at least one such fraction. Further, each 1/5 sum or 1/4 sum that contains one such fraction must contain at least one more such fraction, in order to eliminate the factor of 3. So if there are exactly three such components, then all three must occur together in a single 1/5 sum, and in a single 1/4 sum. Otherwise there must be more than three such fractions. Tom Allan Wechsler writes:
Tom, at first I thought I saw a gap in this logic, but then I realized that in the 4 * 1/4 assembly, all of the quarters must be divided into exactly two pieces. Having realized that lemma, I reread your reasoning and everything made sense.
It feels like the LCM machinery you bring in at the very end might be leveraged to carry more of the proof.
Now we just have to show f(5) != 9.
On Sun, Dec 17, 2017 at 10:41 AM, Tom Karzes <karzes@sonic.net> wrote:
I believe I can prove that f(5) is not 8, which leaves either 9 or 10.
Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 must be the sum of exactly two smaller component fractions (since the largest possible component fraction is 1/5).
Now enumerate the possible component breakdown in the 5 * 1/5 case. The possibilities are:
(a) 2, 2, 2, 1, 1 (b) 3, 2, 1, 1, 1 (c) 4, 1, 1, 1, 1
These are all of the ways to divide 5 values into 8 components.
In each case, consider what values are required in order to combine these 8 values into 4 * 1/4.
In case (a), exactly two of the component values are 1/5. That means two others must be 1/20 in order to make 1/4. 1/5 - 1/20 is 3/20. So we have two instances of (3/20 + 1/20) and two instances of (1/5). That leaves a single pair of values. After pairing (1/5 + 1/20) twice to get 2 * 1/4, we are left needing 2 * 1/4 out of 2 * 3/20 and two other values, which must therefore be 2 * 1/10 since (3/20 + 1/10) is 1/4. So for case (a) we have:
2 * 1/5, 2 * 3/20, 2 * 1/10, 2 * 1/20
In case (b), exactly three of the component values are 1/5. That means that three others must be 1/20 in order to make 1/4. So three other values must 1/20 in other to make 1/4. The only way to get 3 * 1/20 out of the remaining five components, three of which sum to 1/5 and two others of which sum to 1/5, is for one to be (1/10 + 1/20 + 1/20) and the other to be (3/20 + 1/20). So for case (b) we have:
3 * 1/5, 1 * 3/20, 1 * 1/10, 3 * 1/20
In case (c), exactly four of the component values are 1/5. That means that four others must be 1/20 in order to make 1/4. So for case (c) we have:
4 * 1/5, 4 * 1/20
That covers all possible ways to make both 5 * 1/5 and 4 * 1/4 out of 8 component values. However, so far this has completely ignored the need to make 3 * 1/3 from the component values. But this is clearly impossible, since in all cases the LCM of the denominators of the components is 20, and x/20 cannot be 1/3 for integer x.
So this rules out f(5) being 8, leaving only 9 and 10 as candidates. It may be possible to rule out 9 using a similar but more convoluted argument, but I have not attempted to do so.
Tom
Tom Karzes writes:
That's right. It's definitely one of 8, 9, or 10. I suspect it's 10, but I can't prove it isn't 8 or 9.
Tom
Allan Wechsler writes:
If I've been following the bidding up until now, we still don't know whether f(5) is 8, 9, or 10.
On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> wrote:
I believe an upper bound for f(n) is given by https://oeis.org/A092249 which can be interpreted as the number of segments resulting from slicing the interval [0, 1] into 2, 3, ... n uniform segments. Clearly this satisfies all of the required sums. The first several values are:
1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,...
Note that this is also https://oeis.org/A002088 but without the initial zero entry.
The question is, is it ever possible to do better than this?
Tom
James Propp writes:
Perhaps my question has been considered in the past as a question about cutting an interval into pieces, since the circularity of the pie/pizza/whatever is irrelevant. (The very first radial cut effectively turns a problem about cutting a disk into wedges into a problem about cutting an interval into subintervals.)
Or maybe we should get rid of geometry entirely, and just ask: What is the smallest collection of fractions (with repetitions allowed), summing to 1, such that by combining fractions in the collection we can write 1 as 1/2 + 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... + 1/n?
Let f(n) be the smallest possible number of such fractions. Clearly f(1) = 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I haven't figured out f(4) (it's either 5 or 6). Has anyone seen this sequence before?
Jim
My blunder, I just didn't read carefully enough! All seems in order. On Sun, Dec 17, 2017 at 11:54 AM, Tom Karzes <karzes@sonic.net> wrote: > Hi Allan, > > Yes, I had mentioned the fact that each 1/4 must be the sum of exactly > two components at the very beginning, then didn't mention it again: > > Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 > must be the sum of exactly two smaller component fractions (since the > largest possible component fraction is 1/5). > > I also had the same thought about using the LCM restriction earlier to > further contrain the component sizes. I think it's safe to say that > at least three of the component fractions must have a factor of 3 in > their denominator (when reduced to lowest-terms), since each of the > three 1/3 sums must contain at least one such fraction. Further, > each 1/5 sum or 1/4 sum that contains one such fraction must contain > at least one more such fraction, in order to eliminate the factor > of 3. So if there are exactly three such components, then all three > must occur together in a single 1/5 sum, and in a single 1/4 sum. > Otherwise there must be more than three such fractions. > > Tom > > > Allan Wechsler writes: > > Tom, at first I thought I saw a gap in this logic, but then I realized > that > > in the 4 * 1/4 assembly, all of the quarters must be divided into > exactly > > two pieces. Having realized that lemma, I reread your reasoning and > > everything made sense. > > > > It feels like the LCM machinery you bring in at the very end might be > > leveraged to carry more of the proof. > > > > Now we just have to show f(5) != 9. > > > > On Sun, Dec 17, 2017 at 10:41 AM, Tom Karzes <karzes@sonic.net> wrote: > > > > > I believe I can prove that f(5) is not 8, which leaves either 9 or 10. > > > > > > Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 > > > must be the sum of exactly two smaller component fractions (since the > > > largest possible component fraction is 1/5). > > > > > > Now enumerate the possible component breakdown in the 5 * 1/5 case. > > > The possibilities are: > > > > > > (a) 2, 2, 2, 1, 1 > > > (b) 3, 2, 1, 1, 1 > > > (c) 4, 1, 1, 1, 1 > > > > > > These are all of the ways to divide 5 values into 8 components. > > > > > > In each case, consider what values are required in order to combine > > > these 8 values into 4 * 1/4. > > > > > > In case (a), exactly two of the component values are 1/5. That means > > > two others must be 1/20 in order to make 1/4. 1/5 - 1/20 is 3/20. > > > So we have two instances of (3/20 + 1/20) and two instances of (1/5). > > > That leaves a single pair of values. After pairing (1/5 + 1/20) twice > > > to get 2 * 1/4, we are left needing 2 * 1/4 out of 2 * 3/20 and two > > > other values, which must therefore be 2 * 1/10 since (3/20 + 1/10) > > > is 1/4. So for case (a) we have: > > > > > > 2 * 1/5, 2 * 3/20, 2 * 1/10, 2 * 1/20 > > > > > > In case (b), exactly three of the component values are 1/5. That > > > means that three others must be 1/20 in order to make 1/4. So > > > three other values must 1/20 in other to make 1/4. The only way > > > to get 3 * 1/20 out of the remaining five components, three of which > > > sum to 1/5 and two others of which sum to 1/5, is for one to be > > > (1/10 + 1/20 + 1/20) and the other to be (3/20 + 1/20). So for > > > case (b) we have: > > > > > > 3 * 1/5, 1 * 3/20, 1 * 1/10, 3 * 1/20 > > > > > > In case (c), exactly four of the component values are 1/5. That > > > means that four others must be 1/20 in order to make 1/4. So > > > for case (c) we have: > > > > > > 4 * 1/5, 4 * 1/20 > > > > > > That covers all possible ways to make both 5 * 1/5 and 4 * 1/4 > > > out of 8 component values. However, so far this has completely > > > ignored the need to make 3 * 1/3 from the component values. But > > > this is clearly impossible, since in all cases the LCM of the > > > denominators of the components is 20, and x/20 cannot be 1/3 > > > for integer x. > > > > > > So this rules out f(5) being 8, leaving only 9 and 10 as candidates. > > > It may be possible to rule out 9 using a similar but more convoluted > > > argument, but I have not attempted to do so. > > > > > > Tom > > > > > > > > > Tom Karzes writes: > > > > That's right. It's definitely one of 8, 9, or 10. I suspect it's > 10, > > > > but I can't prove it isn't 8 or 9. > > > > > > > > Tom > > > > > > > > Allan Wechsler writes: > > > > > If I've been following the bidding up until now, we still don't > know > > > > > whether f(5) is 8, 9, or 10. > > > > > > > > > > On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> > > > wrote: > > > > > > > > > > > I believe an upper bound for f(n) is given by > > > https://oeis.org/A092249 > > > > > > which can be interpreted as the number of segments resulting > from > > > slicing > > > > > > the interval [0, 1] into 2, 3, ... n uniform segments. > Clearly > > > this > > > > > > satisfies all of the required sums. The first several values > are: > > > > > > > > > > > > 1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,... > > > > > > > > > > > > Note that this is also https://oeis.org/A002088 but without > the > > > initial > > > > > > zero entry. > > > > > > > > > > > > The question is, is it ever possible to do better than this? > > > > > > > > > > > > Tom > > > > > > > > > > > > > > > > > > James Propp writes: > > > > > > > Perhaps my question has been considered in the past as a > > > question about > > > > > > > cutting an interval into pieces, since the circularity of > the > > > > > > > pie/pizza/whatever is irrelevant. (The very first radial > cut > > > effectively > > > > > > > turns a problem about cutting a disk into wedges into a > problem > > > about > > > > > > > cutting an interval into subintervals.) > > > > > > > > > > > > > > Or maybe we should get rid of geometry entirely, and just > ask: > > > What is > > > > > > the > > > > > > > smallest collection of fractions (with repetitions > allowed), > > > summing to > > > > > > 1, > > > > > > > such that by combining fractions in the collection we can > write > > > 1 as > > > > > > 1/2 + > > > > > > > 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... > + 1/n? > > > > > > > > > > > > > > Let f(n) be the smallest possible number of such fractions. > > > Clearly > > > > > > f(1) = > > > > > > > 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I > > > haven't > > > > > > figured > > > > > > > out f(4) (it's either 5 or 6). Has anyone seen this > sequence > > > before? > > > > > > > > > > > > > > Jim > > > > > > > > > > > > > > > > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.) Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do. But I can't even prove the lemma. On Sun, Dec 17, 2017 at 12:00 PM, Allan Wechsler <acwacw@gmail.com> wrote: > My blunder, I just didn't read carefully enough! All seems in order. > > On Sun, Dec 17, 2017 at 11:54 AM, Tom Karzes <karzes@sonic.net> wrote: > >> Hi Allan, >> >> Yes, I had mentioned the fact that each 1/4 must be the sum of exactly >> two components at the very beginning, then didn't mention it again: >> >> Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 >> must be the sum of exactly two smaller component fractions (since the >> largest possible component fraction is 1/5). >> >> I also had the same thought about using the LCM restriction earlier to >> further contrain the component sizes. I think it's safe to say that >> at least three of the component fractions must have a factor of 3 in >> their denominator (when reduced to lowest-terms), since each of the >> three 1/3 sums must contain at least one such fraction. Further, >> each 1/5 sum or 1/4 sum that contains one such fraction must contain >> at least one more such fraction, in order to eliminate the factor >> of 3. So if there are exactly three such components, then all three >> must occur together in a single 1/5 sum, and in a single 1/4 sum. >> Otherwise there must be more than three such fractions. >> >> Tom >> >> >> Allan Wechsler writes: >> > Tom, at first I thought I saw a gap in this logic, but then I realized >> that >> > in the 4 * 1/4 assembly, all of the quarters must be divided into >> exactly >> > two pieces. Having realized that lemma, I reread your reasoning and >> > everything made sense. >> > >> > It feels like the LCM machinery you bring in at the very end might be >> > leveraged to carry more of the proof. >> > >> > Now we just have to show f(5) != 9. >> > >> > On Sun, Dec 17, 2017 at 10:41 AM, Tom Karzes <karzes@sonic.net> wrote: >> > >> > > I believe I can prove that f(5) is not 8, which leaves either 9 or >> 10. >> > > >> > > Proof: If we assume f(5) is 8, then in the 4 * 1/4 case, each 1/4 >> > > must be the sum of exactly two smaller component fractions (since the >> > > largest possible component fraction is 1/5). >> > > >> > > Now enumerate the possible component breakdown in the 5 * 1/5 case. >> > > The possibilities are: >> > > >> > > (a) 2, 2, 2, 1, 1 >> > > (b) 3, 2, 1, 1, 1 >> > > (c) 4, 1, 1, 1, 1 >> > > >> > > These are all of the ways to divide 5 values into 8 components. >> > > >> > > In each case, consider what values are required in order to combine >> > > these 8 values into 4 * 1/4. >> > > >> > > In case (a), exactly two of the component values are 1/5. That means >> > > two others must be 1/20 in order to make 1/4. 1/5 - 1/20 is 3/20. >> > > So we have two instances of (3/20 + 1/20) and two instances of (1/5). >> > > That leaves a single pair of values. After pairing (1/5 + 1/20) twice >> > > to get 2 * 1/4, we are left needing 2 * 1/4 out of 2 * 3/20 and two >> > > other values, which must therefore be 2 * 1/10 since (3/20 + 1/10) >> > > is 1/4. So for case (a) we have: >> > > >> > > 2 * 1/5, 2 * 3/20, 2 * 1/10, 2 * 1/20 >> > > >> > > In case (b), exactly three of the component values are 1/5. That >> > > means that three others must be 1/20 in order to make 1/4. So >> > > three other values must 1/20 in other to make 1/4. The only way >> > > to get 3 * 1/20 out of the remaining five components, three of which >> > > sum to 1/5 and two others of which sum to 1/5, is for one to be >> > > (1/10 + 1/20 + 1/20) and the other to be (3/20 + 1/20). So for >> > > case (b) we have: >> > > >> > > 3 * 1/5, 1 * 3/20, 1 * 1/10, 3 * 1/20 >> > > >> > > In case (c), exactly four of the component values are 1/5. That >> > > means that four others must be 1/20 in order to make 1/4. So >> > > for case (c) we have: >> > > >> > > 4 * 1/5, 4 * 1/20 >> > > >> > > That covers all possible ways to make both 5 * 1/5 and 4 * 1/4 >> > > out of 8 component values. However, so far this has completely >> > > ignored the need to make 3 * 1/3 from the component values. But >> > > this is clearly impossible, since in all cases the LCM of the >> > > denominators of the components is 20, and x/20 cannot be 1/3 >> > > for integer x. >> > > >> > > So this rules out f(5) being 8, leaving only 9 and 10 as candidates. >> > > It may be possible to rule out 9 using a similar but more convoluted >> > > argument, but I have not attempted to do so. >> > > >> > > Tom >> > > >> > > >> > > Tom Karzes writes: >> > > > That's right. It's definitely one of 8, 9, or 10. I suspect >> it's 10, >> > > > but I can't prove it isn't 8 or 9. >> > > > >> > > > Tom >> > > > >> > > > Allan Wechsler writes: >> > > > > If I've been following the bidding up until now, we still >> don't know >> > > > > whether f(5) is 8, 9, or 10. >> > > > > >> > > > > On Sat, Dec 16, 2017 at 5:59 PM, Tom Karzes <karzes@sonic.net> >> > > wrote: >> > > > > >> > > > > > I believe an upper bound for f(n) is given by >> > > https://oeis.org/A092249 >> > > > > > which can be interpreted as the number of segments resulting >> from >> > > slicing >> > > > > > the interval [0, 1] into 2, 3, ... n uniform segments. >> Clearly >> > > this >> > > > > > satisfies all of the required sums. The first several >> values are: >> > > > > > >> > > > > > 1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,... >> > > > > > >> > > > > > Note that this is also https://oeis.org/A002088 but without >> the >> > > initial >> > > > > > zero entry. >> > > > > > >> > > > > > The question is, is it ever possible to do better than this? >> > > > > > >> > > > > > Tom >> > > > > > >> > > > > > >> > > > > > James Propp writes: >> > > > > > > Perhaps my question has been considered in the past as a >> > > question about >> > > > > > > cutting an interval into pieces, since the circularity of >> the >> > > > > > > pie/pizza/whatever is irrelevant. (The very first radial >> cut >> > > effectively >> > > > > > > turns a problem about cutting a disk into wedges into a >> problem >> > > about >> > > > > > > cutting an interval into subintervals.) >> > > > > > > >> > > > > > > Or maybe we should get rid of geometry entirely, and just >> ask: >> > > What is >> > > > > > the >> > > > > > > smallest collection of fractions (with repetitions >> allowed), >> > > summing to >> > > > > > 1, >> > > > > > > such that by combining fractions in the collection we can >> write >> > > 1 as >> > > > > > 1/2 + >> > > > > > > 1/2, or as 1/3 + 1/3 + 1/3, or ..., or as 1/n + 1/n + ... >> + 1/n? >> > > > > > > >> > > > > > > Let f(n) be the smallest possible number of such >> fractions. >> > > Clearly >> > > > > > f(1) = >> > > > > > > 1 and f(2) = 2, and it's not hard to show that f(3) = 4. I >> > > haven't >> > > > > > figured >> > > > > > > out f(4) (it's either 5 or 6). Has anyone seen this >> sequence >> > > before? >> > > > > > > >> > > > > > > Jim >> > > > > > > >> > > > > > >> > > >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values: 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 Can we always do as well (or better) using only rational component values? I suspect the answer is yes. Note that the example above has the general form: 1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3 1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6) This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution? Tom Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these. On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem. On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back. Victor Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1} 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k We can linearize (2) by using big-M: z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing. Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n. On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller <victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6 On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller <victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller <victorsmiller@gmail.com> wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller <victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts! And your 11-part solution for f(6) also beats a simple union of divisions into equal parts! Have you tried f(7), or is that past what it can handle? Tom Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller <victorsmiller@gmail.com> wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller <victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes: > I was challenging myself to try to think of any finite algorithm, be it > ever so expensive and cumbersome, that would settle the question of whether > p pieces suffices for a given n. A useful lemma would be that if it can be > done in p pieces, then it can be done with pieces whose denominaters divide > n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't > matter how weak this lemma is.) > > Then, we could say, "Iterate over all partitions of n! into p parts, and > for each such partition, check to see if it works, using the partition as > the numerators of fractions whose denominators are all n!." This would be > heinously expensive but it would at least provide an upper bound on how > much computational work we have to do. > > But I can't even prove the lemma. >
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12. Victor On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller <victorsmiller@gmail.com
wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
> Can you prove that it's safe to ignore irrational solutions? Here's a > (non-optimal) irrational solution for f(3), using 5 component values: > > 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 > 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 > 1/3 = 1/3 > > 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 > 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 > > Can we always do as well (or better) using only rational component > values? > I suspect the answer is yes. > > Note that the example above has the general form: > > 1/3 = a + (1/3 - a) > 1/3 = (1/2 - a) + (a - 1/6) > 1/3 = 1/3 > > 1/2 = a + (1/2 - a) > 1/2 = 1/3 + (1/3 - a) + (a - 1/6) > > This works for any value of "a" that doesn't produce zero or negative > values. In particular, "a" can be given a rational value. Is it the > case that any solution involving irrational values can be decomposed > into something like this, which in turn can be converted into a > rational solution? > > Tom > > > Allan Wechsler writes: > > I was challenging myself to try to think of any finite algorithm, > be it > > ever so expensive and cumbersome, that would settle the question of > whether > > p pieces suffices for a given n. A useful lemma would be that if it > can be > > done in p pieces, then it can be done with pieces whose > denominaters divide > > n!. (LCM(1,...,n) would be even stronger, but for my purposes it > doesn't > > matter how weak this lemma is.) > > > > Then, we could say, "Iterate over all partitions of n! into p > parts, and > > for each such partition, check to see if it works, using the > partition as > > the numerators of fractions whose denominators are all n!." This > would be > > heinously expensive but it would at least provide an upper bound on > how > > much computational work we have to do. > > > > But I can't even prove the lemma. > > >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249 1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7 Tom Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller <victorsmiller@gmail.com
wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> wrote:
> Here's a proof that there are optimal rational solutions: For a > putatitve solution to f(n) = k, you can write a mixed integer program which > will say whether or not there is such a solution. The only integer > variables are 0/1 variables which indicate whether "piece" i contributes to > a particular sum producing 1/n. There are only a finite number of settings > for these. Once you have done this the remainder is a polytope bounded by > half spaces with integer coefficients. So the vertices of the polytope > have rational coefficients. An optimal solution must be among these. > > On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote: > >> Can you prove that it's safe to ignore irrational solutions? Here's a >> (non-optimal) irrational solution for f(3), using 5 component values: >> >> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >> 1/3 = 1/3 >> >> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 >> >> Can we always do as well (or better) using only rational component >> values? >> I suspect the answer is yes. >> >> Note that the example above has the general form: >> >> 1/3 = a + (1/3 - a) >> 1/3 = (1/2 - a) + (a - 1/6) >> 1/3 = 1/3 >> >> 1/2 = a + (1/2 - a) >> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >> >> This works for any value of "a" that doesn't produce zero or negative >> values. In particular, "a" can be given a rational value. Is it the >> case that any solution involving irrational values can be decomposed >> into something like this, which in turn can be converted into a >> rational solution? >> >> Tom >> >> >> Allan Wechsler writes: >> > I was challenging myself to try to think of any finite algorithm, >> be it >> > ever so expensive and cumbersome, that would settle the question of >> whether >> > p pieces suffices for a given n. A useful lemma would be that if it >> can be >> > done in p pieces, then it can be done with pieces whose >> denominaters divide >> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it >> doesn't >> > matter how weak this lemma is.) >> > >> > Then, we could say, "Iterate over all partitions of n! into p >> parts, and >> > for each such partition, check to see if it works, using the >> partition as >> > the numerators of fractions whose denominators are all n!." This >> would be >> > heinously expensive but it would at least provide an upper bound on >> how >> > much computational work we have to do. >> > >> > But I can't even prove the lemma. >> > >>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
Tom, Thanks. It's always a bit of a mystery what cplex does under the covers. In the meantime, here's a different solutions for f(6) (these are the numerators over 60): 1,1,2,2,4,5,7,8,10,10,10 On Mon, Dec 18, 2017 at 3:29 PM, Tom Karzes <karzes@sonic.net> wrote:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com
wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] = 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> wrote:
> More specifically let x[1], ..., x[k] be non-negative variables <= 1, > and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 > means that x[i] contributes to the j-th 1/i. We then have > 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= > 1 if you want to omit that piece). You might object that sum(j) y[i,j] * > x[j] isn't linear. You can fix this by introducting new variables > z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by > z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving > this to a MIP solver is a finite algorithm for the problem. > > On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> > wrote: > >> Here's a proof that there are optimal rational solutions: For a >> putatitve solution to f(n) = k, you can write a mixed integer program which >> will say whether or not there is such a solution. The only integer >> variables are 0/1 variables which indicate whether "piece" i contributes to >> a particular sum producing 1/n. There are only a finite number of settings >> for these. Once you have done this the remainder is a polytope bounded by >> half spaces with integer coefficients. So the vertices of the polytope >> have rational coefficients. An optimal solution must be among these. >> >> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net
wrote:
>> >>> Can you prove that it's safe to ignore irrational solutions? Here's a >>> (non-optimal) irrational solution for f(3), using 5 component values: >>> >>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >>> 1/3 = 1/3 >>> >>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 >>> >>> Can we always do as well (or better) using only rational component >>> values? >>> I suspect the answer is yes. >>> >>> Note that the example above has the general form: >>> >>> 1/3 = a + (1/3 - a) >>> 1/3 = (1/2 - a) + (a - 1/6) >>> 1/3 = 1/3 >>> >>> 1/2 = a + (1/2 - a) >>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >>> >>> This works for any value of "a" that doesn't produce zero or negative >>> values. In particular, "a" can be given a rational value. Is it the >>> case that any solution involving irrational values can be decomposed >>> into something like this, which in turn can be converted into a >>> rational solution? >>> >>> Tom >>> >>> >>> Allan Wechsler writes: >>> > I was challenging myself to try to think of any finite algorithm, >>> be it >>> > ever so expensive and cumbersome, that would settle the question of >>> whether >>> > p pieces suffices for a given n. A useful lemma would be that if it >>> can be >>> > done in p pieces, then it can be done with pieces whose >>> denominaters divide >>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it >>> doesn't >>> > matter how weak this lemma is.) >>> > >>> > Then, we could say, "Iterate over all partitions of n! into p >>> parts, and >>> > for each such partition, check to see if it works, using the >>> partition as >>> > the numerators of fractions whose denominators are all n!." This >>> would be >>> > heinously expensive but it would at least provide an upper bound on >>> how >>> > much computational work we have to do. >>> > >>> > But I can't even prove the lemma. >>> > >>>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7. There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n. I'd like to say F(n) <= F(n-1) + phi(n), but I can only get F(n) <= F(n-1) + (n - maximum-proper-divisor(n)) I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping. We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n. Rich ----------- Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller <victorsmiller@gmail.com
wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> wrote:
> More specifically let x[1], ..., x[k] be non-negative variables <= 1, > and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 > means that x[i] contributes to the j-th 1/i. We then have > 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= > 1 if you want to omit that piece). You might object that sum(j) y[i,j] * > x[j] isn't linear. You can fix this by introducting new variables > z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by > z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving > this to a MIP solver is a finite algorithm for the problem. > > On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> > wrote: > >> Here's a proof that there are optimal rational solutions: For a >> putatitve solution to f(n) = k, you can write a mixed integer program which >> will say whether or not there is such a solution. The only integer >> variables are 0/1 variables which indicate whether "piece" i contributes to >> a particular sum producing 1/n. There are only a finite number of settings >> for these. Once you have done this the remainder is a polytope bounded by >> half spaces with integer coefficients. So the vertices of the polytope >> have rational coefficients. An optimal solution must be among these. >> >> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote: >> >>> Can you prove that it's safe to ignore irrational solutions? Here's a >>> (non-optimal) irrational solution for f(3), using 5 component values: >>> >>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >>> 1/3 = 1/3 >>> >>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 >>> >>> Can we always do as well (or better) using only rational component >>> values? >>> I suspect the answer is yes. >>> >>> Note that the example above has the general form: >>> >>> 1/3 = a + (1/3 - a) >>> 1/3 = (1/2 - a) + (a - 1/6) >>> 1/3 = 1/3 >>> >>> 1/2 = a + (1/2 - a) >>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >>> >>> This works for any value of "a" that doesn't produce zero or negative >>> values. In particular, "a" can be given a rational value. Is it the >>> case that any solution involving irrational values can be decomposed >>> into something like this, which in turn can be converted into a >>> rational solution? >>> >>> Tom >>> >>> >>> Allan Wechsler writes: >>> > I was challenging myself to try to think of any finite algorithm, >>> be it >>> > ever so expensive and cumbersome, that would settle the question of >>> whether >>> > p pieces suffices for a given n. A useful lemma would be that if it >>> can be >>> > done in p pieces, then it can be done with pieces whose >>> denominaters divide >>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it >>> doesn't >>> > matter how weak this lemma is.) >>> > >>> > Then, we could say, "Iterate over all partitions of n! into p >>> parts, and >>> > for each such partition, check to see if it works, using the >>> partition as >>> > the numerators of fractions whose denominators are all n!." This >>> would be >>> > heinously expensive but it would at least provide an upper bound on >>> how >>> > much computational work we have to do. >>> > >>> > But I can't even prove the lemma. >>> > >>>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it. On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com
wrote:
I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6
On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> wrote:
> Slight correction in my last post. Here is the correct version. > Tomorrow, when I get into work, I'll give the f(5) problem to cplex and > report back. > > Victor > > Solve the following problem -- given a positive integer n > 1, and a > positive integer k decide if there are k reals x[1], ..., x[k] >= 0 > such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, > r=1,...,i in {0,1} > > 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i > 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > 3) x[j] in [0, 1/n] for j=1,..., k > > We can linearize (2) by using big-M: > > z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > > (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) > > There's lots of symmetries. We can (partially) break them by insisting > that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are > lexicographically increasing. > > Also, as remarked before, we don't need to put any conditions for i, for > which a non-trivial multiple is <=n. > > > On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> > wrote: > >> More specifically let x[1], ..., x[k] be non-negative variables <= 1, >> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 >> means that x[i] contributes to the j-th 1/i. We then have >> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= >> 1 if you want to omit that piece). You might object that sum(j) y[i,j] * >> x[j] isn't linear. You can fix this by introducting new variables >> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by >> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving >> this to a MIP solver is a finite algorithm for the problem. >> >> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> >> wrote: >> >>> Here's a proof that there are optimal rational solutions: For a >>> putatitve solution to f(n) = k, you can write a mixed integer program which >>> will say whether or not there is such a solution. The only integer >>> variables are 0/1 variables which indicate whether "piece" i contributes to >>> a particular sum producing 1/n. There are only a finite number of settings >>> for these. Once you have done this the remainder is a polytope bounded by >>> half spaces with integer coefficients. So the vertices of the polytope >>> have rational coefficients. An optimal solution must be among these. >>> >>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < karzes@sonic.net> wrote: >>> >>>> Can you prove that it's safe to ignore irrational solutions? Here's a >>>> (non-optimal) irrational solution for f(3), using 5 component values: >>>> >>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >>>> 1/3 = 1/3 >>>> >>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 >>>> >>>> Can we always do as well (or better) using only rational component >>>> values? >>>> I suspect the answer is yes. >>>> >>>> Note that the example above has the general form: >>>> >>>> 1/3 = a + (1/3 - a) >>>> 1/3 = (1/2 - a) + (a - 1/6) >>>> 1/3 = 1/3 >>>> >>>> 1/2 = a + (1/2 - a) >>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >>>> >>>> This works for any value of "a" that doesn't produce zero or negative >>>> values. In particular, "a" can be given a rational value. Is it the >>>> case that any solution involving irrational values can be decomposed >>>> into something like this, which in turn can be converted into a >>>> rational solution? >>>> >>>> Tom >>>> >>>> >>>> Allan Wechsler writes: >>>> > I was challenging myself to try to think of any finite algorithm, >>>> be it >>>> > ever so expensive and cumbersome, that would settle the question of >>>> whether >>>> > p pieces suffices for a given n. A useful lemma would be that if it >>>> can be >>>> > done in p pieces, then it can be done with pieces whose >>>> denominaters divide >>>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it >>>> doesn't >>>> > matter how weak this lemma is.) >>>> > >>>> > Then, we could say, "Iterate over all partitions of n! into p >>>> parts, and >>>> > for each such partition, check to see if it works, using the >>>> partition as >>>> > the numerators of fractions whose denominators are all n!." This >>>> would be >>>> > heinously expensive but it would at least provide an upper bound on >>>> how >>>> > much computational work we have to do. >>>> > >>>> > But I can't even prove the lemma. >>>> > >>>>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)? Jim On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com
wrote:
> I coded the model in cplex (I'll give the slightly corrected version > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, > 1/10, 3/20, 1/6, 1/5, 1/5 > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, > 1/6 > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> > wrote: > >> Slight correction in my last post. Here is the correct version. >> Tomorrow, when I get into work, I'll give the f(5) problem to cplex and >> report back. >> >> Victor >> >> Solve the following problem -- given a positive integer n > 1, and a >> positive integer k decide if there are k reals x[1], ..., x[k] >= 0 >> such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, >> r=1,...,i in {0,1} >> >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i >> 3) x[j] in [0, 1/n] for j=1,..., k >> >> We can linearize (2) by using big-M: >> >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] >> >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) >> >> There's lots of symmetries. We can (partially) break them by insisting >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are >> lexicographically increasing. >> >> Also, as remarked before, we don't need to put any conditions for i, for >> which a non-trivial multiple is <=n. >> >> >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> >> wrote: >> >>> More specifically let x[1], ..., x[k] be non-negative variables <= 1, >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 >>> means that x[i] contributes to the j-th 1/i. We then have >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= >>> 1 if you want to omit that piece). You might object that sum(j) y[i,j] * >>> x[j] isn't linear. You can fix this by introducting new variables >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving >>> this to a MIP solver is a finite algorithm for the problem. >>> >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> >>> wrote: >>> >>>> Here's a proof that there are optimal rational solutions: For a >>>> putatitve solution to f(n) = k, you can write a mixed integer program which >>>> will say whether or not there is such a solution. The only integer >>>> variables are 0/1 variables which indicate whether "piece" i contributes to >>>> a particular sum producing 1/n. There are only a finite number of settings >>>> for these. Once you have done this the remainder is a polytope bounded by >>>> half spaces with integer coefficients. So the vertices of the polytope >>>> have rational coefficients. An optimal solution must be among these. >>>> >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < karzes@sonic.net> wrote: >>>> >>>>> Can you prove that it's safe to ignore irrational solutions? Here's a >>>>> (non-optimal) irrational solution for f(3), using 5 component values: >>>>> >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >>>>> 1/3 = 1/3 >>>>> >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 >>>>> >>>>> Can we always do as well (or better) using only rational component >>>>> values? >>>>> I suspect the answer is yes. >>>>> >>>>> Note that the example above has the general form: >>>>> >>>>> 1/3 = a + (1/3 - a) >>>>> 1/3 = (1/2 - a) + (a - 1/6) >>>>> 1/3 = 1/3 >>>>> >>>>> 1/2 = a + (1/2 - a) >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >>>>> >>>>> This works for any value of "a" that doesn't produce zero or negative >>>>> values. In particular, "a" can be given a rational value. Is it the >>>>> case that any solution involving irrational values can be decomposed >>>>> into something like this, which in turn can be converted into a >>>>> rational solution? >>>>> >>>>> Tom >>>>> >>>>> >>>>> Allan Wechsler writes: >>>>> > I was challenging myself to try to think of any finite algorithm, >>>>> be it >>>>> > ever so expensive and cumbersome, that would settle the question of >>>>> whether >>>>> > p pieces suffices for a given n. A useful lemma would be that if it >>>>> can be >>>>> > done in p pieces, then it can be done with pieces whose >>>>> denominaters divide >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it >>>>> doesn't >>>>> > matter how weak this lemma is.) >>>>> > >>>>> > Then, we could say, "Iterate over all partitions of n! into p >>>>> parts, and >>>>> > for each such partition, check to see if it works, using the >>>>> partition as >>>>> > the numerators of fractions whose denominators are all n!." This >>>>> would be >>>>> > heinously expensive but it would at least provide an upper bound on >>>>> how >>>>> > much computational work we have to do. >>>>> > >>>>> > But I can't even prove the lemma. >>>>> > >>>>>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286. OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)? The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6. On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts!
And your 11-part solution for f(6) also beats a simple union of divisions into equal parts!
Have you tried f(7), or is that past what it can handle?
Tom
Victor Miller writes: > Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com > > wrote: > > > I coded the model in cplex (I'll give the slightly corrected version > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, > > 1/10, 3/20, 1/6, 1/5, 1/5 > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, > > 1/6 > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < victorsmiller@gmail.com> > > wrote: > > > >> Slight correction in my last post. Here is the correct version. > >> Tomorrow, when I get into work, I'll give the f(5) problem to cplex and > >> report back. > >> > >> Victor > >> > >> Solve the following problem -- given a positive integer n
1, and a
> >> positive integer k decide if there are k reals x[1], ..., x[k] >= 0 > >> such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, > >> r=1,...,i in {0,1} > >> > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > >> 3) x[j] in [0, 1/n] for j=1,..., k > >> > >> We can linearize (2) by using big-M: > >> > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > >> > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) > >> > >> There's lots of symmetries. We can (partially) break them by insisting > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are > >> lexicographically increasing. > >> > >> Also, as remarked before, we don't need to put any conditions for i, for > >> which a non-trivial multiple is <=n. > >> > >> > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < victorsmiller@gmail.com> > >> wrote: > >> > >>> More specifically let x[1], ..., x[k] be non-negative variables <= 1, > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 > >>> means that x[i] contributes to the j-th 1/i. We then have > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= > >>> 1 if you want to omit that piece). You might object that sum(j) y[i,j] * > >>> x[j] isn't linear. You can fix this by introducting new variables > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving > >>> this to a MIP solver is a finite algorithm for the problem. > >>> > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < victorsmiller@gmail.com> > >>> wrote: > >>> > >>>> Here's a proof that there are optimal rational solutions: For a > >>>> putatitve solution to f(n) = k, you can write a mixed integer program which > >>>> will say whether or not there is such a solution. The only integer > >>>> variables are 0/1 variables which indicate whether "piece" i contributes to > >>>> a particular sum producing 1/n. There are only a finite number of settings > >>>> for these. Once you have done this the remainder is a polytope bounded by > >>>> half spaces with integer coefficients. So the vertices of the polytope > >>>> have rational coefficients. An optimal solution must be among these. > >>>> > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < karzes@sonic.net> wrote: > >>>> > >>>>> Can you prove that it's safe to ignore irrational solutions? Here's a > >>>>> (non-optimal) irrational solution for f(3), using 5 component values: > >>>>> > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 > >>>>> 1/3 = 1/3 > >>>>> > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 > >>>>> > >>>>> Can we always do as well (or better) using only rational component > >>>>> values? > >>>>> I suspect the answer is yes. > >>>>> > >>>>> Note that the example above has the general form: > >>>>> > >>>>> 1/3 = a + (1/3 - a) > >>>>> 1/3 = (1/2 - a) + (a - 1/6) > >>>>> 1/3 = 1/3 > >>>>> > >>>>> 1/2 = a + (1/2 - a) > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) > >>>>> > >>>>> This works for any value of "a" that doesn't produce zero or negative > >>>>> values. In particular, "a" can be given a rational value. Is it the > >>>>> case that any solution involving irrational values can be decomposed > >>>>> into something like this, which in turn can be converted into a > >>>>> rational solution? > >>>>> > >>>>> Tom > >>>>> > >>>>> > >>>>> Allan Wechsler writes: > >>>>> > I was challenging myself to try to think of any finite algorithm, > >>>>> be it > >>>>> > ever so expensive and cumbersome, that would settle the question of > >>>>> whether > >>>>> > p pieces suffices for a given n. A useful lemma would be that if it > >>>>> can be > >>>>> > done in p pieces, then it can be done with pieces whose > >>>>> denominaters divide > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes it > >>>>> doesn't > >>>>> > matter how weak this lemma is.) > >>>>> > > >>>>> > Then, we could say, "Iterate over all partitions of n! into p > >>>>> parts, and > >>>>> > for each such partition, check to see if it works, using the > >>>>> partition as > >>>>> > the numerators of fractions whose denominators are all n!." This > >>>>> would be > >>>>> > heinously expensive but it would at least provide an upper bound on > >>>>> how > >>>>> > much computational work we have to do. > >>>>> > > >>>>> > But I can't even prove the lemma. > >>>>> > > >>>>>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html I was thinking about the problem last night and came up with the following: 1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1) + (5-1) + (6-1) + (7-1) - 1 = 17 for f(7). On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes:
Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a tentative upper bound for the number of parts, and let it optimize it. I suspect that the previously conjectured upper bound from A092249 isn't right. Just to see if I could give it a much larger space to explore, I gave it a tentative upper bound of 112 and after a few minutes it hasn't even found any feasible solution! The only thing that it's proved so far is that f(7) >= 12.
Victor
On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote:
> Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution > beats a simple union of divisions into equal parts! > > And your 11-part solution for f(6) also beats a simple union of divisions > into equal parts! > > Have you tried f(7), or is that past what it can handle? > > Tom > > Victor Miller writes: > > Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, > 1/30, > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 > > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com > > > > wrote: > > > > > I coded the model in cplex (I'll give the slightly corrected version > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, > > > 1/10, 3/20, 1/6, 1/5, 1/5 > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, > 1/6, > > > 1/6 > > > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < > victorsmiller@gmail.com> > > > wrote: > > > > > >> Slight correction in my last post. Here is the correct version. > > >> Tomorrow, when I get into work, I'll give the f(5) problem to cplex > and > > >> report back. > > >> > > >> Victor > > >> > > >> Solve the following problem -- given a positive integer n
1, and a
> > >> positive integer k decide if there are k reals x[1], ..., x[k] >= 0 > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, > > >> r=1,...,i in {0,1} > > >> > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for > each i > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > > >> 3) x[j] in [0, 1/n] for j=1,..., k > > >> > > >> We can linearize (2) by using big-M: > > >> > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > > >> > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) > > >> > > >> There's lots of symmetries. We can (partially) break them by > insisting > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k > are > > >> lexicographically increasing. > > >> > > >> Also, as remarked before, we don't need to put any conditions for i, > for > > >> which a non-trivial multiple is <=n. > > >> > > >> > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < > victorsmiller@gmail.com> > > >> wrote: > > >> > > >>> More specifically let x[1], ..., x[k] be non-negative variables <= > 1, > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value > of 1 > > >>> means that x[i] contributes to the j-th 1/i. We then have > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or > maybe <= > > >>> 1 if you want to omit that piece). You might object that sum(j) > y[i,j] * > > >>> x[j] isn't linear. You can fix this by introducting new variables > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this > by > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So > giving > > >>> this to a MIP solver is a finite algorithm for the problem. > > >>> > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < > victorsmiller@gmail.com> > > >>> wrote: > > >>> > > >>>> Here's a proof that there are optimal rational solutions: For a > > >>>> putatitve solution to f(n) = k, you can write a mixed integer > program which > > >>>> will say whether or not there is such a solution. The only integer > > >>>> variables are 0/1 variables which indicate whether "piece" i > contributes to > > >>>> a particular sum producing 1/n. There are only a finite number of > settings > > >>>> for these. Once you have done this the remainder is a polytope > bounded by > > >>>> half spaces with integer coefficients. So the vertices of the > polytope > > >>>> have rational coefficients. An optimal solution must be among > these. > > >>>> > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < karzes@sonic.net> > wrote: > > >>>> > > >>>>> Can you prove that it's safe to ignore irrational solutions? > Here's a > > >>>>> (non-optimal) irrational solution for f(3), using 5 component > values: > > >>>>> > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 > > >>>>> 1/3 = 1/3 > > >>>>> > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2)
4)/24
> > >>>>> > > >>>>> Can we always do as well (or better) using only rational component > > >>>>> values? > > >>>>> I suspect the answer is yes. > > >>>>> > > >>>>> Note that the example above has the general form: > > >>>>> > > >>>>> 1/3 = a + (1/3 - a) > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) > > >>>>> 1/3 = 1/3 > > >>>>> > > >>>>> 1/2 = a + (1/2 - a) > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) > > >>>>> > > >>>>> This works for any value of "a" that doesn't produce zero or > negative > > >>>>> values. In particular, "a" can be given a rational value. Is it > the > > >>>>> case that any solution involving irrational values can be > decomposed > > >>>>> into something like this, which in turn can be converted into a > > >>>>> rational solution? > > >>>>> > > >>>>> Tom > > >>>>> > > >>>>> > > >>>>> Allan Wechsler writes: > > >>>>> > I was challenging myself to try to think of any finite > algorithm, > > >>>>> be it > > >>>>> > ever so expensive and cumbersome, that would settle the > question of > > >>>>> whether > > >>>>> > p pieces suffices for a given n. A useful lemma would be that > if it > > >>>>> can be > > >>>>> > done in p pieces, then it can be done with pieces whose > > >>>>> denominaters divide > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes > it > > >>>>> doesn't > > >>>>> > matter how weak this lemma is.) > > >>>>> > > > >>>>> > Then, we could say, "Iterate over all partitions of n! into p > > >>>>> parts, and > > >>>>> > for each such partition, check to see if it works, using the > > >>>>> partition as > > >>>>> > the numerators of fractions whose denominators are all n!." > This > > >>>>> would be > > >>>>> > heinously expensive but it would at least provide an upper > bound on > > >>>>> how > > >>>>> > much computational work we have to do. > > >>>>> > > > >>>>> > But I can't even prove the lemma. > > >>>>> > > > >>>>> > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I was wrong. The Russian discussion group gave the following [image: $F(7) \leq 15$]: [image: $(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$] [image: $(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$] [image: $(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/5$] [image: $(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$] On Tue, Dec 19, 2017 at 10:35 AM, Victor Miller <victorsmiller@gmail.com> wrote:
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html
I was thinking about the problem last night and came up with the following:
1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1) + (5-1) + (6-1) + (7-1) - 1 = 17 for f(7).
On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
For what it's worth, here's a naive, almost-certainly-suboptimal 18-part solution for n=7 corresponding to the bound of 18 given by https://oeis.org/A092249
1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7
Tom
Victor Miller writes: > Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a > tentative upper bound for the number of parts, and let it optimize it. I > suspect that the previously conjectured upper bound from A092249 isn't > right. Just to see if I could give it a much larger space to explore, I > gave it a tentative upper bound of 112 and after a few minutes it hasn't > even found any feasible solution! The only thing that it's proved so far > is that f(7) >= 12. > > Victor > > On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote: > > > Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution > > beats a simple union of divisions into equal parts! > > > > And your 11-part solution for f(6) also beats a simple union of divisions > > into equal parts! > > > > Have you tried f(7), or is that past what it can handle? > > > > Tom > > > > Victor Miller writes: > > > Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, > > 1/30, > > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 > > > > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < victorsmiller@gmail.com > > > > > > wrote: > > > > > > > I coded the model in cplex (I'll give the slightly corrected version > > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, > > > > 1/10, 3/20, 1/6, 1/5, 1/5 > > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, > > 1/6, > > > > 1/6 > > > > > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < > > victorsmiller@gmail.com> > > > > wrote: > > > > > > > >> Slight correction in my last post. Here is the correct version. > > > >> Tomorrow, when I get into work, I'll give the f(5) problem to cplex > > and > > > >> report back. > > > >> > > > >> Victor > > > >> > > > >> Solve the following problem -- given a positive integer n
1, and a > > > >> positive integer k decide if there are k reals x[1], ..., x[k] >= 0 > > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, > > > >> r=1,...,i in {0,1} > > > >> > > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for > > each i > > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > > > >> 3) x[j] in [0, 1/n] for j=1,..., k > > > >> > > > >> We can linearize (2) by using big-M: > > > >> > > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > > > >> > > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j]) > > > >> > > > >> There's lots of symmetries. We can (partially) break them by > > insisting > > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k > > are > > > >> lexicographically increasing. > > > >> > > > >> Also, as remarked before, we don't need to put any conditions for i, > > for > > > >> which a non-trivial multiple is <=n. > > > >> > > > >> > > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < > > victorsmiller@gmail.com> > > > >> wrote: > > > >> > > > >>> More specifically let x[1], ..., x[k] be non-negative variables <= > > 1, > > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value > > of 1 > > > >>> means that x[i] contributes to the j-th 1/i. We then have > > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or > > maybe <= > > > >>> 1 if you want to omit that piece). You might object that sum(j) > > y[i,j] * > > > >>> x[j] isn't linear. You can fix this by introducting new variables > > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this > > by > > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So > > giving > > > >>> this to a MIP solver is a finite algorithm for the problem. > > > >>> > > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < > > victorsmiller@gmail.com> > > > >>> wrote: > > > >>> > > > >>>> Here's a proof that there are optimal rational solutions: For a > > > >>>> putatitve solution to f(n) = k, you can write a mixed integer > > program which > > > >>>> will say whether or not there is such a solution. The only integer > > > >>>> variables are 0/1 variables which indicate whether "piece" i > > contributes to > > > >>>> a particular sum producing 1/n. There are only a finite number of > > settings > > > >>>> for these. Once you have done this the remainder is a polytope > > bounded by > > > >>>> half spaces with integer coefficients. So the vertices of the > > polytope > > > >>>> have rational coefficients. An optimal solution must be among > > these. > > > >>>> > > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < karzes@sonic.net> > > wrote: > > > >>>> > > > >>>>> Can you prove that it's safe to ignore irrational solutions? > > Here's a > > > >>>>> (non-optimal) irrational solution for f(3), using 5 component > > values: > > > >>>>> > > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 > > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 > > > >>>>> 1/3 = 1/3 > > > >>>>> > > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 > > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24 > > > >>>>> > > > >>>>> Can we always do as well (or better) using only rational component > > > >>>>> values? > > > >>>>> I suspect the answer is yes. > > > >>>>> > > > >>>>> Note that the example above has the general form: > > > >>>>> > > > >>>>> 1/3 = a + (1/3 - a) > > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) > > > >>>>> 1/3 = 1/3 > > > >>>>> > > > >>>>> 1/2 = a + (1/2 - a) > > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) > > > >>>>> > > > >>>>> This works for any value of "a" that doesn't produce zero or > > negative > > > >>>>> values. In particular, "a" can be given a rational value. Is it > > the > > > >>>>> case that any solution involving irrational values can be > > decomposed > > > >>>>> into something like this, which in turn can be converted into a > > > >>>>> rational solution? > > > >>>>> > > > >>>>> Tom > > > >>>>> > > > >>>>> > > > >>>>> Allan Wechsler writes: > > > >>>>> > I was challenging myself to try to think of any finite > > algorithm, > > > >>>>> be it > > > >>>>> > ever so expensive and cumbersome, that would settle the > > question of > > > >>>>> whether > > > >>>>> > p pieces suffices for a given n. A useful lemma would be that > > if it > > > >>>>> can be > > > >>>>> > done in p pieces, then it can be done with pieces whose > > > >>>>> denominaters divide > > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my purposes > > it > > > >>>>> doesn't > > > >>>>> > matter how weak this lemma is.) > > > >>>>> > > > > >>>>> > Then, we could say, "Iterate over all partitions of n! into p > > > >>>>> parts, and > > > >>>>> > for each such partition, check to see if it works, using the > > > >>>>> partition as > > > >>>>> > the numerators of fractions whose denominators are all n!." > > This > > > >>>>> would be > > > >>>>> > heinously expensive but it would at least provide an upper > > bound on > > > >>>>> how > > > >>>>> > much computational work we have to do. > > > >>>>> > > > > >>>>> > But I can't even prove the lemma. > > > >>>>> > > > > >>>>> > > > > _______________________________________________ > > math-fun mailing list > > math-fun@mailman.xmission.com > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-f un > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
And for f(8) <= 17 (also from the Russian discussion): [image: $36,35,57,48,105,50,62,15,63,55,42,17,43,34,58,47,73.$] [image: $36+35+34=50+55=15+17+73=57+48=58+47=105=63+42=62+43,$] [image: $62+58=105+15=48+55+17=36+50+34=47+73=35+42+43=57+63,$] [image: $36+57+47=50+17+73=35+105=55+42+43=48+34+58=62+15+63,$] [image: $105+63=57+62+15+34=36+35+55+42=48+47+73=50+17+43+58.$] On Tue, Dec 19, 2017 at 10:38 AM, Victor Miller <victorsmiller@gmail.com> wrote:
I was wrong. The Russian discussion group gave the following
[image: $F(7) \leq 15$]: [image: $(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$] [image: $(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$] [image: $(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/5$] [image: $(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$]
On Tue, Dec 19, 2017 at 10:35 AM, Victor Miller <victorsmiller@gmail.com> wrote:
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html
I was thinking about the problem last night and came up with the following:
1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1) + (5-1) + (6-1) + (7-1) - 1 = 17 for f(7).
On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
We can extend Victor's 11 piece solution for n=6 to a 17-piece solution for n=7.
There's an inequality: F(n) <= F(n-1)+n-1 Arrange all the pieces along the line [0,1] in any order. Make n-1 cuts at k/n for 0<k<n.
I'd like to say F(n) <= F(n-1) + phi(n), but I can only get
F(n) <= F(n-1) + (n - maximum-proper-divisor(n))
I'm allowing 1 as a proper divisor, but not n. To get the inequality: let m = max-prop-div(n). Arrange the pieces in the n-1 solution into size 1/m groups. Place these along the [0,1] line. Then some of the cuts for k/n will overlap all the cuts for the 1/m grouping.
We can say F(n) <= sum(phi(n)). In this case, just make all the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just the Farey series for n, excluding 1/1.) With no rearrangement of the pieces, when we get around to making the cuts for k/n, cuts will already exist for all proper divisors d|n. The sum should be roughly n(n+1)/2 * 6/pi^2. In this solution, the smallest piece is 1/n(n-1). The common denominator for all the pieces is indeed LCM(1...n), very roughly e^n.
Rich
-----------
Quoting Tom Karzes <karzes@sonic.net>:
> For what it's worth, here's a naive, almost-certainly-suboptimal > 18-part solution for n=7 corresponding to the bound of 18 given by > https://oeis.org/A092249 > > 1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, > 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7 > > Tom > > Victor Miller writes: > > Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a > > tentative upper bound for the number of parts, and let it optimize > it. I > > suspect that the previously conjectured upper bound from A092249 isn't > > right. Just to see if I could give it a much larger space to explore, > I > > gave it a tentative upper bound of 112 and after a few minutes it > hasn't > > even found any feasible solution! The only thing that it's proved so > far > > is that f(7) >= 12. > > > > Victor > > > > On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net> wrote: > > > > > Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution > > > beats a simple union of divisions into equal parts! > > > > > > And your 11-part solution for f(6) also beats a simple union of > divisions > > > into equal parts! > > > > > > Have you tried f(7), or is that past what it can handle? > > > > > > Tom > > > > > > Victor Miller writes: > > > > Whoops, in f(6) threre should have been 2 parts of size 7/60: > 1/30, > > > 1/30, > > > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 > > > > > > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < > victorsmiller@gmail.com > > > > > > > > wrote: > > > > > > > > > I coded the model in cplex (I'll give the slightly corrected > version > > > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, > 1/20, 1/12, > > > > > 1/10, 3/20, 1/6, 1/5, 1/5 > > > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, > 7/60, > > > 1/6, > > > > > 1/6 > > > > > > > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < > > > victorsmiller@gmail.com> > > > > > wrote: > > > > > > > > > >> Slight correction in my last post. Here is the correct > version. > > > > >> Tomorrow, when I get into work, I'll give the f(5) problem to > cplex > > > and > > > > >> report back. > > > > >> > > > > >> Victor > > > > >> > > > > >> Solve the following problem -- given a positive integer n
> 1, and a > > > > >> positive integer k decide if there are k reals x[1], ..., > x[k] >= 0 > > > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, > ..., k, > > > > >> r=1,...,i in {0,1} > > > > >> > > > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 > for > > > each i > > > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > > > > >> 3) x[j] in [0, 1/n] for j=1,..., k > > > > >> > > > > >> We can linearize (2) by using big-M: > > > > >> > > > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > > > > >> > > > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * > (1-y[i,r,j]) > > > > >> > > > > >> There's lots of symmetries. We can (partially) break them by > > > insisting > > > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), > j=1,...,k > > > are > > > > >> lexicographically increasing. > > > > >> > > > > >> Also, as remarked before, we don't need to put any conditions > for i, > > > for > > > > >> which a non-trivial multiple is <=n. > > > > >> > > > > >> > > > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < > > > victorsmiller@gmail.com> > > > > >> wrote: > > > > >> > > > > >>> More specifically let x[1], ..., x[k] be non-negative > variables <= > > > 1, > > > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose > value > > > of 1 > > > > >>> means that x[i] contributes to the j-th 1/i. We then have > > > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 > (or > > > maybe <= > > > > >>> 1 if you want to omit that piece). You might object that > sum(j) > > > y[i,j] * > > > > >>> x[j] isn't linear. You can fix this by introducting new > variables > > > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can > enforce this > > > by > > > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). > So > > > giving > > > > >>> this to a MIP solver is a finite algorithm for the problem. > > > > >>> > > > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < > > > victorsmiller@gmail.com> > > > > >>> wrote: > > > > >>> > > > > >>>> Here's a proof that there are optimal rational solutions: > For a > > > > >>>> putatitve solution to f(n) = k, you can write a mixed integer > > > program which > > > > >>>> will say whether or not there is such a solution. The only > integer > > > > >>>> variables are 0/1 variables which indicate whether "piece" i > > > contributes to > > > > >>>> a particular sum producing 1/n. There are only a finite > number of > > > settings > > > > >>>> for these. Once you have done this the remainder is a > polytope > > > bounded by > > > > >>>> half spaces with integer coefficients. So the vertices of > the > > > polytope > > > > >>>> have rational coefficients. An optimal solution must be > among > > > these. > > > > >>>> > > > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < > karzes@sonic.net> > > > wrote: > > > > >>>> > > > > >>>>> Can you prove that it's safe to ignore irrational solutions? > > > Here's a > > > > >>>>> (non-optimal) irrational solution for f(3), using 5 > component > > > values: > > > > >>>>> > > > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 > > > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 > > > > >>>>> 1/3 = 1/3 > > > > >>>>> > > > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 > > > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - > 4)/24 > > > > >>>>> > > > > >>>>> Can we always do as well (or better) using only rational > component > > > > >>>>> values? > > > > >>>>> I suspect the answer is yes. > > > > >>>>> > > > > >>>>> Note that the example above has the general form: > > > > >>>>> > > > > >>>>> 1/3 = a + (1/3 - a) > > > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) > > > > >>>>> 1/3 = 1/3 > > > > >>>>> > > > > >>>>> 1/2 = a + (1/2 - a) > > > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) > > > > >>>>> > > > > >>>>> This works for any value of "a" that doesn't produce zero or > > > negative > > > > >>>>> values. In particular, "a" can be given a rational > value. Is it > > > the > > > > >>>>> case that any solution involving irrational values can be > > > decomposed > > > > >>>>> into something like this, which in turn can be converted > into a > > > > >>>>> rational solution? > > > > >>>>> > > > > >>>>> Tom > > > > >>>>> > > > > >>>>> > > > > >>>>> Allan Wechsler writes: > > > > >>>>> > I was challenging myself to try to think of any finite > > > algorithm, > > > > >>>>> be it > > > > >>>>> > ever so expensive and cumbersome, that would settle the > > > question of > > > > >>>>> whether > > > > >>>>> > p pieces suffices for a given n. A useful lemma would > be that > > > if it > > > > >>>>> can be > > > > >>>>> > done in p pieces, then it can be done with pieces whose > > > > >>>>> denominaters divide > > > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my > purposes > > > it > > > > >>>>> doesn't > > > > >>>>> > matter how weak this lemma is.) > > > > >>>>> > > > > > >>>>> > Then, we could say, "Iterate over all partitions of n! > into p > > > > >>>>> parts, and > > > > >>>>> > for each such partition, check to see if it works, using > the > > > > >>>>> partition as > > > > >>>>> > the numerators of fractions whose denominators are all > n!." > > > This > > > > >>>>> would be > > > > >>>>> > heinously expensive but it would at least provide an > upper > > > bound on > > > > >>>>> how > > > > >>>>> > much computational work we have to do. > > > > >>>>> > > > > > >>>>> > But I can't even prove the lemma. > > > > >>>>> > > > > > >>>>> > > > > > > _______________________________________________ > > > math-fun mailing list > > > math-fun@mailman.xmission.com > > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-f un > > > > > _______________________________________________ > > math-fun mailing list > > math-fun@mailman.xmission.com > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > -- > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The blog is many screens long, but the same poster (he didn't say how he found it) shows that f(8) <= 16: [image: $17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88.$] [image: $23+82=80+25=88+17=32+73=52+53=38+67=68+37=47+58,$] [image: $23+80+17=25+37+58=88+32=52+68=73+47=82+38=53+67,$] [image: $82+58=88+52=25+68+47=23+80+37=73+67=17+32+53+38,$] [image: $53+68+47=23+82+25+38=80+88=73+37+58=17+32+52+67.$] On Tue, Dec 19, 2017 at 10:41 AM, Victor Miller <victorsmiller@gmail.com> wrote:
And for f(8) <= 17 (also from the Russian discussion):
[image: $36,35,57,48,105,50,62,15,63,55,42,17,43,34,58,47,73.$]
[image: $36+35+34=50+55=15+17+73=57+48=58+47=105=63+42=62+43,$] [image: $62+58=105+15=48+55+17=36+50+34=47+73=35+42+43=57+63,$] [image: $36+57+47=50+17+73=35+105=55+42+43=48+34+58=62+15+63,$] [image: $105+63=57+62+15+34=36+35+55+42=48+47+73=50+17+43+58.$]
On Tue, Dec 19, 2017 at 10:38 AM, Victor Miller <victorsmiller@gmail.com> wrote:
I was wrong. The Russian discussion group gave the following
[image: $F(7) \leq 15$]: [image: $(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$] [image: $(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$] [image: $(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/5$] [image: $(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$]
On Tue, Dec 19, 2017 at 10:35 AM, Victor Miller <victorsmiller@gmail.com> wrote:
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html
I was thinking about the problem last night and came up with the following:
1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1) + (5-1) + (6-1) + (7-1) - 1 = 17 for f(7).
On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
> We can extend Victor's 11 piece solution for n=6 to a 17-piece solution > for n=7. > > There's an inequality: F(n) <= F(n-1)+n-1 > Arrange all the pieces along the line [0,1] in any order. > Make n-1 cuts at k/n for 0<k<n. > > I'd like to say F(n) <= F(n-1) + phi(n), but I can only get > > F(n) <= F(n-1) + (n - maximum-proper-divisor(n)) > > I'm allowing 1 as a proper divisor, but not n. > To get the inequality: let m = max-prop-div(n). > Arrange the pieces in the n-1 solution into size 1/m groups. > Place these along the [0,1] line. > Then some of the cuts for k/n will overlap all the cuts for the 1/m > grouping. > > We can say F(n) <= sum(phi(n)). In this case, just make all > the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just > the Farey series for n, excluding 1/1.) With no rearrangement > of the pieces, when we get around to making the cuts for k/n, > cuts will already exist for all proper divisors d|n. > The sum should be roughly n(n+1)/2 * 6/pi^2. > In this solution, the smallest piece is 1/n(n-1). > The common denominator for all the pieces is indeed LCM(1...n), > very roughly e^n. > > Rich > > ----------- > > Quoting Tom Karzes <karzes@sonic.net>: > >> For what it's worth, here's a naive, almost-certainly-suboptimal >> 18-part solution for n=7 corresponding to the bound of 18 given by >> https://oeis.org/A092249 >> >> 1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, >> 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7 >> >> Tom >> >> Victor Miller writes: >> > Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a >> > tentative upper bound for the number of parts, and let it optimize >> it. I >> > suspect that the previously conjectured upper bound from A092249 isn't >> > right. Just to see if I could give it a much larger space to explore, >> I >> > gave it a tentative upper bound of 112 and after a few minutes it >> hasn't >> > even found any feasible solution! The only thing that it's proved so >> far >> > is that f(7) >= 12. >> > >> > Victor >> > >> > On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net
wrote: >> > >> > > Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution >> > > beats a simple union of divisions into equal parts! >> > > >> > > And your 11-part solution for f(6) also beats a simple union of >> divisions >> > > into equal parts! >> > > >> > > Have you tried f(7), or is that past what it can handle? >> > > >> > > Tom >> > > >> > > Victor Miller writes: >> > > > Whoops, in f(6) threre should have been 2 parts of size 7/60: >> 1/30, >> > > 1/30, >> > > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 >> > > > >> > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < >> victorsmiller@gmail.com >> > > > >> > > > wrote: >> > > > >> > > > > I coded the model in cplex (I'll give the slightly corrected >> version >> > > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, >> 1/20, 1/12, >> > > > > 1/10, 3/20, 1/6, 1/5, 1/5 >> > > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, >> 7/60, >> > > 1/6, >> > > > > 1/6 >> > > > > >> > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > > wrote: >> > > > > >> > > > >> Slight correction in my last post. Here is the correct >> version. >> > > > >> Tomorrow, when I get into work, I'll give the f(5) problem to >> cplex >> > > and >> > > > >> report back. >> > > > >> >> > > > >> Victor >> > > > >> >> > > > >> Solve the following problem -- given a positive integer n
>> 1, and a >> > > > >> positive integer k decide if there are k reals x[1], ..., >> x[k] >= 0 >> > > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, >> ..., k, >> > > > >> r=1,...,i in {0,1} >> > > > >> >> > > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 >> for >> > > each i >> > > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i >> > > > >> 3) x[j] in [0, 1/n] for j=1,..., k >> > > > >> >> > > > >> We can linearize (2) by using big-M: >> > > > >> >> > > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] >> > > > >> >> > > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * >> (1-y[i,r,j]) >> > > > >> >> > > > >> There's lots of symmetries. We can (partially) break them by >> > > insisting >> > > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), >> j=1,...,k >> > > are >> > > > >> lexicographically increasing. >> > > > >> >> > > > >> Also, as remarked before, we don't need to put any conditions >> for i, >> > > for >> > > > >> which a non-trivial multiple is <=n. >> > > > >> >> > > > >> >> > > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > >> wrote: >> > > > >> >> > > > >>> More specifically let x[1], ..., x[k] be non-negative >> variables <= >> > > 1, >> > > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose >> value >> > > of 1 >> > > > >>> means that x[i] contributes to the j-th 1/i. We then have >> > > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 >> (or >> > > maybe <= >> > > > >>> 1 if you want to omit that piece). You might object that >> sum(j) >> > > y[i,j] * >> > > > >>> x[j] isn't linear. You can fix this by introducting new >> variables >> > > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can >> enforce this >> > > by >> > > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). >> So >> > > giving >> > > > >>> this to a MIP solver is a finite algorithm for the problem. >> > > > >>> >> > > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > >>> wrote: >> > > > >>> >> > > > >>>> Here's a proof that there are optimal rational solutions: >> For a >> > > > >>>> putatitve solution to f(n) = k, you can write a mixed integer >> > > program which >> > > > >>>> will say whether or not there is such a solution. The only >> integer >> > > > >>>> variables are 0/1 variables which indicate whether "piece" i >> > > contributes to >> > > > >>>> a particular sum producing 1/n. There are only a finite >> number of >> > > settings >> > > > >>>> for these. Once you have done this the remainder is a >> polytope >> > > bounded by >> > > > >>>> half spaces with integer coefficients. So the vertices of >> the >> > > polytope >> > > > >>>> have rational coefficients. An optimal solution must be >> among >> > > these. >> > > > >>>> >> > > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < >> karzes@sonic.net> >> > > wrote: >> > > > >>>> >> > > > >>>>> Can you prove that it's safe to ignore irrational solutions? >> > > Here's a >> > > > >>>>> (non-optimal) irrational solution for f(3), using 5 >> component >> > > values: >> > > > >>>>> >> > > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >> > > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >> > > > >>>>> 1/3 = 1/3 >> > > > >>>>> >> > > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >> > > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - >> 4)/24 >> > > > >>>>> >> > > > >>>>> Can we always do as well (or better) using only rational >> component >> > > > >>>>> values? >> > > > >>>>> I suspect the answer is yes. >> > > > >>>>> >> > > > >>>>> Note that the example above has the general form: >> > > > >>>>> >> > > > >>>>> 1/3 = a + (1/3 - a) >> > > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) >> > > > >>>>> 1/3 = 1/3 >> > > > >>>>> >> > > > >>>>> 1/2 = a + (1/2 - a) >> > > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >> > > > >>>>> >> > > > >>>>> This works for any value of "a" that doesn't produce zero or >> > > negative >> > > > >>>>> values. In particular, "a" can be given a rational >> value. Is it >> > > the >> > > > >>>>> case that any solution involving irrational values can be >> > > decomposed >> > > > >>>>> into something like this, which in turn can be converted >> into a >> > > > >>>>> rational solution? >> > > > >>>>> >> > > > >>>>> Tom >> > > > >>>>> >> > > > >>>>> >> > > > >>>>> Allan Wechsler writes: >> > > > >>>>> > I was challenging myself to try to think of any finite >> > > algorithm, >> > > > >>>>> be it >> > > > >>>>> > ever so expensive and cumbersome, that would settle the >> > > question of >> > > > >>>>> whether >> > > > >>>>> > p pieces suffices for a given n. A useful lemma would >> be that >> > > if it >> > > > >>>>> can be >> > > > >>>>> > done in p pieces, then it can be done with pieces whose >> > > > >>>>> denominaters divide >> > > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my >> purposes >> > > it >> > > > >>>>> doesn't >> > > > >>>>> > matter how weak this lemma is.) >> > > > >>>>> > >> > > > >>>>> > Then, we could say, "Iterate over all partitions of n! >> into p >> > > > >>>>> parts, and >> > > > >>>>> > for each such partition, check to see if it works, using >> the >> > > > >>>>> partition as >> > > > >>>>> > the numerators of fractions whose denominators are all >> n!." >> > > This >> > > > >>>>> would be >> > > > >>>>> > heinously expensive but it would at least provide an >> upper >> > > bound on >> > > > >>>>> how >> > > > >>>>> > much computational work we have to do. >> > > > >>>>> > >> > > > >>>>> > But I can't even prove the lemma. >> > > > >>>>> > >> > > > >>>>> >> > > >> > > _______________________________________________ >> > > math-fun mailing list >> > > math-fun@mailman.xmission.com >> > > https://mailman.xmission.com/c gi-bin/mailman/listinfo/math-fun >> > > >> > _______________________________________________ >> > math-fun mailing list >> > math-fun@mailman.xmission.com >> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-f un >> > >> >> -- >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> >> > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK). They seem like a rather jolly, collegial crew over there. They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here. On Tue, Dec 19, 2017 at 10:41 AM, Victor Miller <victorsmiller@gmail.com> wrote:
And for f(8) <= 17 (also from the Russian discussion):
[image: $36,35,57,48,105,50,62,15,63,55,42,17,43,34,58,47,73.$]
[image: $36+35+34=50+55=15+17+73=57+48=58+47=105=63+42=62+43,$] [image: $62+58=105+15=48+55+17=36+50+34=47+73=35+42+43=57+63,$] [image: $36+57+47=50+17+73=35+105=55+42+43=48+34+58=62+15+63,$] [image: $105+63=57+62+15+34=36+35+55+42=48+47+73=50+17+43+58.$]
On Tue, Dec 19, 2017 at 10:38 AM, Victor Miller <victorsmiller@gmail.com> wrote:
I was wrong. The Russian discussion group gave the following
[image: $F(7) \leq 15$]: [image: $(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$] [image: $(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$] [image: $(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/ 5$] [image: $(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$]
On Tue, Dec 19, 2017 at 10:35 AM, Victor Miller <victorsmiller@gmail.com
wrote:
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html
I was thinking about the problem last night and came up with the following:
1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1) + (5-1) + (6-1) + (7-1) - 1 = 17 for f(7).
On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
> We can extend Victor's 11 piece solution for n=6 to a 17-piece solution > for n=7. > > There's an inequality: F(n) <= F(n-1)+n-1 > Arrange all the pieces along the line [0,1] in any order. > Make n-1 cuts at k/n for 0<k<n. > > I'd like to say F(n) <= F(n-1) + phi(n), but I can only get > > F(n) <= F(n-1) + (n - maximum-proper-divisor(n)) > > I'm allowing 1 as a proper divisor, but not n. > To get the inequality: let m = max-prop-div(n). > Arrange the pieces in the n-1 solution into size 1/m groups. > Place these along the [0,1] line. > Then some of the cuts for k/n will overlap all the cuts for the 1/m > grouping. > > We can say F(n) <= sum(phi(n)). In this case, just make all > the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just > the Farey series for n, excluding 1/1.) With no rearrangement > of the pieces, when we get around to making the cuts for k/n, > cuts will already exist for all proper divisors d|n. > The sum should be roughly n(n+1)/2 * 6/pi^2. > In this solution, the smallest piece is 1/n(n-1). > The common denominator for all the pieces is indeed LCM(1...n), > very roughly e^n. > > Rich > > ----------- > > Quoting Tom Karzes <karzes@sonic.net>: > >> For what it's worth, here's a naive, almost-certainly-suboptimal >> 18-part solution for n=7 corresponding to the bound of 18 given by >> https://oeis.org/A092249 >> >> 1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, >> 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7 >> >> Tom >> >> Victor Miller writes: >> > Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a >> > tentative upper bound for the number of parts, and let it optimize >> it. I >> > suspect that the previously conjectured upper bound from A092249 isn't >> > right. Just to see if I could give it a much larger space to explore, >> I >> > gave it a tentative upper bound of 112 and after a few minutes it >> hasn't >> > even found any feasible solution! The only thing that it's proved so >> far >> > is that f(7) >= 12. >> > >> > Victor >> > >> > On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes < karzes@sonic.net> wrote: >> > >> > > Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution >> > > beats a simple union of divisions into equal parts! >> > > >> > > And your 11-part solution for f(6) also beats a simple union of >> divisions >> > > into equal parts! >> > > >> > > Have you tried f(7), or is that past what it can handle? >> > > >> > > Tom >> > > >> > > Victor Miller writes: >> > > > Whoops, in f(6) threre should have been 2 parts of size 7/60: >> 1/30, >> > > 1/30, >> > > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 >> > > > >> > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < >> victorsmiller@gmail.com >> > > > >> > > > wrote: >> > > > >> > > > > I coded the model in cplex (I'll give the slightly corrected >> version >> > > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, >> 1/20, 1/12, >> > > > > 1/10, 3/20, 1/6, 1/5, 1/5 >> > > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, >> 7/60, >> > > 1/6, >> > > > > 1/6 >> > > > > >> > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > > wrote: >> > > > > >> > > > >> Slight correction in my last post. Here is the correct >> version. >> > > > >> Tomorrow, when I get into work, I'll give the f(5) problem to >> cplex >> > > and >> > > > >> report back. >> > > > >> >> > > > >> Victor >> > > > >> >> > > > >> Solve the following problem -- given a positive integer n
>> 1, and a >> > > > >> positive integer k decide if there are k reals x[1], ..., >> x[k] >= 0 >> > > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, >> ..., k, >> > > > >> r=1,...,i in {0,1} >> > > > >> >> > > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 >> for >> > > each i >> > > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i >> > > > >> 3) x[j] in [0, 1/n] for j=1,..., k >> > > > >> >> > > > >> We can linearize (2) by using big-M: >> > > > >> >> > > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] >> > > > >> >> > > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * >> (1-y[i,r,j]) >> > > > >> >> > > > >> There's lots of symmetries. We can (partially) break them by >> > > insisting >> > > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), >> j=1,...,k >> > > are >> > > > >> lexicographically increasing. >> > > > >> >> > > > >> Also, as remarked before, we don't need to put any conditions >> for i, >> > > for >> > > > >> which a non-trivial multiple is <=n. >> > > > >> >> > > > >> >> > > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > >> wrote: >> > > > >> >> > > > >>> More specifically let x[1], ..., x[k] be non-negative >> variables <= >> > > 1, >> > > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose >> value >> > > of 1 >> > > > >>> means that x[i] contributes to the j-th 1/i. We then have >> > > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 >> (or >> > > maybe <= >> > > > >>> 1 if you want to omit that piece). You might object that >> sum(j) >> > > y[i,j] * >> > > > >>> x[j] isn't linear. You can fix this by introducting new >> variables >> > > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can >> enforce this >> > > by >> > > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). >> So >> > > giving >> > > > >>> this to a MIP solver is a finite algorithm for the problem. >> > > > >>> >> > > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > >>> wrote: >> > > > >>> >> > > > >>>> Here's a proof that there are optimal rational solutions: >> For a >> > > > >>>> putatitve solution to f(n) = k, you can write a mixed integer >> > > program which >> > > > >>>> will say whether or not there is such a solution. The only >> integer >> > > > >>>> variables are 0/1 variables which indicate whether "piece" i >> > > contributes to >> > > > >>>> a particular sum producing 1/n. There are only a finite >> number of >> > > settings >> > > > >>>> for these. Once you have done this the remainder is a >> polytope >> > > bounded by >> > > > >>>> half spaces with integer coefficients. So the vertices of >> the >> > > polytope >> > > > >>>> have rational coefficients. An optimal solution must be >> among >> > > these. >> > > > >>>> >> > > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < >> karzes@sonic.net> >> > > wrote: >> > > > >>>> >> > > > >>>>> Can you prove that it's safe to ignore irrational solutions? >> > > Here's a >> > > > >>>>> (non-optimal) irrational solution for f(3), using 5 >> component >> > > values: >> > > > >>>>> >> > > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >> > > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >> > > > >>>>> 1/3 = 1/3 >> > > > >>>>> >> > > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >> > > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - >> 4)/24 >> > > > >>>>> >> > > > >>>>> Can we always do as well (or better) using only rational >> component >> > > > >>>>> values? >> > > > >>>>> I suspect the answer is yes. >> > > > >>>>> >> > > > >>>>> Note that the example above has the general form: >> > > > >>>>> >> > > > >>>>> 1/3 = a + (1/3 - a) >> > > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) >> > > > >>>>> 1/3 = 1/3 >> > > > >>>>> >> > > > >>>>> 1/2 = a + (1/2 - a) >> > > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >> > > > >>>>> >> > > > >>>>> This works for any value of "a" that doesn't produce zero or >> > > negative >> > > > >>>>> values. In particular, "a" can be given a rational >> value. Is it >> > > the >> > > > >>>>> case that any solution involving irrational values can be >> > > decomposed >> > > > >>>>> into something like this, which in turn can be converted >> into a >> > > > >>>>> rational solution? >> > > > >>>>> >> > > > >>>>> Tom >> > > > >>>>> >> > > > >>>>> >> > > > >>>>> Allan Wechsler writes: >> > > > >>>>> > I was challenging myself to try to think of any finite >> > > algorithm, >> > > > >>>>> be it >> > > > >>>>> > ever so expensive and cumbersome, that would settle the >> > > question of >> > > > >>>>> whether >> > > > >>>>> > p pieces suffices for a given n. A useful lemma would >> be that >> > > if it >> > > > >>>>> can be >> > > > >>>>> > done in p pieces, then it can be done with pieces whose >> > > > >>>>> denominaters divide >> > > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my >> purposes >> > > it >> > > > >>>>> doesn't >> > > > >>>>> > matter how weak this lemma is.) >> > > > >>>>> > >> > > > >>>>> > Then, we could say, "Iterate over all partitions of n! >> into p >> > > > >>>>> parts, and >> > > > >>>>> > for each such partition, check to see if it works, using >> the >> > > > >>>>> partition as >> > > > >>>>> > the numerators of fractions whose denominators are all >> n!." >> > > This >> > > > >>>>> would be >> > > > >>>>> > heinously expensive but it would at least provide an >> upper >> > > bound on >> > > > >>>>> how >> > > > >>>>> > much computational work we have to do. >> > > > >>>>> > >> > > > >>>>> > But I can't even prove the lemma. >> > > > >>>>> > >> > > > >>>>> >> > > >> > > _______________________________________________ >> > > math-fun mailing list >> > > math-fun@mailman.xmission.com >> > > https://mailman.xmission.com/ cgi-bin/mailman/listinfo/math-f un >> > > >> > _______________________________________________ >> > math-fun mailing list >> > math-fun@mailman.xmission.com >> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math- fun >> > >> >> -- >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> >> > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Allan, Thanks. Why didn't I see that? In any case it's not completely clear to me what the algorithms were to find good solutions for f(n), but here's one: Do this inductively -- collect a whole bunch of good solutions for f(n), and try to extend them to f(n+1), by a sort of bin packing procedure: have n+1 bin of capacity 1/(n+1) and for each solution for f(n) try to place the pieces in the bins so that you need to make the minimal number of cuts to make them fit exactly. It's not clear, a priori, which of the minimal solutions to f(n) will extend to f(n+1), you need to collect a bunch of them. On Tue, Dec 19, 2017 at 10:47 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK).
They seem like a rather jolly, collegial crew over there.
They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here.
On Tue, Dec 19, 2017 at 10:41 AM, Victor Miller <victorsmiller@gmail.com> wrote:
And for f(8) <= 17 (also from the Russian discussion):
[image: $36,35,57,48,105,50,62,15,63,55,42,17,43,34,58,47,73.$]
[image: $36+35+34=50+55=15+17+73=57+48=58+47=105=63+42=62+43,$] [image: $62+58=105+15=48+55+17=36+50+34=47+73=35+42+43=57+63,$] [image: $36+57+47=50+17+73=35+105=55+42+43=48+34+58=62+15+63,$] [image: $105+63=57+62+15+34=36+35+55+42=48+47+73=50+17+43+58.$]
On Tue, Dec 19, 2017 at 10:38 AM, Victor Miller <victorsmiller@gmail.com
wrote:
I was wrong. The Russian discussion group gave the following
[image: $F(7) \leq 15$]: [image: $(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$] [image: $(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$] [image: $(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/ 5$] [image: $(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$]
On Tue, Dec 19, 2017 at 10:35 AM, Victor Miller < victorsmiller@gmail.com
wrote:
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html
I was thinking about the problem last night and came up with the following:
1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1)
(5-1) + (6-1) + (7-1) - 1 = 17 for f(7).
On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
> OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that > none of them are "the answer"; if any one of them is in fact the f(n) we > have been discussing, it will take nontrivial mathematics to prove it. > > On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote: > > > We can extend Victor's 11 piece solution for n=6 to a 17-piece solution > > for n=7. > > > > There's an inequality: F(n) <= F(n-1)+n-1 > > Arrange all the pieces along the line [0,1] in any order. > > Make n-1 cuts at k/n for 0<k<n. > > > > I'd like to say F(n) <= F(n-1) + phi(n), but I can only get > > > > F(n) <= F(n-1) + (n - maximum-proper-divisor(n)) > > > > I'm allowing 1 as a proper divisor, but not n. > > To get the inequality: let m = max-prop-div(n). > > Arrange the pieces in the n-1 solution into size 1/m groups. > > Place these along the [0,1] line. > > Then some of the cuts for k/n will overlap all the cuts for the 1/m > > grouping. > > > > We can say F(n) <= sum(phi(n)). In this case, just make all > > the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just > > the Farey series for n, excluding 1/1.) With no rearrangement > > of the pieces, when we get around to making the cuts for k/n, > > cuts will already exist for all proper divisors d|n. > > The sum should be roughly n(n+1)/2 * 6/pi^2. > > In this solution, the smallest piece is 1/n(n-1). > > The common denominator for all the pieces is indeed LCM(1...n), > > very roughly e^n. > > > > Rich > > > > ----------- > > > > Quoting Tom Karzes <karzes@sonic.net>: > > > >> For what it's worth, here's a naive, almost-certainly-suboptimal > >> 18-part solution for n=7 corresponding to the bound of 18 given by > >> https://oeis.org/A092249 > >> > >> 1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, > >> 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7 > >> > >> Tom > >> > >> Victor Miller writes: > >> > Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a > >> > tentative upper bound for the number of parts, and let it optimize > >> it. I > >> > suspect that the previously conjectured upper bound from A092249 > isn't > >> > right. Just to see if I could give it a much larger space to > explore, > >> I > >> > gave it a tentative upper bound of 112 and after a few minutes it > >> hasn't > >> > even found any feasible solution! The only thing that it's proved so > >> far > >> > is that f(7) >= 12. > >> > > >> > Victor > >> > > >> > On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes < karzes@sonic.net> > wrote: > >> > > >> > > Wow, nice job! I was expecting f(5) to be 10. Your 9-part > solution > >> > > beats a simple union of divisions into equal parts! > >> > > > >> > > And your 11-part solution for f(6) also beats a simple union of > >> divisions > >> > > into equal parts! > >> > > > >> > > Have you tried f(7), or is that past what it can handle? > >> > > > >> > > Tom > >> > > > >> > > Victor Miller writes: > >> > > > Whoops, in f(6) threre should have been 2 parts of size 7/60: > >> 1/30, > >> > > 1/30, > >> > > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 > >> > > > > >> > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < > >> victorsmiller@gmail.com > >> > > > > >> > > > wrote: > >> > > > > >> > > > > I coded the model in cplex (I'll give the slightly corrected > >> version > >> > > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, > >> 1/20, 1/12, > >> > > > > 1/10, 3/20, 1/6, 1/5, 1/5 > >> > > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, > 1/10, > >> 7/60, > >> > > 1/6, > >> > > > > 1/6 > >> > > > > > >> > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < > >> > > victorsmiller@gmail.com> > >> > > > > wrote: > >> > > > > > >> > > > >> Slight correction in my last post. Here is the correct > >> version. > >> > > > >> Tomorrow, when I get into work, I'll give the f(5) problem > to > >> cplex > >> > > and > >> > > > >> report back. > >> > > > >> > >> > > > >> Victor > >> > > > >> > >> > > > >> Solve the following problem -- given a positive integer n > > >> 1, and a > >> > > > >> positive integer k decide if there are k reals x[1], ..., > >> x[k] >= 0 > >> > > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, > >> ..., k, > >> > > > >> r=1,...,i in {0,1} > >> > > > >> > >> > > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 > >> for > >> > > each i > >> > > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i > >> > > > >> 3) x[j] in [0, 1/n] for j=1,..., k > >> > > > >> > >> > > > >> We can linearize (2) by using big-M: > >> > > > >> > >> > > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] > >> > > > >> > >> > > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * > >> (1-y[i,r,j]) > >> > > > >> > >> > > > >> There's lots of symmetries. We can (partially) break them by > >> > > insisting > >> > > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), > >> j=1,...,k > >> > > are > >> > > > >> lexicographically increasing. > >> > > > >> > >> > > > >> Also, as remarked before, we don't need to put any > conditions > >> for i, > >> > > for > >> > > > >> which a non-trivial multiple is <=n. > >> > > > >> > >> > > > >> > >> > > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < > >> > > victorsmiller@gmail.com> > >> > > > >> wrote: > >> > > > >> > >> > > > >>> More specifically let x[1], ..., x[k] be non-negative > >> variables <= > >> > > 1, > >> > > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable > whose > >> value > >> > > of 1 > >> > > > >>> means that x[i] contributes to the j-th 1/i. We then have > >> > > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 > >> (or > >> > > maybe <= > >> > > > >>> 1 if you want to omit that piece). You might object that > >> sum(j) > >> > > y[i,j] * > >> > > > >>> x[j] isn't linear. You can fix this by introducting new > >> variables > >> > > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can > >> enforce this > >> > > by > >> > > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). > >> So > >> > > giving > >> > > > >>> this to a MIP solver is a finite algorithm for the problem. > >> > > > >>> > >> > > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < > >> > > victorsmiller@gmail.com> > >> > > > >>> wrote: > >> > > > >>> > >> > > > >>>> Here's a proof that there are optimal rational solutions: > >> For a > >> > > > >>>> putatitve solution to f(n) = k, you can write a mixed > integer > >> > > program which > >> > > > >>>> will say whether or not there is such a solution. The > only > >> integer > >> > > > >>>> variables are 0/1 variables which indicate whether "piece" > i > >> > > contributes to > >> > > > >>>> a particular sum producing 1/n. There are only a finite > >> number of > >> > > settings > >> > > > >>>> for these. Once you have done this the remainder is a > >> polytope > >> > > bounded by > >> > > > >>>> half spaces with integer coefficients. So the vertices of > >> the > >> > > polytope > >> > > > >>>> have rational coefficients. An optimal solution must be > >> among > >> > > these. > >> > > > >>>> > >> > > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < > >> karzes@sonic.net> > >> > > wrote: > >> > > > >>>> > >> > > > >>>>> Can you prove that it's safe to ignore irrational > solutions? > >> > > Here's a > >> > > > >>>>> (non-optimal) irrational solution for f(3), using 5 > >> component > >> > > values: > >> > > > >>>>> > >> > > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 > >> > > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 > >> > > > >>>>> 1/3 = 1/3 > >> > > > >>>>> > >> > > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 > >> > > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - > >> 4)/24 > >> > > > >>>>> > >> > > > >>>>> Can we always do as well (or better) using only rational > >> component > >> > > > >>>>> values? > >> > > > >>>>> I suspect the answer is yes. > >> > > > >>>>> > >> > > > >>>>> Note that the example above has the general form: > >> > > > >>>>> > >> > > > >>>>> 1/3 = a + (1/3 - a) > >> > > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) > >> > > > >>>>> 1/3 = 1/3 > >> > > > >>>>> > >> > > > >>>>> 1/2 = a + (1/2 - a) > >> > > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) > >> > > > >>>>> > >> > > > >>>>> This works for any value of "a" that doesn't produce zero > or > >> > > negative > >> > > > >>>>> values. In particular, "a" can be given a rational > >> value. Is it > >> > > the > >> > > > >>>>> case that any solution involving irrational values can be > >> > > decomposed > >> > > > >>>>> into something like this, which in turn can be converted > >> into a > >> > > > >>>>> rational solution? > >> > > > >>>>> > >> > > > >>>>> Tom > >> > > > >>>>> > >> > > > >>>>> > >> > > > >>>>> Allan Wechsler writes: > >> > > > >>>>> > I was challenging myself to try to think of any finite > >> > > algorithm, > >> > > > >>>>> be it > >> > > > >>>>> > ever so expensive and cumbersome, that would settle the > >> > > question of > >> > > > >>>>> whether > >> > > > >>>>> > p pieces suffices for a given n. A useful lemma would > >> be that > >> > > if it > >> > > > >>>>> can be > >> > > > >>>>> > done in p pieces, then it can be done with pieces whose > >> > > > >>>>> denominaters divide > >> > > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my > >> purposes > >> > > it > >> > > > >>>>> doesn't > >> > > > >>>>> > matter how weak this lemma is.) > >> > > > >>>>> > > >> > > > >>>>> > Then, we could say, "Iterate over all partitions of n! > >> into p > >> > > > >>>>> parts, and > >> > > > >>>>> > for each such partition, check to see if it works, > using > >> the > >> > > > >>>>> partition as > >> > > > >>>>> > the numerators of fractions whose denominators are all > >> n!." > >> > > This > >> > > > >>>>> would be > >> > > > >>>>> > heinously expensive but it would at least provide an > >> upper > >> > > bound on > >> > > > >>>>> how > >> > > > >>>>> > much computational work we have to do. > >> > > > >>>>> > > >> > > > >>>>> > But I can't even prove the lemma. > >> > > > >>>>> > > >> > > > >>>>> > >> > > > >> > > _______________________________________________ > >> > > math-fun mailing list > >> > > math-fun@mailman.xmission.com > >> > > https://mailman.xmission.com/ cgi-bin/mailman/listinfo/math-f un > >> > > > >> > _______________________________________________ > >> > math-fun mailing list > >> > math-fun@mailman.xmission.com > >> > https://mailman.xmission.com/ cgi-bin/mailman/listinfo/math- fun > >> > > >> > >> -- > >> > >> _______________________________________________ > >> math-fun mailing list > >> math-fun@mailman.xmission.com > >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math- fun > >> > >> > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun@mailman.xmission.com > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Is it necessarily the case that an optimal solution for n+1 can be derived from an optimal solution for n by making additional cuts (i.e., by splitting some of the fractions)? Another way to ask this is whether an optimal solution for n+1 can be reduced to an optimal solution for n by combining pieces. I.e., can the groupings up to n always be formed with certain pieces from the n+1 solution always occurring in pairs? Tom Victor Miller writes:
Allan, Thanks. Why didn't I see that? In any case it's not completely clear to me what the algorithms were to find good solutions for f(n), but here's one:
Do this inductively -- collect a whole bunch of good solutions for f(n), and try to extend them to f(n+1), by a sort of bin packing procedure: have n+1 bin of capacity 1/(n+1) and for each solution for f(n) try to place the pieces in the bins so that you need to make the minimal number of cuts to make them fit exactly. It's not clear, a priori, which of the minimal solutions to f(n) will extend to f(n+1), you need to collect a bunch of them.
On Tue, Dec 19, 2017 at 10:47 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK).
They seem like a rather jolly, collegial crew over there.
They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here.
Victor, I can't remember if you managed to put a lower bound on the LCM of the denominators. The Russian group discussed this as well, and found some optimal solutions for n=5 that required a common denominator of 120 rather than 60. But n=5 does have some solutions based on 60ths. My intuition is that there will always be optimal solutions based on a common denominator of LCM(1..n). But I can't come close to proving it. Tom, the Russians give several complete lists of solutions for n=5 and (I think) n=6; it ought to be possible to use them to look for ones that are not refinements of smaller solutions. I am guessing that there are some such, which would answer your question in the negative. On Tue, Dec 19, 2017 at 11:57 AM, Tom Karzes <karzes@sonic.net> wrote:
Is it necessarily the case that an optimal solution for n+1 can be derived from an optimal solution for n by making additional cuts (i.e., by splitting some of the fractions)?
Another way to ask this is whether an optimal solution for n+1 can be reduced to an optimal solution for n by combining pieces. I.e., can the groupings up to n always be formed with certain pieces from the n+1 solution always occurring in pairs?
Tom
Victor Miller writes:
Allan, Thanks. Why didn't I see that? In any case it's not completely clear to me what the algorithms were to find good solutions for f(n), but here's one:
Do this inductively -- collect a whole bunch of good solutions for f(n), and try to extend them to f(n+1), by a sort of bin packing procedure: have n+1 bin of capacity 1/(n+1) and for each solution for f(n) try to place the pieces in the bins so that you need to make the minimal number of cuts to make them fit exactly. It's not clear, a priori, which of the minimal solutions to f(n) will extend to f(n+1), you need to collect a bunch of them.
On Tue, Dec 19, 2017 at 10:47 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK).
They seem like a rather jolly, collegial crew over there.
They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Warren writes: It seems to me the top open problem here is to determine the asymptotic behavior of F(n). It clearly is somewhere between linear and quadratic growth. Theorem: F(n) < 0.2704 * n^2 for all large-enough n. This is due to the inequality F(n) <= F(n-1) + n - LargestDivisor(n). and the fact that the average value of LargestDivisor(n) is C*n where C=0.4593 roughly, and more precisely C = Sum[Product[1-1/Prime[m],{m,1,k}]/Prime[k],{k,1,infinity}]. Here 0.2704 = (1-C)/2 more precisely. I doubt that upper bound is tight. I have a nonrigorous but reasonably convincing "random covering" argument that there exists a constant K>0 such that F(n) < K * (n^2) / log(n) for all sufficiently large n. Subquadratic. It even is plausible that any K>1 works, using natural log; perhaps my argument can be rigorized but at present I have not done that. On Tue, Dec 19, 2017 at 1:01 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Victor, I can't remember if you managed to put a lower bound on the LCM of the denominators. The Russian group discussed this as well, and found some optimal solutions for n=5 that required a common denominator of 120 rather than 60. But n=5 does have some solutions based on 60ths. My intuition is that there will always be optimal solutions based on a common denominator of LCM(1..n). But I can't come close to proving it.
Tom, the Russians give several complete lists of solutions for n=5 and (I think) n=6; it ought to be possible to use them to look for ones that are not refinements of smaller solutions. I am guessing that there are some such, which would answer your question in the negative.
On Tue, Dec 19, 2017 at 11:57 AM, Tom Karzes <karzes@sonic.net> wrote:
Is it necessarily the case that an optimal solution for n+1 can be derived from an optimal solution for n by making additional cuts (i.e., by splitting some of the fractions)?
Another way to ask this is whether an optimal solution for n+1 can be reduced to an optimal solution for n by combining pieces. I.e., can the groupings up to n always be formed with certain pieces from the n+1 solution always occurring in pairs?
Tom
Victor Miller writes:
Allan, Thanks. Why didn't I see that? In any case it's not completely clear to me what the algorithms were to find good solutions for f(n), but here's one:
Do this inductively -- collect a whole bunch of good solutions for f(n), and try to extend them to f(n+1), by a sort of bin packing procedure: have n+1 bin of capacity 1/(n+1) and for each solution for f(n) try to place the pieces in the bins so that you need to make the minimal number of cuts to make them fit exactly. It's not clear, a priori, which of the minimal solutions to f(n) will extend to f(n+1), you need to collect a bunch of them.
On Tue, Dec 19, 2017 at 10:47 AM, Allan Wechsler <acwacw@gmail.com> wrote:
Google translate seems to work fine for the Russian discussion at dxdy.ru. Every once in a while you trip over something (like LCM = NOK).
They seem like a rather jolly, collegial crew over there.
They also wrestled momentarily with the worry that the optimal solution might be irrational, but somebody quickly demonstrated that the problem was equivalent to very big systems of linear equations with rational coefficients, exactly as Victor pointed out here.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Dec 19, 2017, at 1:01 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Victor, I can't remember if you managed to put a lower bound on the LCM of the denominators. The Russian group discussed this as well, and found some optimal solutions for n=5 that required a common denominator of 120 rather than 60. But n=5 does have some solutions based on 60ths. My intuition is that there will always be optimal solutions based on a common denominator of LCM(1..n). But I can't come close to proving it.
I just recently started thinking about this and wondered if, for the case that the denominator is LCM(1..n), one could express feasibility just in terms of linear equations for 0/1 variables. Here’s what I've come up with so far, but I don’t guarantee I haven’t overlooked something! m = LCM(1..n) My 0/1 variables have four indices: x[i,j,k,p] i = 1..m labels the “atoms” of the pizza j = 2..n labels the “partition” (j = 3 means we serve three mathematicians) k = 1..j labels the parts of partition j p = 1..P labels the pizza pieces The smallest P that gives a feasible point is f(n). Here is the interpretation of the variables: x[i,j,k,p] = 1 if atom i belongs to piece p and in partition j lies in part k; x[i,j,k,p] = 0 otherwise. There are three kinds of equations: 1) for all (j,k,p) and all pairs (i,i’) : x[i,j,k,p] = x[i',j,k,p] 2) for all (i,j) : sum_(k,p) x[i,j,k,p] = 1 3) for all (j,k) : sum_(i,p) x[i,j,k,p] = m/j Roughly speaking, 1) says that all the atoms of a piece act the same way, 2) says every atom appears exactly once in each partition, and 3) says the partitions have equal size. -Veit
After reading the blog dxdy discussion, I've implemented the following: My MIP (mixed integer programming) setup is a lot like what Veit has suggested -- I do have extra relations to break symmetries (which is rather important since the symmetry group is huge). What I've added, is exhausting over all possible partitions (just the numbers not the sets -- I allow the MIP to find the placement) -- so if we have a putative value of f(n) = k, we look for partitions of k into m parts for each n/2 +1 <= m <= n, and only look at those whose parts are >=2 if m < n. For every combination of such I add sum constraints to insure that the number of parts corresponds to the assumed partition. In addition for the partitions for m=n, if a part has size 1 -- we know that a corresponding piece has size 1/n. Doing this can get lots of solutions -- at most 1 for each combination of partitions (most of them fail). I've found a few solutions for n=5 and n=6 which have denominator 2*LCM. Victor On Wed, Dec 20, 2017 at 4:56 PM, Veit Elser <ve10@cornell.edu> wrote:
On Dec 19, 2017, at 1:01 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Victor, I can't remember if you managed to put a lower bound on the LCM of the denominators. The Russian group discussed this as well, and found some optimal solutions for n=5 that required a common denominator of 120 rather than 60. But n=5 does have some solutions based on 60ths. My intuition is that there will always be optimal solutions based on a common denominator of LCM(1..n). But I can't come close to proving it.
I just recently started thinking about this and wondered if, for the case that the denominator is LCM(1..n), one could express feasibility just in terms of linear equations for 0/1 variables. Here’s what I've come up with so far, but I don’t guarantee I haven’t overlooked something!
m = LCM(1..n)
My 0/1 variables have four indices: x[i,j,k,p]
i = 1..m labels the “atoms” of the pizza j = 2..n labels the “partition” (j = 3 means we serve three mathematicians) k = 1..j labels the parts of partition j p = 1..P labels the pizza pieces
The smallest P that gives a feasible point is f(n).
Here is the interpretation of the variables:
x[i,j,k,p] = 1 if atom i belongs to piece p and in partition j lies in part k; x[i,j,k,p] = 0 otherwise.
There are three kinds of equations:
1) for all (j,k,p) and all pairs (i,i’) : x[i,j,k,p] = x[i',j,k,p]
2) for all (i,j) : sum_(k,p) x[i,j,k,p] = 1
3) for all (j,k) : sum_(i,p) x[i,j,k,p] = m/j
Roughly speaking, 1) says that all the atoms of a piece act the same way, 2) says every atom appears exactly once in each partition, and 3) says the partitions have equal size.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I read once about a solution for a loaf-formed cake, but that makes no difference here, here's the circular version: One eater takes the knife and makes a cut from center to perimeter. then, the cake is slowly rotated, with the knife above the same position. The first eater (including the one with the knife) who screams gets the piece that's cut at the knife's position and is out of the competition. Then the rotation is continued until either each eater has a piece or no cake is left. It's each eater's decision how much that will be.
participants (11)
-
Allan Wechsler -
Andy Latto -
Dirk Lattermann -
Guy Haworth -
James Propp -
Michael Kleber -
Neil Sloane -
rcs＠xmission.com -
Tom Karzes -
Veit Elser -
Victor Miller