Suppose a small country has 15 cities and 70 roads, where each road directly connects precisely 2 cities. What is the largest possible number of cities that are directly connected to every other city?
Take one city that's connected to each other city; that accounts for 14 roads.
Take another city connecting to each other city, accounting for 13 more roads. So far 27 roads.
Take another city connecting to each other city, accounting for 12 more roads. So far 39 roads.
Take another city connecting to each other city, accounting for 11 more roads. So far 50 roads.
Take another city connecting to each other city, accounting for 10 more roads. So far 60 roads.
Take another city connecting to each other city, accounting for 9 more roads. So far 69 roads.
There's only one more road left--not enough to fully connect any remaining city.
So the answer is six.
|
|
Posted by Charlie
on 2019-05-14 11:42:43 |
solution