26
$\begingroup$

A province has 10 cities (arranged in a circular manner). Every pair of cities is directly connected by a straight highway, and each has its own unique number: Highway 1, Highway 2, Highway 3, ..., Highway 45. Below is an example of one such numbering, but the governor Tonald Drump loves rearranging the numbers of the highways, so the numbers are periodically changing.

enter image description here

Note that you cannot exit these highways partway between cities, and instead must proceed all the way down the highway to the destination city.

An obscure religion requires its members to go on a pilgrimage to this province. For reasons lost to time, each pilgrim must, after arriving at one of these cities

  • only travel via these highways,
  • travel on at least nine of the highways during the pilgrimage, and
  • only travel on a highway if it has a strictly larger number than the one they just walked down.

Note that they need not visit every city, repeating cities is acceptable, and pilgrims can choose their starting point.

Tonald Drump, who has no love of this religion (and has even suggested building a wall to keep them out), has made it clear he'd like to rearrange the numbers of the highway so that the pilgrim's task is impossible.

Show that no matter how Tonald Drump numbers these highways, the pilgrims can always complete their journey.

$\endgroup$
  • $\begingroup$ So trump isn't allowed to rename them mid-pilgrimage? $\endgroup$ – DrunkWolf Jan 16 '16 at 16:34
  • 1
    $\begingroup$ @DrunkWolf you mean 'Drump' :) $\endgroup$ – Beastly Gerbil Jan 16 '16 at 16:38
  • $\begingroup$ @DrunkWolf: Correct, the numbers stay fixed during any pilgrimage. $\endgroup$ – Tyler Seacrest Jan 16 '16 at 17:01
  • $\begingroup$ Trying with n=4 first... $\endgroup$ – Joe Z. Jan 16 '16 at 17:35
  • 1
    $\begingroup$ @Oliphaunt No, I didn't really know, I simply wrote a program which enumerates all possible numberings (which is reasonable for n<=5) and examined the permutations with the fewest possible paths (4 for n=4, 8 for n=5). $\endgroup$ – Matthias Urlichs Feb 6 '16 at 8:42
11
$\begingroup$

We can show that a pilgrimage is always possible by employing the pigeonhole principle. Let there be 10 bins, one for each city, and iterate over the highways in order. In iteration $i$, each bin will contain the longest trail ending in that city using only highways up to and including $i$. (If there is more than one such trail, pick an arbitrary one.) Initially, in iteration 0, each bin contains only the city itself, for a trail of length 0.

Claim: During each iteration, the sum of the trail lengths over all bins increases by at least 2.

Proof:

Assume that during iteration $i$, we add highway $X-Y$ and consider the longest trails ending in cities $X$ and $Y$ after iteration $i-1$. We consider two cases:

(1) Both trails had the same length $n$. In this case, we can simply append highway $X-Y$ to both trails for a new longest trail, so each will now have length $n+1$. The sum of lengths increases by 2 and the claim holds.

(2) The lengths of the trails were unequal; without loss of generality assume that trail $t_1$ ending in city $X$ had length $n$ and trail $t_2$ ending in $Y$ had length $m \leq n-1$. In this case, after adding highway $X-Y$, $t_1$ is still the (possibly joint) longest trail ending in city $X$; however, the longest trail ending in city $Y$ is now $t_1$ with highway $X-Y$ appended, for a length of $n+1 \geq m+2$. Again the claim holds.

This means that after all 45 highways have been added, the sum over all 10 bins is at least 90. The pigeonhole principle tells us that at least one trail must have length 9 and fulfils the requirements for a proper pilgrimage. In fact this already holds for 41 highways, so even if Drump throws up four roadblocks he won't be successful.

Running through the example presented in the puzzle, with cities named a through j in clockwise fashion starting from the topmost city, here's the situation after iterating over the first five highways (highway 05, just added, caused the sum to increase by 3):

a(l=1) : e-01-a
b(l=0) : b
c(l=1) : j-03-c
d(l=0) : d
e(l=1) : a-01-e
f(l=3) : e-01-a-02-i-05-f
g(l=0) : g
h(l=2) : j-03-c-04-h
i(l=2) : e-01-a-02-i
j(l=1) : c-03-j
sum = 11 (+3)

And here's the eventual list of trails. All of them start by walking the same seven highways e-01-a-02-i-08-e-10-h-11-f-14-d-15-c, abbreviated as e-...-c below. As you see, in this example highway network, die-hard pilgrims could increase the length of their pilgrimage by more than half if they wanted.

a(l=12): e-...-c-19-f-26-g-29-j-35-d-44-a
b(l=14): e-...-c-19-f-26-g-29-j-32-a-41-c-42-e-43-b
c(l=12): e-...-c-19-f-26-g-29-j-32-a-41-c
d(l=12): e-...-c-19-f-26-g-29-j-32-a-44-d
e(l=14): e-...-c-19-f-26-g-29-j-32-a-34-f-39-b-43-e
f(l=12): e-...-c-19-f-26-g-29-j-32-a-34-f
g(l=12): e-...-c-19-f-26-g-29-j-32-a-38-g
h(l=14): e-...-c-19-f-26-g-29-j-32-a-34-f-40-j-45-h
i(l=9) : e-...-c-23-g-25-i
j(l=13): e-...-c-19-f-26-g-29-j-32-a-34-f-40-j
sum = 124 (+5)

At first I tried to construct the example by hand, but it turned out to be easier and less error-prone to write a simple program. The hand-constructed example up to highway 05 then served nicely to validate it. Here's the Python program if you want to experiment further:

example = [
    'ae', 'ai', 'cj', 'ch', 'fi', 'dg', 'eg', 'ei', 'bj',
    'eh', 'fh', 'gh', 'di', 'df', 'cd', 'ij', 'ah', 'bg',
    'cf', 'de', 'bi', 'ab', 'cg', 'hi', 'gi', 'fg', 'ej',
    'ef', 'gj', 'bd', 'bc', 'aj', 'dh', 'af', 'dj', 'ci',
    'bh', 'ag', 'bf', 'fj', 'ac', 'ce', 'be', 'ad', 'hj',
]

trails = dict()
for v in 'abcdefghij': trails[v] = v

def output(last):
    sum=0
    for v in 'abcdefghij':
        t = trails[v]
        l = (len(t)-1)/5
        sum += l
        print '%s(l=%d)%s: %s' % (
                v, l, '' if l>9 else ' ', t)
    print 'sum = %d (+%d)\n' % (sum, sum-last)
    return sum

sum = output(0)

for i in range(len(example)):
    v,w = tuple(example[i])
    t1,t2 = trails[v], trails[w]
    t1 += '-%02d-%s' % (i+1, w)
    t2 += '-%02d-%s' % (i+1, v)
    if len(t1) > len(trails[w]):
        trails[w] = t1
    if len(t2) > len(trails[v]):
        trails[v] = t2
    sum = output(sum)
$\endgroup$
10
$\begingroup$

Here's a stronger statement, with a quicker proof. Given any graph (not necessarily complete or even connected) and any ordering of its edges, there's an increasing walk of length at least the average degree of the graph's vertices. Proof: Put a pedestrian on every vertex; at time k, let the pedestrians at either end of the kth edge change places. When everyone's done walking, each pedestrian will have taken an increasing walk; if there are n vertices and m edges, there will have been n walks of total length 2m, thus average length 2m/n = average degree.

$\endgroup$
  • 2
    $\begingroup$ This is a fantastic answer! Welcome to Puzzling - I hope to see you around here more! c: $\endgroup$ – Deusovi Feb 14 '16 at 21:03
3
$\begingroup$

The statement is:

given a fully connected graph on n nodes where each edge has a unique weight it is possible to find a path of length n-1 whose edge weight is strictly increasing with each edge

By induction:

The case for 3 nodes is obvious (take road 1 to road 2, no way can Drump stop those pilgrims!)

Given that its possible to find our desired path in any graph of N-1 nodes, we turn to the case of N nodes. (We look at N = 6 because its convenient to draw). Grab any old 5 (N-1) nodes, there is an increasing path of length 4 (N-2) in them, consider how that 6th (N-th) node is connected though:

enter image description here

We draw arrows to indicate possible directions of travel along each edge which would create an increasing path which starts along path 1-2-3-.... Note that we must draw edge 1-6 as "up" because if it were "down" we would create path 6-1-2-3-4-5 and be done.

Given this, edge 2-6 must be "up", else we could create path 1-6-2-3-4-5 and be done.

Given this, edge 3-6 must be "up", else we could create path 1-2-6-3-4-5 and be done.

...

If we continue in this way edge 5-6 will be up, but then path 1-2-3-4-5-6 solves our problem!

$\endgroup$
  • $\begingroup$ Sorry, this doesn't work. You oversimplify the problem by representing the highway numbers simply as arrows. To see why, in your inductive step for example let the highways connecting to city 6 increase in value from left to right, with values higher than the highways in the path except for the rightmost two, which are set lower than any highways in your path. Now the longest path through city 6 has length 2. Remember, Drump can definitely number highways so the pilgrims must avoid some specific city. Any proof must allow for construction of a path with repeating cities; your proof doesn't. $\endgroup$ – Oliphaunt Jan 25 '16 at 21:50
  • $\begingroup$ Put differently, if your proof were correct then there would always be a path visiting all cities. We know that's not the case. $\endgroup$ – Oliphaunt Jan 25 '16 at 21:52
  • $\begingroup$ I have to think on your criticism more. I don't think that cycles exist (each path is strictly greater than all those previous). One cannot revisit a city. $\endgroup$ – eretmochelys Jan 25 '16 at 22:16
  • $\begingroup$ nope, spoke too soon. cycles can exist. :) $\endgroup$ – eretmochelys Jan 25 '16 at 22:18
  • 1
    $\begingroup$ This is a very nice proof that every tournament contains a Hamiltonian path. $\endgroup$ – Tyler Seacrest Jan 26 '16 at 6:47

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.