Register to reply

A combinatorics problem on connecting the cities

by Vineeth T
Tags: cities, combinatorics, connecting
Share this thread:
Vineeth T
Dec17-12, 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.
Phys.Org News Partner Science news on
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
Dec17-12, 10:49 AM
P: 403
5*15=75 which is not an even number. So it is impossible.
Vineeth T
Dec19-12, 07:38 AM
P: 31
Quote Quote by Rogerio View Post
5*15=75 which is not an even number. So it is impossible.
Hi! Rogerio
Can you explain me clearly why is it impossible?

Dec19-12, 08:16 AM
P: 11,589
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