## Mountain trails

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

wraith
Posts: 102
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

### Mountain trails

In a mountain there are 100 lodges and 1000 trails. Each trail connects two lodges. Each trail has a difficulty and there are no two trails with the same difficulty.

A tourist wants to make a 20 day trip. He wants to start at some lodge, walk along some trail and stay at the lodge at the end, then walk along some other trail the next day, stay at the lodge at the other end, and so forth. The key part is that he wants each trail for the day to have a bigger difficulty than the one from the previous day.

He can choose the starting lodge.

Is this always possible or does there exist a configuration of 100 lodges and 1000 trails where tracking 20 trails with increasing difficulty is not possible?
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

sfwc
Posts: 225
Joined: Tue Mar 29, 2011 1:41 pm UTC

### Re: Mountain trails

Solution:
Spoiler:
This is always possible.

Imagine a hiker, call her Helen, who hikes according to the following policy: first she follows the easiest trail from her starting lodge. On each successive day she follows the easiest trail from the lodge she just arrived at which is harder than the trail she just arrived on, as long as there is such a trail. Since the trails are getting harder and harder she must eventually arrive at a lodge from which there are no harder trails, and then she stops. Let's imagine that Helen publishes a book, `Helen's giant book of hiking routes', listing all the routes that she could follow when hiking according to this policy. Since there are 100 possible starting lodges, the book contains 100 routes.

The key fact we need is that every trail appears on two different routes in Helen's book, once in each direction. To see this, consider another Hiker, let's call him Tim, who hikes according to the opposite policy to Helen: on any given day he follows the hardest trail from the lodge he just arrived at which is easier than the trail he just arrived on, as long as there is such a trail. Tim is also a little freer than Helen, in that he doesn't put any restrictions on the trail to be followed on the first day of his hike. Now consider a given trail, and a given direction. Suppose Tim begins by following this trail in the opposite direction. Since the trails he follows are getting easier and easier, eventually he must stop at some lodge, arriving along the easiest trail to that lodge. If Helen were to start at that lodge, she would simply retrace Tim's steps in the opposite direction, eventually hiking the given trail in the given direction. So there is a route in Helen's book where that trail is used in that direction.

This means that the total length of all the routes in Helen's book is at least twice the number of trails, that is, at least 2000. Since there are only 100 routes, one of them must have length at least 20. What's more, the trails along that route are increasing in difficulty. So all the tourist has to do is to buy Helen's book, look up the longest route, and follow the first 20 trails of that route.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

### Re: Mountain trails

Nitpick: I think you need to specify that no two trails connect the same two lodges.

curiosityspoon
Posts: 36
Joined: Wed Sep 24, 2014 5:01 pm UTC

### Re: Mountain trails

Even if you paired up the lodges into 50 isolated sections, connecting each pair within a section with 19 trails only gets you to 950. The 951st trail is therefore pigeonholed into forcing at least two lodges to have 20 connections, at which point this analysis works just as well no matter how many of those trails are redundant routes.