Bonus puzzler for Bill

Hint

Bill Earl

The problem as stated doesn't give enough detail to explore all possible paths. But it gives enough detail to identify a set of paths that is sufficient to prove the answer.

Question

Alex Y

My reading of the problem is different from real life in one important aspect. I think that the paths have a single level of difficulty, which apply in either direction (while I consider a hike up a 20% grade to be of greater difficulty than a hike down the same path). Is my assumption correct (and material)?

Re: Question

Bill Earl

Excellent question:

From a graph theory perspective, this problem would be characterized as a "weighted graph" with each edge (trail) assigned a weight. The weight would be the same regardless of the direction. If the problem stated any direction-specific difficulty, it would be considered a "weighted directed graph". Any kind of directedness would complicate the solution considerably.

From a hiker's perspective, downhill is not always easier. In particular, when the going gets steep, your legs take more of a pounding on the way down. If you have ever done this with a 50 pound pack or a tired youngster on your shoulders, you will know what I mean.

UNCLE!

Alex Y

I've got to cry "uncle" on this one. I have seen the answer given in the original source, which was for a more general case, but I am lost, and haven't had the persistence to follow it though.

Bill, can you explain how to find such a path, or at least prove its existence?

Re: UNCLE!

Bill Earl

The problem boils down to proving that there is at least one path consisting of 20 trails ordered in increasing difficulty. We don't have enough information to determine what that path is, but we can prove that one exists.

From the problem statement, we know that there are 100 rest stops, 1000 trails, and exactly two rest-stops associated with each trail.

From each of the 100 rest-stops, there exists some path consisting of a sequence of 0 or more trails of increasing difficulty. (The problem statement does not rule out the possibility of a rest stop with no trails - although it would make no difference to the solution). There may be more than one possible path from a rest-stop, but we will choose one exactly one path from each rest stop using the following process:

Start by placing a token representing a virtual hiker at each rest-stop on the map.

Going through the list of 1000 trails in order of increasing difficulty, for each trail in the list, swap places of the the two virtual hiker tokens associated with rest-stops at each end of the trail. Note that each step of this process will move exactly two tokens, and that all steps will begin and end with exactly one token at each rest-stop.

In the end, you will have looked at 1000 trails and made 2 virtual hiker moves per trail. For each virtual hiker, the sequence of moves will have been along a path of increasing level of difficulty (because that is the order we went through the list of trails). Since there are exactly 100 tokens and we made exactly 2000 moves, that means the average number of moves per virtual hiker was 20. That means there must be at least one path with at least 20 moves of monotonically increasing difficulty.

Re: UNCLE!

Alex Y

Thanks. You gave essentially the same demonstration as I saw, but, at least for me, yours was easier to follow. Here is the version I saw:

Solution: We generalise the problem as follows: Let G = (V,E) be a graph

with |V | = n, |E| = m and suppose that e1 < e2 < � � � < em is an arbitrary

ordering of the edges E. Let d = 2m/n be the average degree. There is a trail

f1, f2, . . . , fk such that k >= d and f1 < f2 < � � � < fk.

Proof: Place n walkers, one at each vertex. Then go through the edges of E

one by one and when you come to edge e = (u, v) the current walkers at u, v

change places. Let Pv be the trail that is traversed by the walker originally at

vertex v. Then each Pv follows an increasing sequence of edges. Now

Sum, for v in V, of |Pv| = 2m

and so there exists v such that |Pv| >= 2m/n.

Yours was SO much easier to follow, even before I converted his proper summation notation into text!