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] --