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
Physical constant is constant even in strong gravitational fields
Montreal VR headset team turns to crowdfunding for Totem
Researchers study vital 'on/off switches' that control when bacteria turn deadly
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: 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