The road less traveled

Suppose a small country has 15 15 cities and 70 70 roads, where each road directly connects precisely 2 2 cities. What is the largest possible number of cities that are directly connected to every other city in the country?


The answer is 6.

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.

2 solutions

Pawan Kumar
Feb 20, 2015

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.

did the same way :D

Trung Đặng Đoàn Đức - 6 years, 3 months ago

Suppose there are n n cities, call them hub cities, that are connected to every other city. There are then ( n 2 ) \dbinom{n}{2} roads that connect the hub cities to one another, and every one of these hubs are connected by a road to the remaining 15 n 15 - n cities. This accounts for ( n 2 ) + n ( 15 n ) \dbinom{n}{2} + n(15 - n) roads, and thus

( n 2 ) + n ( 15 n ) 70 n ( n 1 ) 2 + n ( 15 n ) 70 \dbinom{n}{2} + n(15 - n) \le 70 \Longrightarrow \dfrac{n(n - 1)}{2} + n(15 - n) \le 70

n 2 n + 30 n 2 n 2 140 n ( 29 n ) 140. \Longrightarrow n^{2} - n + 30n - 2n^{2} \le 140 \Longrightarrow n(29 - n) \le 140.

Now as n 15 n \le 15 , we work our way down from 15 15 to find that n = 6 n = 6 is the largest value that satisfies this inequality, as 6 ( 29 6 ) = 138. 6*(29 - 6) = 138. So if we connect 6 6 cities to every other city and place the remaining 140 138 = 2 140 - 138 = 2 roads between different pairs of the 9 9 non-hub cities then we have a network that involves 6 6 hub cities, i.e., the maximum possible value of n = 6 \boxed{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.

A Former Brilliant Member - 6 years, 3 months ago

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. :)

Brian Charlesworth - 6 years, 3 months ago

Log in to reply

I have read both the poems. :)

Prasun Biswas - 6 years, 3 months ago

Log in to reply

@Prasun Biswas Actually , the Road Less Traveled is a book , so I guess you are mistaken .

A Former Brilliant Member - 6 years, 3 months ago

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

Prasun Biswas - 6 years, 3 months ago

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 ?

A Former Brilliant Member - 6 years, 3 months ago

Log in to reply

@A Former Brilliant Member I don't remember exactly, but you may be right.

Prasun Biswas - 6 years, 3 months ago

Nicely explained. I used the logical method

Figel Ilham - 6 years, 3 months ago

Plz do more questions like that

Mr Yovan - 4 years, 10 months ago

I did as 14 n n ( n 1 ) 2 70 14n - \frac{n(n - 1)}{2} \le 70 , because each city is connected to each other city but we are over counting by n ( n 1 ) 2 \frac{n(n - 1)}{2} . Yours is easier to think :)

Abhisek Panigrahi - 3 years, 7 months ago

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...