A tale of (not so) many cities

The Queen plans to build a number of new cities in the wilderness, connected by a network of roads. She expects the annual tax revenues from each city to be numerically equal to the square of the population. Road maintenance will be expensive, though. The annual cost for each road is expected to be numerically equal to the product of the populations of the two cities that road connects. To keep the costs for road maintenance down, the Queen decrees that there should be only one way to get from any city to any other, and not more than three roads should connect to any given city (the attached design would be acceptable, for example).

Unfortunately, Parliament is responsible for deciding which roads will be built (subject to the two Queen's decrees) and how many people live in each city, but has no concern for attempting to stay financially solvent (meaning tax revenue \( \geq \) road maintenance). Regardless of what Parliament decides, what is the largest number of cities that the Queen can build without risking to lose money?

Inspiration

×

Problem Loading...

Note Loading...

Set Loading...