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)