# A combinatorics problem on connecting the cities

by Vineeth T
Tags: cities, combinatorics, connecting
 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.
 P: 403 5*15=75 which is not an even number. So it is impossible.
P: 31
 Quote by Rogerio 5*15=75 which is not an even number. So it is impossible.
Hi! Rogerio
Can you explain me clearly why is it impossible?

Mentor
P: 9,636

## 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.

 Related Discussions Precalculus Mathematics Homework 1 Mechanical Engineering 11 Set Theory, Logic, Probability, Statistics 6 Introductory Physics Homework 7 Precalculus Mathematics Homework 7