Suppose a small country has 1 5 cities and 7 0 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 in the country?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
did the same way :D
Suppose there are n cities, call them hub cities, that are connected to every other city. There are then ( 2 n ) roads that connect the hub cities to one another, and every one of these hubs are connected by a road to the remaining 1 5 − n cities. This accounts for ( 2 n ) + n ( 1 5 − n ) roads, and thus
( 2 n ) + n ( 1 5 − n ) ≤ 7 0 ⟹ 2 n ( n − 1 ) + n ( 1 5 − n ) ≤ 7 0
⟹ n 2 − n + 3 0 n − 2 n 2 ≤ 1 4 0 ⟹ n ( 2 9 − n ) ≤ 1 4 0 .
Now as n ≤ 1 5 , we work our way down from 1 5 to find that n = 6 is the largest value that satisfies this inequality, as 6 ∗ ( 2 9 − 6 ) = 1 3 8 . So if we connect 6 cities to every other city and place the remaining 1 4 0 − 1 3 8 = 2 roads between different pairs of the 9 non-hub cities then we have a network that involves 6 hub cities, i.e., the maximum possible value of n = 6 is achievable.
Nice question sir :)
Earlier I was confused sir, that did you mean "The Road Not Taken" by Robert Frost , but then I googled it up to find it's this book that you were referring to.
Log in to reply
Thanks. Yes, I had previously posted a question titled "The Road Not Taken" so I had to think of a different title for this one. I have read "The Road Less Traveled", (and found it quite inspiring), and I thought it would make a good title for this question. :)
Log in to reply
I have read both the poems. :)
Log in to reply
@Prasun Biswas – Actually , the Road Less Traveled is a book , so I guess you are mistaken .
Log in to reply
@A Former Brilliant Member – No, I think there's a poem with the same name (it was in our class 9 English syllabus). But then again, maybe I mixed up the names. I hate literature anyway. :3
Log in to reply
@Prasun Biswas – Yes I remember it , it was indeed the Road Not Taken . Was there a pic of a man on his horse looking at some cabin ?
Log in to reply
@A Former Brilliant Member – I don't remember exactly, but you may be right.
Nicely explained. I used the logical method
Plz do more questions like that
I did as 1 4 n − 2 n ( n − 1 ) ≤ 7 0 , because each city is connected to each other city but we are over counting by 2 n ( n − 1 ) . Yours is easier to think :)
Problem Loading...
Note Loading...
Set Loading...
A rather brute-force solution:
Let the (fully connected) cities that are directly connected to every other city be A, B, C, so on.
Let's count the number of unique roads for each fully connected city:
Unique roads for city A = 14 (because its connected to remaining 14 cities)
Unique roads for city B = 13 (because we have already counted road connecting A to B)
Unique roads for City C = 12
Unique roads for City D = 11
Unique roads for City E = 10
Unique roads for City F = 9
Total Unique roads so far = 69. Hence we can't have another fully connected city because that would require another 8 roads.
Total fully connected cities = A to F = 6.