This note arose from comments on the problem: The King needs your help
An ambitious king plans to build several new cities in the wilderness, connected by a network of roads. He 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. The project is considered viable as long as the tax revenues exceed the cost, regardless of the (positive) populations of the various cities.
- If the road network was a loop, what can we say about the potential revenue?
- If the road network was a complete graph, what can we say about the potential revenue?
- If the road network was a tree, what can we say about the potential revenue?
For further investigations
- What kind of road networks could we submit, such that any population size could be supported (revenue neutral)?
- What kind of road networks could we submit, such that any non-zero population size would result in a surplus (revenue generating)?
Given any road network, how would you determine if there is a potential population size that would result in a deficit?
Given a fixed population size and road network, how would you distribute them to generate the king the most amount of money? The least amount of money?