[math-fun] Counterintuitive optimization
Does anyone have a favorite example of a fake optimum? One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution. I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal. (Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!) Jim
Hello, what about walking in the rain and trying to optimize the speed ? and not getting too wet.. https://www.quora.com/What-is-the-optimum-walking-speed-to-prevent-getting-w... Is this a good example ? or maybe the Nash equilibrium ? does not look intuitive at all to me. https://en.wikipedia.org/wiki/Nash_equilibrium Best regards, Simon Plouffe
I like the (somewhat well known) task of minimizing the time to cross a bridge in the dark, knowing that the bridge can only carry two persons, that there is only one flashlight needed, and that these 4 persons can cross the bridge in 1, 2, 5 and 10 minutes respectively. Hint: you can do better than 19 minutes. I also like one where you need to get three persons to cross a certain distance with one bike, knowing that the three can walk at speeds 6, 6, and 12 km/h but cycle at 15, 15, and 30 km/h respectively. The bike can be left lying on the road. The solution was somewhat surprising to me. Of course I don't remember where I saw them. The first one should be googleable, and I just made the numbers up for the second one. Cheers, Sébastien On 17 February 2016 at 16:34, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello,
what about walking in the rain and trying to optimize the speed ? and not getting too wet..
https://www.quora.com/What-is-the-optimum-walking-speed-to-prevent-getting-w...
Is this a good example ? or maybe the Nash equilibrium ?
does not look intuitive at all to me.
https://en.wikipedia.org/wiki/Nash_equilibrium
Best regards, Simon Plouffe _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, Feb 17, 2016 at 11:29 AM, Seb Perez-D <sbprzd+mathfun@gmail.com> wrote:
I like the (somewhat well known) task of minimizing the time to cross a bridge in the dark, knowing that the bridge can only carry two persons, that there is only one flashlight needed, and that these 4 persons can cross the bridge in 1, 2, 5 and 10 minutes respectively. Hint: you can do better than 19 minutes.
This is an example of a phenomenon I find interesting, where are intuitions can lead us to slightly inferior solutions, but they won't lead us to extremely inferior solutions. I'll bet that many people, in trying to solve the above problem, came up with a 19 minute solution, and maybe had some difficulty finding the 17 minute solution. But try giving someone who hasn't solved the problem before a similar problem, where the crossing times are 1, 2, 1,000,000, and 1,000,003 minutes. Now people find it much easier to find the solution that takes 1 million-and-change minutes, rather than the one that takes 2 million-and-change. A similar thing happens with the Monty Hall problem. You can model the problem with 3 cards. One of which, the Ace of spades, represents the prize. We shuffle the 3 cards, you choose 1, but don't turn it up yet, and I take the other two, look at them, and turn one of them (never the Ace of Spaces) face up. Now I ask if you want to switch to the other face-down card, and many people see no reason to switch; they erroneously reason "2 cards, I don't know anything about either, so the chances are 1/2 that each is the Ace of Spades". But give people the 52-door version of the same problem and see what happens. They choose a card, and leave it face down. I look at the other 51 cards, pull out the 37th card, and turn up the other 50, none of which are the ace of spades, face up. Now pretty much everyone wants to switch to the 37th card. Most explanations I've seen as to why people get the Monty Hall problem wrong would predict that people would have just as much trouble getting the 52-card problem right as the 3 card problem, but in fact, lots of people get the 3-card problem wrong, and pretty much everyone gets the 52 card problem right. Andy Latto andy.latto@pobox.com
I must say, this one was fun to think about and read about; thanks for posting. On Wed, Feb 17, 2016 at 8:29 AM, Seb Perez-D <sbprzd+mathfun@gmail.com> wrote:
I also like one where you need to get three persons to cross a certain distance with one bike, knowing that the three can walk at speeds 6, 6, and 12 km/h but cycle at 15, 15, and 30 km/h respectively. The bike can be left lying on the road. The solution was somewhat surprising to me.
This topic always reminds me of my most embarrassing programming/math failure. Many years ago, Minsky invented a robotic arm design, and master machinist Bill Bennett made it. (Google “Minsky Bennett arm”.) It had 8 hinge joints, so it would seem that deploying the “hand” end to any given position and orientation (6 space) would be easy, due to the 2 degrees of freedom. I was asked to write a program to move the arm to any desired goal. The only approach I knew was hill climbing. The computation of end position and orientation from the flexion of the 8 joints was straightforward. But the hill climber kept getting stuck close to the goal, in local minima. I tried perturbations in the neighborhood. I tried using the derivatives of two joints moving simultaneously. Maybe also three or more simultaneously, I don’t remember. I gave it goals that result from roughly midrange positions of the joints, so I knew the goals were achievable and not along some boundary plane of joint space. All to no avail. It often got stuck in local minima, close but too far for a robot hand to reasonably do something like pick up a block. I had to give up. I don’t think anyone else tried to write a deployer. My failure resulted in the arm, a wonder of engineering and very organic looking, being relegated to curiosity status. Last I knew, it was on display at the MIT museum. — Mike
On Feb 17, 2016, at 10:01 AM, James Propp <jamespropp@gmail.com> wrote:
Does anyone have a favorite example of a fake optimum?
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
You mean like this one? "Arrange 8 points on the surface of a unit sphere such that the minimum distance between points is as large as possible." There are other optimisation problems like this which are not packing problems per se, such as: "Determine the Steiner tree of four points positioned at the vertices of a square." Or even: "What is the optimal foam of soap bubbles?" (The answer to this one is unknown, but Kelvin's conjecturally optimal foam of truncated octahedra is beaten by the Wieare-Phelan structure.)
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, exactly like that. (The Steiner tree problem was actually one I already had in mind.) Jim On Wednesday, February 17, 2016, Adam P. Goucher <apgoucher@gmx.com> wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
You mean like this one?
"Arrange 8 points on the surface of a unit sphere such that the minimum distance between points is as large as possible."
There are other optimisation problems like this which are not packing problems per se, such as:
"Determine the Steiner tree of four points positioned at the vertices of a square."
Or even:
"What is the optimal foam of soap bubbles?"
(The answer to this one is unknown, but Kelvin's conjecturally optimal foam of truncated octahedra is beaten by the Wieare-Phelan structure.)
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or
A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's my favorite such problem (suggested to me by D G Arthur, with some history before that I can dig out if anyone is interested). Grading in Concrete Math is based on a series of n problem sets p_1 .. p_n. For each problem set p_i, there are q_i questions; the number of questions a student gets correct is s_i. At the end of the year, the student may *drop* any k of the n problem sets (k is fixed and given). Let G be the subset of {1..n} remaining (G is of size n-k). The final grade is calculated as (sum_{j in G} s_j) / (sum_{j in G) p_j) For instance, if my grades were 6 of 10 (60%), 42 of 60 (70%), 23 of 30 (76.7%) my best option is not to drop the 6 of 10,which would leave me with 65 of 90 or 72.2%, but to drop the "better" 42 of 60, leaving me with 29 of 40 or 72.5%. How do you pick which k grades to drop to maximize the final score? The solution has some elegance, though it may not be as simple as many of the puzzles we see. On Wed, Feb 17, 2016 at 10:26 AM, James Propp <jamespropp@gmail.com> wrote:
Yes, exactly like that. (The Steiner tree problem was actually one I already had in mind.)
Jim
On Wednesday, February 17, 2016, Adam P. Goucher <apgoucher@gmx.com> wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
You mean like this one?
"Arrange 8 points on the surface of a unit sphere such that the minimum distance between points is as large as possible."
There are other optimisation problems like this which are not packing problems per se, such as:
"Determine the Steiner tree of four points positioned at the vertices of a square."
Or even:
"What is the optimal foam of soap bubbles?"
(The answer to this one is unknown, but Kelvin's conjecturally optimal foam of truncated octahedra is beaten by the Wieare-Phelan structure.)
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or
A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to
contributors,
so
if you prefer anonymity, please let me know!)
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> 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
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Just wondering: Should that denominator be the sum of the q_j, rather than of the p_j ? It seems easier to add, and then divide by the sum of, numbers than of problem sets, whose algebraic structure is mysterious. —Dan
On Feb 17, 2016, at 5:23 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Here's my favorite such problem (suggested to me by D G Arthur, with some history before that I can dig out if anyone is interested).
Grading in Concrete Math is based on a series of n problem sets p_1 .. p_n. For each problem set p_i, there are q_i questions; the number of questions a student gets correct is s_i.
At the end of the year, the student may *drop* any k of the n problem sets (k is fixed and given). Let G be the subset of {1..n} remaining (G is of size n-k). The final grade is calculated as
(sum_{j in G} s_j) / (sum_{j in G) p_j)
For instance, if my grades were
6 of 10 (60%), 42 of 60 (70%), 23 of 30 (76.7%)
my best option is not to drop the 6 of 10,which would leave me with 65 of 90 or 72.2%, but to drop the "better" 42 of 60, leaving me with 29 of 40 or 72.5%.
How do you pick which k grades to drop to maximize the final score? The solution has some elegance, though it may not be as simple as many of the puzzles we see.
Yes, you are correct. My apologies for the error. It should read (sum_{j in G} s_j) / (sum_{j in G) q_j) -tom On Wed, Feb 17, 2016 at 5:52 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just wondering: Should that denominator be the sum of the q_j, rather than of the p_j ?
It seems easier to add, and then divide by the sum of, numbers than of problem sets, whose algebraic structure is mysterious.
—Dan
On Feb 17, 2016, at 5:23 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Here's my favorite such problem (suggested to me by D G Arthur, with some history before that I can dig out if anyone is interested).
Grading in Concrete Math is based on a series of n problem sets p_1 .. p_n. For each problem set p_i, there are q_i questions; the number of questions a student gets correct is s_i.
At the end of the year, the student may *drop* any k of the n problem sets (k is fixed and given). Let G be the subset of {1..n} remaining (G is of size n-k). The final grade is calculated as
(sum_{j in G} s_j) / (sum_{j in G) p_j)
For instance, if my grades were
6 of 10 (60%), 42 of 60 (70%), 23 of 30 (76.7%)
my best option is not to drop the 6 of 10,which would leave me with 65 of 90 or 72.2%, but to drop the "better" 42 of 60, leaving me with 29 of 40 or 72.5%.
How do you pick which k grades to drop to maximize the final score? The solution has some elegance, though it may not be as simple as many of the puzzles we see.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Simpson's paradox can be cast as a fake optimum if you're looking for, say, the best linear fit to a collection of data. On Wed, Feb 17, 2016 at 5:52 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Just wondering: Should that denominator be the sum of the q_j, rather than of the p_j ?
It seems easier to add, and then divide by the sum of, numbers than of problem sets, whose algebraic structure is mysterious.
—Dan
On Feb 17, 2016, at 5:23 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Here's my favorite such problem (suggested to me by D G Arthur, with some history before that I can dig out if anyone is interested).
Grading in Concrete Math is based on a series of n problem sets p_1 .. p_n. For each problem set p_i, there are q_i questions; the number of questions a student gets correct is s_i.
At the end of the year, the student may *drop* any k of the n problem sets (k is fixed and given). Let G be the subset of {1..n} remaining (G is of size n-k). The final grade is calculated as
(sum_{j in G} s_j) / (sum_{j in G) p_j)
For instance, if my grades were
6 of 10 (60%), 42 of 60 (70%), 23 of 30 (76.7%)
my best option is not to drop the 6 of 10,which would leave me with 65 of 90 or 72.2%, but to drop the "better" 42 of 60, leaving me with 29 of 40 or 72.5%.
How do you pick which k grades to drop to maximize the final score? The solution has some elegance, though it may not be as simple as many of the puzzles we see.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On 2016-02-17 07:01, James Propp wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim
How many unit diameter pennies fit in a 2x100 rectangle? And this one amazes me: http://www2.stetson.edu/~efriedma/cirRcir/ Why isn't #31 just #32 symmetrized, with the big purple reduced to a green, and the bottom orange deleted? --rwg
On 2016-02-18 21:01, rwg wrote:
On 2016-02-17 07:01, James Propp wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim
How many unit diameter pennies fit in a 2x100 rectangle?
Sorry! I meant 2 by 200 rectangle!
And this one amazes me: http://www2.stetson.edu/~efriedma/cirRcir/ Why isn't #31 just #32 symmetrized, with the big purple reduced to a green, and the bottom orange deleted? --rwg
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL On 2/19/16, rwg <rwg@sdf.org> wrote:
On 2016-02-18 21:01, rwg wrote:
On 2016-02-17 07:01, James Propp wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim
How many unit diameter pennies fit in a 2x100 rectangle?
Sorry! I meant 2 by 200 rectangle!
And this one amazes me: http://www2.stetson.edu/~efriedma/cirRcir/ Why isn't #31 just #32 symmetrized, with the big purple reduced to a green, and the bottom orange deleted? --rwg
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Most are only best known; usually he gives a pointer if a (nontrivial) proof exists. Charles Greathouse Analyst/Programmer Case Western Reserve University On Fri, Feb 19, 2016 at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
On 2/19/16, rwg <rwg@sdf.org> wrote:
On 2016-02-18 21:01, rwg wrote:
On 2016-02-17 07:01, James Propp wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim
How many unit diameter pennies fit in a 2x100 rectangle?
Sorry! I meant 2 by 200 rectangle!
And this one amazes me: http://www2.stetson.edu/~efriedma/cirRcir/ Why isn't #31 just #32 symmetrized, with the big purple reduced to a green, and the bottom orange deleted? --rwg
_______________________________________________ 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 had the very same question. But on some related pages, some packings or coverings are referred to as best known and others are said to be proven the best . . . so I'm guessing that unless the word "proved" is used, they are only the best known. It's not easy to find the absolute optimum of such things with proof. One thing a torus-lover like me would like to see added if Erich decides to do so is additional best-known or proven optima for the two most symmetrical tori: a) the square torus C / Z[i] and b) the hexagonal torus C / Z[w] for w = exp(2pi*i/3) Another interesting thing would be to see graphs of the natural integer index for each case plotted against the best-known optimum. It's particularly interesting to see the "discontinuities" in such graphs. (For example, the smallest radius circle that contains 6 nonoverlapping unit circles is the same radius as for 7, but 8 takes a jump.) —Dan
On Feb 19, 2016, at 5:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
I had the very same question. But on some related pages, some packings or coverings are referred to as best known and others are said to be proven the best . . . so I'm guessing that unless the word "proved" is used, they are only the best known.
It's not easy to find the absolute optimum of such things with proof.
this is correct. in general on my packing pages "Trivial" means there is an easy proof not attributed to a given person, "Proved by ..." means it has been proven optimal, and "Found by ..." means it is only the best currently known, with no proof known. much fame awaits those who could find such proofs, but they do tend to be hard. for example, it was only in this century that the best packing of 6 unit squares in a square was confirmed to be a square of side 3. (i proved the cases for 7, 8, 14, and 15 squares a few years earlier.) i suspect 27 unit squares in a square will be the next to be proved. http://www2.stetson.edu/~efriedma/squinsqu/s27.gif
One thing a torus-lover like me would like to see added if Erich decides to do so is additional best-known or proven optima for the two most symmetrical tori:
when i retire in a few years, my guess is that you will see exactly that. :) erich
We used this as Problem 211 in The Inquisitive Problem Solver. I don't know where we got it from. Elwyn Berlekamp and Joe Buhler may have used it in their column in Emissary, the journal of MSRI. We only gave a packing of 477 balls in a 1 x 2 x 238 box. I know that better results are known to Ron Graham and to Elwyn Berlekamp. Perhaps either or both of them will tell us what they know, and how much has been proved. R. On Fri, 19 Feb 2016, Erich Friedman wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
I had the very same question. But on some related pages, some packings or coverings are referred to as best known and others are said to be proven the best . . . so I'm guessing that unless the word "proved" is used, they are only the best known.
It's not easy to find the absolute optimum of such things with proof.
this is correct. in general on my packing pages "Trivial" means there is an easy proof not attributed to a given person, "Proved by ..." means it has been proven optimal, and "Found by ..." means it is only the best currently known, with no proof known.
much fame awaits those who could find such proofs, but they do tend to be hard. for example, it was only in this century that the best packing of 6 unit squares in a square was confirmed to be a square of side 3. (i proved the cases for 7, 8, 14, and 15 squares a few years earlier.) i suspect 27 unit squares in a square will be the next to be proved.
http://www2.stetson.edu/~efriedma/squinsqu/s27.gif
One thing a torus-lover like me would like to see added if Erich decides to do so is additional best-known or proven optima for the two most symmetrical tori:
when i retire in a few years, my guess is that you will see exactly that. :)
erich _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Richard — thanks for mentioning that book, whose existence I knew nothing of. For anyone who like me was eager to see the solution, I found it by googling on the unquoted phrase: 477 balls in a 1 x 2 x 238 box which leads right to that book. —Dan P.S. Somehow this reminds me of the "sausage catastrophe", which has been discussed on this forum. (Or google on that phrase and view the hit in Sphere Packings, Lattices, and Groups, by Neil and John Conway, which I found to be the 3rd one down.)
On Feb 19, 2016, at 10:14 AM, rkg <rkg@ucalgary.ca> wrote:
We used this as Problem 211 in The Inquisitive Problem Solver. I don't know where we got it from. Elwyn Berlekamp and Joe Buhler may have used it in their column in Emissary, the journal of MSRI. We only gave a packing of 477 balls in a 1 x 2 x 238 box. I know that better results are known to Ron Graham and to Elwyn Berlekamp. Perhaps either or both of them will tell us what they know, and how much has been proved. R.
On Fri, 19 Feb 2016, Erich Friedman wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
I had the very same question. But on some related pages, some packings or coverings are referred to as best known and others are said to be proven the best . . . so I'm guessing that unless the word "proved" is used, they are only the best known.
It's not easy to find the absolute optimum of such things with proof.
this is correct. in general on my packing pages "Trivial" means there is an easy proof not attributed to a given person, "Proved by ..." means it has been proven optimal, and "Found by ..." means it is only the best currently known, with no proof known.
much fame awaits those who could find such proofs, but they do tend to be hard. for example, it was only in this century that the best packing of 6 unit squares in a square was confirmed to be a square of side 3. (i proved the cases for 7, 8, 14, and 15 squares a few years earlier.) i suspect 27 unit squares in a square will be the next to be proved.
http://www2.stetson.edu/~efriedma/squinsqu/s27.gif
One thing a torus-lover like me would like to see added if Erich decides to do so is additional best-known or proven optima for the two most symmetrical tori:
when i retire in a few years, my guess is that you will see exactly that. :)
erich _______________________________________________ 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
Thanks for the pointer, Richard. Locally optimizing two pennies at the end improves 477 pennies in 2x238 to 473 pennies in 2x236 I don't see any further improvements. The same idea lets you pack 400 pennies in 1.964 x 200 For Gosper's original 2x200 teaser, I'd be very surprised if 401 were possible. Scott On Fri, Feb 19, 2016 at 10:14 AM, rkg <rkg@ucalgary.ca> wrote:
We used this as Problem 211 in The Inquisitive Problem Solver. I don't know where we got it from. Elwyn Berlekamp and Joe Buhler may have used it in their column in Emissary, the journal of MSRI. We only gave a packing of 477 balls in a 1 x 2 x 238 box. I know that better results are known to Ron Graham and to Elwyn Berlekamp. Perhaps either or both of them will tell us what they know, and how much has been proved. R.
On Fri, 19 Feb 2016, Erich Friedman wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved
to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
I had the very same question. But on some related pages, some
packings or coverings are referred to as best known and others are said to be proven the best . . . so I'm guessing that unless the word "proved" is used, they are only the best known.
It's not easy to find the absolute optimum of such things with proof.
this is correct. in general on my packing pages "Trivial" means there is an easy proof not attributed to a given person, "Proved by ..." means it has been proven optimal, and "Found by ..." means it is only the best currently known, with no proof known.
much fame awaits those who could find such proofs, but they do tend to be hard. for example, it was only in this century that the best packing of 6 unit squares in a square was confirmed to be a square of side 3. (i proved the cases for 7, 8, 14, and 15 squares a few years earlier.) i suspect 27 unit squares in a square will be the next to be proved.
http://www2.stetson.edu/~efriedma/squinsqu/s27.gif
One thing a torus-lover like me would like to see added if Erich
decides to do so is additional best-known or proven optima for the two most symmetrical tori:
when i retire in a few years, my guess is that you will see exactly that. :)
erich _______________________________________________ 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
Ron Graham admits to knowing more about this problem, but hasn't vouchsafed anything yet. R. On Mon, 22 Feb 2016, Scott Huddleston wrote:
Thanks for the pointer, Richard. Locally optimizing two pennies at the end improves 477 pennies in 2x238 to 473 pennies in 2x236 I don't see any further improvements.
The same idea lets you pack 400 pennies in 1.964 x 200
For Gosper's original 2x200 teaser, I'd be very surprised if 401 were possible.
Scott
On Fri, Feb 19, 2016 at 10:14 AM, rkg <rkg@ucalgary.ca> wrote:
We used this as Problem 211 in The Inquisitive Problem Solver. I don't know where we got it from. Elwyn Berlekamp and Joe Buhler may have used it in their column in Emissary, the journal of MSRI. We only gave a packing of 477 balls in a 1 x 2 x 238 box. I know that better results are known to Ron Graham and to Elwyn Berlekamp. Perhaps either or both of them will tell us what they know, and how much has been proved. R.
On Fri, 19 Feb 2016, Erich Friedman wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved
to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
I had the very same question. But on some related pages, some
packings or coverings are referred to as best known and others are said to be proven the best . . . so I'm guessing that unless the word "proved" is used, they are only the best known.
It's not easy to find the absolute optimum of such things with proof.
this is correct. in general on my packing pages "Trivial" means there is an easy proof not attributed to a given person, "Proved by ..." means it has been proven optimal, and "Found by ..." means it is only the best currently known, with no proof known.
much fame awaits those who could find such proofs, but they do tend to be hard. for example, it was only in this century that the best packing of 6 unit squares in a square was confirmed to be a square of side 3. (i proved the cases for 7, 8, 14, and 15 squares a few years earlier.) i suspect 27 unit squares in a square will be the next to be proved.
http://www2.stetson.edu/~efriedma/squinsqu/s27.gif
One thing a torus-lover like me would like to see added if Erich
decides to do so is additional best-known or proven optima for the two most symmetrical tori:
when i retire in a few years, my guess is that you will see exactly that. :)
erich _______________________________________________ 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
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters … WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that’s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal. -Veit http://mathoverflow.net/questions/38086/a-circle-packing-conjecture
Maybe it's obvious, but I'd just like to know if the maximal sum of the radii of n circles in a circle of unit radius approaches its upper bound sqrt(n). (Or have I been caught in the sort of trap that inspired this conversation?) Charles Greathouse Analyst/Programmer Case Western Reserve University On Fri, Feb 19, 2016 at 9:08 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters … WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that’s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal.
-Veit
http://mathoverflow.net/questions/38086/a-circle-packing-conjecture _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
For best known packings of equal circles in a circle see here http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html On Fri, Feb 19, 2016 at 2:07 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
Maybe it's obvious, but I'd just like to know if the maximal sum of the radii of n circles in a circle of unit radius approaches its upper bound sqrt(n). (Or have I been caught in the sort of trap that inspired this conversation?)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Feb 19, 2016 at 9:08 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com>
wrote:
I'm a tad suspicious: are the circle packings on Friedman's page
proved
to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters … WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that’s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal.
-Veit
http://mathoverflow.net/questions/38086/a-circle-packing-conjecture _______________________________________________ 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
Incidentally, an amusement I played with my freshman roommates at MIT as well as those in the apartment across the hall (3rd floor of 50 Massachusetts Ave.) was to find the tightest arrangement of N pennies on a table, for various N — the identical problem. —Dan
On Feb 19, 2016, at 12:20 PM, James Buddenhagen <jbuddenh@gmail.com> wrote:
For best known packings of equal circles in a circle see here http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html <http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html>
My intuitions say that the maximal sum of radii for circles within a circle will approach, not sqrt(n), but sqrt(An), where A = pi sqrt(3)/6 ~ .9069 is the ration of the area inside the circles to the total area in a hexagonal close-packing. To get a radius-sum of sqrt(n), you'd want n circles of radius 1/sqrt(n). But those will have total area pi, the same as the area of the bounding circle, while my intuition says that when you have lots of small circles, they will be roughly the same size in roughly a hexagonal close-packing, so they won't have total area more than A pi. So if there are n circles, each should have area A pi/n, or radius sqrt(A)/sqrt(n), and n of them have total radius sqrt(nA). Andy Latto andy.latto@pobox.com On Fri, Feb 19, 2016 at 3:07 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
Maybe it's obvious, but I'd just like to know if the maximal sum of the radii of n circles in a circle of unit radius approaches its upper bound sqrt(n). (Or have I been caught in the sort of trap that inspired this conversation?)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Feb 19, 2016 at 9:08 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters … WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that’s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal.
-Veit
http://mathoverflow.net/questions/38086/a-circle-packing-conjecture _______________________________________________ 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
-- Andy.Latto@pobox.com
I think this can be improved by staging the circle sizes, assuming you're allowed to use circles of different sizes. Let N be humungous. (stage 1) Allocate some minor portion n of N to a close packing of largish circles that comes close to achieving the coverage of hexagonal close-packing. This leaves ~10% of the area uncovered. (stage 2) Now use the remaining N-n (much smaller) circles to cover that 10%. The coverage of that will approach the value for hex-close-packing, since the second stage circles are tiny, generally tinier than the wastage in the irregularly shaped holes left after stage 1. For sufficiently large N, and a sufficient ratio between the stage 1 and stage 2 circles, the uncovered area approaches 10% x 10% = 1%. The idea can be used with more stages to make the uncovered area approach 0%. Unclear if this maximizes the radial sum. Rich ----------- Quoting Andy Latto <andy.latto@pobox.com>:
My intuitions say that the maximal sum of radii for circles within a circle will approach, not sqrt(n), but sqrt(An), where A = pi sqrt(3)/6 ~ .9069 is the ration of the area inside the circles to the total area in a hexagonal close-packing. To get a radius-sum of sqrt(n), you'd want n circles of radius 1/sqrt(n). But those will have total area pi, the same as the area of the bounding circle, while my intuition says that when you have lots of small circles, they will be roughly the same size in roughly a hexagonal close-packing, so they won't have total area more than A pi. So if there are n circles, each should have area A pi/n, or radius sqrt(A)/sqrt(n), and n of them have total radius sqrt(nA).
Andy Latto andy.latto@pobox.com
On Fri, Feb 19, 2016 at 3:07 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
Maybe it's obvious, but I'd just like to know if the maximal sum of the radii of n circles in a circle of unit radius approaches its upper bound sqrt(n). (Or have I been caught in the sort of trap that inspired this conversation?)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Feb 19, 2016 at 9:08 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ? WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that?s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal.
-Veit
http://mathoverflow.net/questions/38086/a-circle-packing-conjecture _______________________________________________ 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
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, Feb 19, 2016 at 4:42 PM, <rcs@xmission.com> wrote:
I think this can be improved by staging the circle sizes, assuming you're allowed to use circles of different sizes.
If by "improved". you mean "fills a higher percentage of the circle" sure. And by having largish, much smaller, and much smaller than that circles, we can have A^3 inside the circles. But we're not trying to maximize the area inside the circles, we're trying to maximize the sum of their radii. If we have n numbers,. and a constraint on the sum of their squares, we maximize their sum by making them all equal. We have a hard constraint that the sum of the squares of the radii must be less than 1, because the areas of the circles must sum to less than the area of the large circle. So we probably want to make the circles close to the same size. If the circles are all the same size, we have a tighter soft constraint that the sum of the radii must be less than sqrt(A), because we can't fill any area bigger than a hexagonal close packing. My intuition says that if we try to use circles of different radii, the gain by needing to satisfy the soft constraint instead of the hard one is less than the loss by not having the radii nearly equal. The difference between the soft and hard constraints isn't that big, because sqrt(A) is already close to 1, and I don't think we get to fill much extra area by varying the circle size until the size of the small circles is small enough that we can fit one into the deltoid made by three mutually tangent larger circles, and I think that this much variation in size will lead to a loss of more than a factor of sqrt(A). Not a proof by any means, just my intuitions. Andy Latto andy.latto@pobox.com
Let N be humungous.
(stage 1) Allocate some minor portion n of N to a close packing of largish circles that comes close to achieving the coverage of hexagonal close-packing. This leaves ~10% of the area uncovered.
(stage 2) Now use the remaining N-n (much smaller) circles to cover that 10%. The coverage of that will approach the value for hex-close-packing, since the second stage circles are tiny, generally tinier than the wastage in the irregularly shaped holes left after stage 1. For sufficiently large N, and a sufficient ratio between the stage 1 and stage 2 circles, the uncovered area approaches 10% x 10% = 1%.
The idea can be used with more stages to make the uncovered area approach 0%.
Unclear if this maximizes the radial sum.
Rich
----------- Quoting Andy Latto <andy.latto@pobox.com>:
My intuitions say that the maximal sum of radii for circles within a circle will approach, not sqrt(n), but sqrt(An), where A = pi sqrt(3)/6 ~ .9069 is the ration of the area inside the circles to the total area in a hexagonal close-packing. To get a radius-sum of sqrt(n), you'd want n circles of radius 1/sqrt(n). But those will have total area pi, the same as the area of the bounding circle, while my intuition says that when you have lots of small circles, they will be roughly the same size in roughly a hexagonal close-packing, so they won't have total area more than A pi. So if there are n circles, each should have area A pi/n, or radius sqrt(A)/sqrt(n), and n of them have total radius sqrt(nA).
Andy Latto andy.latto@pobox.com
On Fri, Feb 19, 2016 at 3:07 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
Maybe it's obvious, but I'd just like to know if the maximal sum of the radii of n circles in a circle of unit radius approaches its upper bound sqrt(n). (Or have I been caught in the sort of trap that inspired this conversation?)
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Fri, Feb 19, 2016 at 9:08 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ? WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that?s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal.
-Veit
http://mathoverflow.net/questions/38086/a-circle-packing-conjecture _______________________________________________ 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
-- 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
-- Andy.Latto@pobox.com
Also interesting would be to maximize the sum of the pth power of the diameters, for N = 1,2,3,.... I wonder if for some given N the maximizing configuration changes discontinuously as p goes past some value p_0. —Dan
On Feb 19, 2016, at 6:08 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 19, 2016, at 8:48 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters … WFL
I have a conjecture that the maximum-sum-of-diameters packings have triangulated contact graphs. If that’s true, one could enumerate the graphs and calculate the packing for each one to see which is maximal.
-Veit
http://mathoverflow.net/questions/38086/a-circle-packing-conjecture
On 2016-02-19 05:48, Fred Lunnon wrote:
I'm a tad suspicious: are the circle packings on Friedman's page proved to be maximal, or are they merely the best known so far? There is no link to any proofs, or key to diameters ... WFL
But even if suboptimal, #31 apparently refutes the optimality of symmetrizing #32. Who'd'a thunk? --rwg (Cantrell actually sent me his diameters, but dammit, I can't find them.)
On 2/19/16, rwg <rwg@sdf.org> wrote:
On 2016-02-18 21:01, rwg wrote:
On 2016-02-17 07:01, James Propp wrote:
Does anyone have a favorite example of a fake optimum?
One class of examples that comes to mind is certain packing problems, where the constraints all obey some sort of symmetry but the optimal symmetrical solution is not as good as the optimal asymmetrical solution.
I'm especially interested in optimization problems where a greedy approach seems intuitively optimal but isn't. E.g., try to construct the biggest possible subset of {1,2,...,20} in which no two elements differ by 3 or 5. A greedy construction gives {1,2,3,9,10,11,17,18,19}, but this isn't optimal.
(Yes, this is for my blog. My default is to give credit to contributors, so if you prefer anonymity, please let me know!)
Jim
How many unit diameter pennies fit in a 2x100 rectangle?
Sorry! I meant 2 by 200 rectangle!
And this one amazes me: http://www2.stetson.edu/~efriedma/cirRcir/ Why isn't #31 just #32 symmetrized, with the big purple reduced to a green, and the bottom orange deleted? --rwg
participants (20)
-
Adam P. Goucher -
Andy Latto -
Charles Greathouse -
Dan Asimov -
Dan Asimov -
Erich Friedman -
Fred Lunnon -
James Buddenhagen -
James Propp -
Marc LeBrun -
Mike Beeler -
Mike Stay -
rcs＠xmission.com -
rkg -
rwg -
Scott Huddleston -
Seb Perez-D -
Simon Plouffe -
Tom Rokicki -
Veit Elser