Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A combinatorics problem on connecting the cities

  1. Dec 17, 2012 #1
    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.
     
    Last edited: Dec 17, 2012
  2. jcsd
  3. Dec 17, 2012 #2
    5*15=75 which is not an even number. So it is impossible.
     
  4. Dec 19, 2012 #3
    Hi! Rogerio
    Can you explain me clearly why is it impossible?
     
  5. Dec 19, 2012 #4

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for combinatorics problem connecting Date
B Combinatorics problem Nov 29, 2016
I Combinatorics problem on drawing sample with given mean Sep 8, 2016
Inclusion-Exclusion principle problem Sep 15, 2015
Solving a inclusion-exclusion problem Nov 18, 2014
2 problems in combinatorics Sep 24, 2014