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.

Improve this question
$\endgroup$
2
  • $\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, 2018 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, 2018 at 14:29

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
7
  • 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, 2018 at 14:11
  • $\begingroup$ This is called graph theory. It's a really interesting part of math. $\endgroup$
    – Quintec
    Feb 22, 2018 at 14:14
  • $\begingroup$ "goes to 8 of 9 other cities exactly", $\endgroup$
    – Oray
    Feb 22, 2018 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, 2018 at 18:35
  • 1
    $\begingroup$ @athin Unless there's only 3 cities, in which case you only need 2 paths :^) $\endgroup$
    – HollyLeaves
    Feb 23, 2018 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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