A combinatorics problem on connecting the cities


by Vineeth T
Tags: cities, combinatorics, connecting
Vineeth T
Vineeth T is offline
#1
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 Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
Rogerio
Rogerio is offline
#2
Dec17-12, 10:49 AM
P: 403
5*15=75 which is not an even number. So it is impossible.
Vineeth T
Vineeth T is offline
#3
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?

mfb
mfb is offline
#4
Dec19-12, 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