6.15 Multiple delivery routes The circulation manager of a small newspaper in a town is asked to reorganize the delivery of the newspaper. The travel network is shown in Figure P6.15.

The newspaper is produced at node 2 and must be delivered to all the other nodes. The manager should decide how many people must be hired to distribute the newspaper. In order to maximize service, the longest of all routes should be as short as possible, but in order to minimize costs the total length of the routes of all people delivering the newspapers should be as short as possible too. These two goals are, in general, contradictory! (Explain why.) The circulation manager meets the goals in the following way:

For all reasonable numbers of hired people he computes the routes such that the total length of the routes is minimized and each hired person has a route of nonzero length. He now compares the length of the longest route for the different solutions with different numbers of hired people. He then chooses the number of people N to hire, such that the longest route with N people is less than with N - 1 people, but is equal to the longest route with N + 1 people. What number is N?