I have returned!

Probability Level 4

A king rules over $2017$ cities, and there are $n$ bridges connecting some of the cities together (a bridge can only be built between two cities, connecting both of them.) One day, he holds a conversation with the royal architect.

King: Our subjects have complained that we are not putting their tax money to good use. Get two cities which you would like to connect, and build a bridge between them.

Architect: But building another bridge would be wasted funds, your majesty. As you can see, if another bridge were to be built between any two cities of your choice, it would be redundant, as there would be another series of bridges which would connect the two cities on which the bridge will be built between. Since this has not yet happened before, our citizens would surely dislike this idea.

Find the minimum value of $n$ for which this dilemma can hold.

The answer is 2016.

2 solutions

Kushal Bose
May 5, 2017

Consider the cities as vertices and bridges as edges between them.So, there are $2017$ vertices and $n$ edges.The present number of bridges already connects every pair if cities not necessarily direct but through series of bridges.If any other bridges will be built then it will be redundant.

This is possible if a graph is a tree where $n$ vertices requires $n-1$ edges to be minimally connected .So, here $2017-1=2016$ bridges are there.

Manuel Kahayon
May 4, 2017

Since none of the $n$ bridges built so far have been redundant, we can see that every bridge must have been built to connect two cities which have not yet been connected before. Assuming that we have $n \leq 2015$ , we can see that there must have been at least two cities for which a bridge could have been built between without redundancy (since all bridge-building efforts were not redundant, and it takes at least $2016$ bridges to fully connect the kingdom.) So, we must have $n \geq 2016$ . Now, if $n = 2016$ , we can see that the entire kingdom must have been connected (Since no bridges are redundant, and 2016 bridges will suffice in connecting the entire kingdom). This means that placing a bridge anywhere would be redundant, since the entire kingdom is already connected. As such, we can see that the answer is $\boxed{2016}$ .

Since bridges are normally built over a natural (or constructed) barriers, it would look much better, if the problem would be about roads instead of bridges. Otherwise, one could argue that if there is only one river (and no other relevant barriers) in the kingdom and each city is either on one side of the bridge or the other (no cities on river islands), then the correct answer should be 1.

Also, rational citizens might be happy to have redundant bridges if there is a significantly shorter route through them. Redundancy can also be useful if one of the bridges/roads collapse or has to be closed for whatever reason (this would isolate two groups of cities from each other without redundancy, which is not the sort of a risk a wise king should take).

Zee Ell - 4 years, 1 month ago

I have returned!

The answer is 2016.

2 solutions

0 pending reports