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?
Mountain trails
Moderators: jestingrabbit, Moderators General, Prelates
Mountain trails
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
Re: Mountain trails
Nitpick: I think you need to specify that no two trails connect the same two lodges.

 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.
Who is online
Users browsing this forum: No registered users and 6 guests