A combinatorics problem on connecting the cities

Vineeth T

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.

Rogerio

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

Vineeth T

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?

mfb

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.

Similar Threads for: A combinatorics problem on connecting the cities
Thread	Forum	Replies
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

Vineeth T	A combinatorics problem on connecting the cities Tweet 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.

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

mfb Mentor	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.