Decision Support Puzzles for Applied Mathematicians
December 2014 - Electrifying
A new city is being built which will include 20 distinct neighborhoods as shown by the house icons in the map. As part of the planning process, electricity needs to be connected to each of the neighborhoods.
The city has been allocated funds to put in 3 electrical substations to service the electrical needs of the neighborhoods. The substations are represented by the 3 electrical box icons to the right of the map. Because laying electrical line to each neighborhood is expensive, the placement of the substations on the map requires careful consideration.
A neighborhood will be serviced by the nearest electrical substation. A neighborhood may only be connected to one substation. The substations may be placed in any cell (including the same cell as an existing neighborhood). The cost of electrical wiring is $1M per km. Distances are measured using a direct line between cells, which are each 1km apart. For example, the distance between cell A1 and B2 is 1.41km.
Question: What is the minimum cost required to connect all neighborhoods to electricity?
Send your answer to firstname.lastname@example.org by February 15th, 2015. The winner, chosen randomly from correct answers, will receive a $25 Amazon Gift Card.