4

This week's "riddler classic" on $538$ is quite the puzzler (as the riddler classic always is). However, I can usually deduce solutions by researching relevant material or just using what's already up in the 'ol noggin. The question states:

Consider four towns arranged to form the corners of a square, where each side is $10$ miles long. You own a road-building company. The state has offered you $\$28$ million to construct a road system linking all four towns in some way, and it costs you $\$1$ million to build one mile of road. Can you turn a profit if you take the job?

Extra credit: How does your business calculus change if there were five towns arranged as a pentagon? Six as a hexagon? Etc.?

I don't need a solution to the problem (as that's the fun!), just want a jumping off point. Simply was wondering how to classify the problem. I've been trying to find similar problems and whatnot to help me along, but I'm struggling. I considered graph theory right off the bat, but there's no nodes to work with! I've also thought of using Lagrange Multipliers, but I'm not quite sure that's applicable here. Lastly, I even considered using mathematica to basically drop particles on a polygon then apply graph theory to that, but that seems rather over the top.

Any hints would be greatly appreciated.

Community
  • 1
Joseph Eck
  • 649
  • 3
    28 is very suspiciously close to $20\sqrt{2}$, which is the sum of the lengths of the 2 diagonals (which would be a suitable road network except that it costs slightly too much). Perhaps you can cut corners a little bit by drawing diagonal lines that meet not quite in the center, and then draw a vertical line between the two intersection points you get. – Ian Jun 02 '18 at 04:42
  • Indeed that last idea will work, with not very much money to spare. I will leave the details to you. – Ian Jun 02 '18 at 04:46

1 Answers1

5

What should I be researching to solve this problem?

My at-a-glance guess: Steiner minimal trees.

See, e.g., Gilbert and Pollak's (1968) Steiner Minimal Trees (pdf) or Courant and Robbins' (1941) "What is mathematics?" as mentioned in the blog post here.

Side-note: Gilbert-Pollak's $\sqrt{3}/2$ "Steiner ratio conjecture" [at the end of p. 23 above] was believed to have been proved successfully; however, an error was later discovered.

Cf. MO 144081 for more details.

Benjamin Dickman
  • 14,451
  • 1
    Thank you for this! That’s just what I was looking for! – Joseph Eck Jun 02 '18 at 05:09
  • 1
    @JosephEck You're welcome. I had Henry Pollak as a professor for a couple of courses earlier in the decade [in fact, he is still teaching as of Spring 2018... at age 90!] which is how I learned of Steiner trees in the first place. Good luck with your solution submission. – Benjamin Dickman Jun 02 '18 at 05:13
  • 1
    I'm surprised to see that my ad hoc idea "draw diagonals, split the central vertex in two, connect these two vertices with a vertical line, continue pulling those two vertices apart until doing so makes it worse" is actually optimal in this particular case. – Ian Jun 02 '18 at 05:36
  • 1
    @Ian I think I rigged up an exact answer in Desmos (Spoiler? alert): link – Benjamin Dickman Jun 02 '18 at 21:41
  • FWIW: The follow-up Riddler mentions Steiner Minimal Trees as well as the "What is mathematics?" reference above. [The optimal decision accords with my previous comment's pointer to Desmos.] – Benjamin Dickman Jun 09 '18 at 06:08