Register to reply 
A combinatorics problem on connecting the cities 
Share this thread: 
#1
Dec1712, 05:21 AM

P: 31

Fifteen cities are planned to be connected in such a way that each city has precisely one road leading to each of five other cities.How many such roads are to be constructed?
This question was asked in a talent test conducted in our school. 


#2
Dec1712, 10:49 AM

P: 403

5*15=75 which is not an even number. So it is impossible.



#3
Dec1912, 07:38 AM

P: 31

Can you explain me clearly why is it impossible? 


#4
Dec1912, 08:16 AM

Mentor
P: 12,113

A combinatorics problem on connecting the cities
Assuming that a road always leads from one city to another city, each city has 5 road ends connected to this city, so we have a total of exactly 75 road ends.
Every road has 2 ends  the total number of road ends has to be even. 75 is not even. 


Register to reply 
Related Discussions  
A Combinatorics Problem  Precalculus Mathematics Homework  1  
Un equal weight connecting rod will creat problem?  Mechanical Engineering  11  
Combinatorics problem  Set Theory, Logic, Probability, Statistics  6  
Having trouble connecting Lorentz transformations with my problem  Introductory Physics Homework  7  
Major problem finding the distance between two cities  Precalculus Mathematics Homework  7 