I'm not sure of a deep connection; from what I gather, it is merely the case that the locker puzzle and problem 6 have a common subproblem, which is: prove that "traversing through boxes" produces a cycle, i.e., leads us to visit a node we have already visited. In the locker puzzle, there is an extra restriction that this cycle include the starting node. This restriction holds because the locker puzzle involves a permutation, while problem 6 does not necessarily involve a permutation.
Unless I'm missing something, problems 6a and 6b can be solved simultaneously using the "traverse through boxes" technique starting at array index 1, despite the comment that "Part (b) seems to be a lot harder than part (a), and it apparently requires entirely different techniques". Since the hedge words "seems" and "apparently" were used, we can't say that the comment is false, but nonetheless, I believe it would be false without those hedge words. The key idea is that, as explained in the PDF on the locker puzzle, "player $ B_i $ never opens a locker (other than locker i) without first finding its number, so each time he opens a new locker he must find either his own number or the number of another unopened locker". The same basic reasoning applies to problem 6, with just slight modifications.
Problem 6 can be made to look a little more like the locker puzzle by taking a[1] out of the picture. We can consider b = {a[2], ... , a[n]} as the "real" array with m = n - 1 elements, and the value a[1] as the index of the start node. We can further relabel {2, ... , n} as {1, ... , m} if desired.
All we care about is finding a cycle, that is, coming across a value that is an index we have already visited. This is equivalent to finding a duplicate in array a, since the indices we visited are precisely array values in a. We can fulfill the time and memory requirements using a boolean array of size m. The boolean array allows us to see if we have visited an index yet, and of course has constant memory and is fast. (Correction: the boolean array would have linear memory, not constant. Evidently there is a better way to solve this.) We are guaranteed not to visit any array index twice, so the algorithm has linear time. If we didn't think of a boolean array, we might be tempted to use some sort of a list structure with fast insert and find, but a boolean array is faster.
To tie the problems together further, we can interpret the data as a directed graph where each vertex has outdegree 1. In the locker puzzle, the indegree for each vertex is also 1, but problem 6 has no such restriction.
The outdegree being 1 guarantees that we can traverse from one vertex to another without any ambiguity. Beyond that, we need to guarantee a cycle will occur regardless of where we start.
A permutation is partitioned into cycles, so this allows us to conclude for the locker puzzle that we will find our cycle precisely when we get back to the starting node. For problem 6, we are guaranteed to find some cycle, because otherwise we would have to go on endlessly, but the array is finite, so that is absurd.
Maybe my answer should be made more rigorous, but I hope it is at least satisfactory and accurate. If not, let me know, and I'll try to fix it. I admit that after looking at this problem for an extended period of time, my mind is getting a bit foggy..
EDIT: Oh I think I figured out how to solve 6b with constant memory. You can follow n - 1 links, thus covering n (not necessarily distinct) array indices of a, and by this time you are guaranteed to be in the middle of a cycle. Note your current array index. Then go around until you see that index again, which will give you the period of the cycle. Then using this you can find the "entry node" of the cycle, which will be your duplicate. (Use modular arithmetic.) I haven't worked it out in detail but I believe that's an accurate sketch.
And of course there is no paradox. (As mentioned by Ron Gordon above, The same problem/same angle is discussed on: math.stackexchange.com/questions/346384/)
Solution 3 - above - is no solution at all. It just sums the distances of the trains at the start of each leg, but that is not the distance flown by the bird on that leg: that is given by (obviously) the bird's velocity times the leg duration. Whoops. The fixed solution is below.
Solution 1 - Easy:
The trains will collide in $T_t=\frac{D_0}{V_1+V_2}$. Hence $D_b=V_b\cdot\frac{D_0}{V_1+V_2}=120\cdot\frac{100}{50}=240$
**Hard Solution **
On the first leg, the ** trains are separated by** the distance $D_0$, which the birds covers in time $T_0=\frac{D_0}{V_b+V_2}$.
The distance flown by the bird is $S_0=V_B\cdot\frac{D_0}{V_b+V_2}$
On the second leg, distance between trains, duration and distance covered by the bird amount to:
$D_1 = D_0-T_0 \cdot (V_1+V_2) = D_0 \cdot \frac{V_b-V_1}{V_b+V_2};$
$T_1=D_0 \cdot \frac{V_1-V_b}{V_1+V_b}*(V_2+V_b))=T_0 \cdot \frac{V_b-V_1}{V_b+V_1};$
$S_1=V_b \cdot T_1$
On the third leg, a recurrence emerges:
$D_2 = D_0 \cdot \frac{(V_1-V_b)\cdot(V_2-V_b)}{(V_1+V_b)\cdot(V_2+V_b)} ;$
$T_2 = T_0 \cdot \frac{(V_1-V_b)\cdot(V_2-V_b)}{(V_1+V_b)\cdot(V_2+V_b)}; $
$S_2=V_b \cdot T_1$
The same recurrence is found to hold between $D_3$ and $D_1$, $T_3$ and $T_1$, $S_3$ and $S_1$.
If we set:
$$R=\frac{(V_1-V_b)\cdot(V_2-V_b)}{(V_1+V_b)\cdot(V_2+V_b)}$$
We see that both the total duration and the total distance traveled by the bird can be computed summing a
geometrical series with coefficient $R$ and respective first terms $(T_0+T_1)$ and $(S_0+S_1)$. $R< 1$ holds, so
convergence is assured.
Therefore we have:
Solution 2:
$$T_t= \sum (T_0+T_1)R^n = \frac{T_0+T_1}{1-R} = \frac{D_0}{V_1+V_2}; $$
$$S_b= \sum (S_0+S_1)R^n = V_b\cdot T_t = V_b\cdot\frac{D_0}{V_1+V_2}$$
This matches solution (1) as it should.
Best Answer
Forget to begin with that we have to find a path, but simply try covering the $9$ points by four infinte straight lines.
Call a line covering $n$ points an $n$-line. Since four lines covering only $2$ points each can never cover $9$ points a solution has at least one $3$-line in it. When identifying rotations and reflections we have exactly three distinct types of $3$-lines:
No parallel $3$-lines
It is not possible to have a solution involving parallel $3$-lines. For instance if we have the following situation:
When the two blue $3$-lines shown above have been placed we have to cover the remaining three points by two lines. So at least one line must cover more than one point which implies that the dashed grey line has to be added. But three parallel lines are clearly impossible, since it takes two additional linear moves to visit and travel along all three, but we only have one line left!
Ruling out type 3
With the above we can rule out type 3 being a part of any solution: We cannot have any line parallel to the initial $3$-line by the above argument. This actually means that each of the remaining three lines has to cover exactly $2$ of the remaining $6$ points each. Also we can only have one line orthogonal to the $3$-line for otherwise we would again have parallel $3$-lines (in the orthogonal direction).
So we have to have two lines passing through $2$ of the remaining $6$ points each that are not parallel nor orthogonal to the initial $3$-line of type 3. When symmetries are considered, this gives essentially two setups to consider. The first one is:
which clearly does not hold a solution since the lines only intersect at one point so it takes far more than four linear moves to travel since you would have to return to this intersection time and again in any path traversing parts of all of these lines. The other setup to consider is:
One way of seing why the above holds no solution is, that some of the lines are only intersected in ways having some of their points lying to both sides of the point of intersection. This makes it impossible to go through all points on any of these without visiting that line twice or reversing direction at some point.
Ruling out exclusive type 1 or 2
If we start from type 1 and do not allow type 2 and already know that type 3 must be ruled out and that no line parallel to the initial $3$-line is allowed, we see that this means that a line that passes the center point of the $9$ point pattern can pass no other point it the pattern as that would lead to one of the situations just mentioned. But with a line that only passes through the center the remaining two lines must covers $5$ points, so one of the lines must cover the $3$ points that are parallel to the initial $3$-line which again leads to a paralel $3$-lines contradiction.
If we start from type 2 and do not allow the other two types, there is essentially only one setup not already covered to consider:
which is another setup having three parallel lines. By previous arguments three distinct parallel lines can never be part of any solution.
The unique solution (type 1 + type 2)
By inclusion-exclusion any solution must involve type 1 and type 2 at the same time. So the situation looks like this to begin with:
and since we already know that we are not allowed to add a line parallel to the $3$-line of type 1 there are only two ways to complete the above setup. One way is like this:
and we see how the $3$-line of type 1 is the only line connecting to the other three lines to one side of their points. The other three lines divide each other in parts having points on each side. So all three other lines must be connected to the $3$-line of type 1 in a given solution. This is impossible since each line can only be connected to two other lines in a path that does not travel along any line twice.
So finally this leaves us with the well known solution as essentially the only possibility when considering rotations and reflections.