7
$\begingroup$

There are 10 cities on this island. For each pair of cities, they may have a bidirectional path.

A trip route is defined as a route which start on a city e.g. $A$, goes to 8 of 9 other cities exactly once (by the paths), and goes back to city $A$. (i.e. a trip route is a cycle of 9 cities/paths.)

What is the minimum number of the paths on this island; so that for each city, there exist a trip route that doesn't visit it?


This puzzle is taken from Indonesia National Science Olympiad in Mathematics 2011.

$\endgroup$
  • $\begingroup$ "goes to 8 of 9 other cities exactly" means from A you should have a connection between one of the cities? or it is at least 8? $\endgroup$ – Oray Feb 22 '18 at 14:14
  • $\begingroup$ If the cities are labeled 1 to 10, then a cycle of 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 1 is an example of a trip route that doesn't visit 4. $\endgroup$ – athin Feb 22 '18 at 14:29
7
$\begingroup$

15

After playing around with it I realized that each city must have at least 3 paths so that if one city goes down there are still 2 paths to enter and leave the city.

Then I tried to construct the cities such that each city ONLY has 3 paths, the minimum required.

Although I am unable to provide a mathematical proof.

Map of cities

$\endgroup$
  • 5
    $\begingroup$ You have a mathematical proof in your answer: there can't be a city with less than 3 roads to it! so you have a minimum number, as you have shown this minimum is doable, you have your demonstration. $\endgroup$ – Untitpoi Feb 22 '18 at 14:11
  • $\begingroup$ This is called graph theory. It's a really interesting part of math. $\endgroup$ – Quintec Feb 22 '18 at 14:14
  • $\begingroup$ "goes to 8 of 9 other cities exactly", $\endgroup$ – Oray Feb 22 '18 at 14:14
  • $\begingroup$ Also, because your graph is vertex-transitive, just showing one 9-city tour shows that any city can be the one left out of the tour. $\endgroup$ – Jaap Scherphuis Feb 22 '18 at 18:35
  • 1
    $\begingroup$ @athin Unless there's only 3 cities, in which case you only need 2 paths :^) $\endgroup$ – HollyLeaves Feb 23 '18 at 13:45

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.