Consider a country with 15 cities. For 1 ≤ j ≤ 15, let $x_j$ denote the number of roads that lead out of city j to other cities in the country. Adding up $x_j$ for each city j results in a number that is at least 135. Prove that there is a city that must have at least 10 roads leading out of it.

My current logic is as follows. I am not sure if this is correct.

For n cities and n-1 roads/city you can draw n*(n-1) roads between them for remaining 15 - n cities you can draw (15 - n) * (15 - n - 1) = (15 - n)(14 - n) roads between them.

$n(n-1) + (15-n)(14-n) = 135$

$2n^2 - 30n + 75 = 0$

$n = 3.1699$ OR $n = 11.830$

Remember $n$ is the number of cities, thus $n-1$ is the number of roads and there must be at least one city with 10.830 roads thus there must be one city with at least 10 roads leading out of it.

  • $\begingroup$ There can be 2 or more roads from city A to city B. $\endgroup$ – fleablood Oct 27 '15 at 5:55
  • $\begingroup$ @fleablood i should clarify the invariants of the problem state that there cannot be more than one road from city A going to city B. $\endgroup$ – user2615936 Oct 27 '15 at 6:02
  • $\begingroup$ Ah, that's fine. I was confused by the 1 <= j <= 15. I thought j referred to the number of roads out and not the city itself. $\endgroup$ – fleablood Oct 27 '15 at 6:08

It's simpler than that. But the basic degree sum formula ($\sum deg(Vertex) = 2|Edge|$ ~ $\sum$ roads out of cities = 2 number of roads) states that the sum of all the roads out of the cities must be an even number. So if its at least 135 it must actually be at least 136. 136/15 > 9 so at least one city must have at least 10 roads out of it.

  • $\begingroup$ There's a typo here: The last line should read "$136/\mathbf{15} > 9$ so..." $\endgroup$ – Brian Tung Oct 27 '15 at 17:21
  • $\begingroup$ That sure is a typo! $\endgroup$ – fleablood Oct 27 '15 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.