A combinatorics problem on connecting the citiesby Vineeth T Tags: cities, combinatorics, connecting 

#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: 10,813

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 