Summary
Sort cats according to the v / x metric in descending order, where v is the constant speed of the cat and x is the initial shift of the cat at time t = 0. It does not matter how you break the connection. Once an order has been initially set up, it will remain the most efficient order for getting cats as long as it follows; so follow him.
Candidates debunked :
In both cases, the motorcycle speed should be w = 20.
It is assumed that you get cats in order from the fastest to the slowest. Counterexample: Cat # 1 (x, v) = (1, 9) and Cat # 2 (x, v) = (100, 10).
It is assumed that you get cats in order from the closest to the farthest. Counterexample: Cat # 1 (x, v) = (1, 1) and Cat # 2 (x, v) = (2, 100).
Detailed derivation :
Let c (k) refer to the k-th cat that the lady raises, v (k) refers to the speed of this cat and x (k) to the initial displacement of the cat (at time t = 0, which we set when the lady starts her motorcycle originally in pursuit of the first cat).
Total time to get the first cat:
t(1) = 2 * x(1) / (w - v(1))
where w is the constant speed of the motorcycle. Since this expression will be important, we can motivate every part of it:
2 * assumes that the lady must catch the cat, and then spend the same amount of time to return the cat home;x(1) / (w - v(1)) is the time required to reach the cat, i.e. close the distance x(1) by moving w - v(1) faster than cat v(1) .
Time to receive the first two cats:
t(2) = t(1) + 2 * (x(2) + v(2)t(1)) / (w - v(2))
That is, it takes a time equal to the time to get the first cat, plus the time to get the second cat. The additional term v(2)t(1) explains the fact that the second cat moves when the lady receives the first cat; otherwise, this part will be the same.
Reordering this expression, we get:
t(2) = t(1)(1 + 2 * v(2) / (w - v(2))) + 2 * x(2) / (w - v(2))
Define the following derived members:
T(k) = 2 * x(k) / (w - v(k)) s(k) = 2 * v(k) / (w - v(k)) + 1
Now rewrite:
t(1) = T(1) t(2) = s(2)T(1) + T(2)
and continue
t(1) = T(1) t(2) = s(2)T(1) + T(2) t(3) = s(3)s(2)t(1) + s(3)T(2) + T(3) ... t(n) = s(n)...s(2)T(1) + s(n)...s(3)T(2) + ... + T(n)
This last expression gives us the total time to get all cats n :
s(n)...s(2)T(1) + s(n)...s(3)T(2) + ... + T(n)
Now we assume that we have the optimal solution in that cats are selected in the most efficient manner. In order to obtain useful properties about this hypothetical optimal solution, we can use the assumed optimality to conclude that exchange cats create a solution that is not better. Imagine that you are changing cats j and j+1 :
... + s(n)...s(j+1)T(j) + s(n)...s(j+2)T(j+1) + ... <= ... + s(n)...s(j)T(j+1) + s(n)...s(j+2)T(j) + ...
Terms with T(k) for k < j have both s(j) and s(j+1) , and by the commutativity of the multiplication, they are not affected by the swap. Terms containing T(k) for k > j + 1 have neither s(j) nor s(j+1) and therefore cannot be affected by the exchange. Only the terms with T(k) such that the swap affects j <= k <= j + 1 , so we can remove the following terms:
s(n)...s(j+2)s(j+1)T(j) + s(n)...s(j+2)T(j+1) <= s(n)...s(j+2)s(j)T(j+1) + s(n)...s(j+2)T(j)
The partial product s(n)...s(j+2) is common to all other terms and must be positive, so we can remove this similar term by separating both sides of the inequality:
s(j+1)T(j) + T(j+1) <= s(j)T(j+1) + T(j)
Change this as follows:
(s(j+1) - 1)T(j) <= (s(j) - 1)T(j+1)
Finally:
(s(j+1) - 1) / T(j+1) <= (s(j) - 1) / T(j)
Recalling our definitions of s(k) and T(k) , simplify this in terms of v and x :
v(j+1) / x(j+1) <= v(j) / x(j)
That is: if we have an optimal solution, it should be such that the ratio of cat speeds to initial displacements should be in descending order. This is a necessary, but perhaps not enough, condition.
Note that this result is consistent with intuition:
- Get the peace of cats (v = 0)
- Get cats that are not gone (x = 0)
- Cats approach motorcycle speed first (or never)
- Get cats that are really far from the last (x → + inf)
It also gives the correct result for the case of two cats; and in this case, if the ratios of speed to displacement are equal, then it can easily be shown that it doesn't matter in which order you get cats (if they are unequal, you must first get a cat with a higher ratio).
Now - I did not consider the case when cats can have the same ratio. It does not seem immediately obvious to me that the order in which you get cats with the same ratio does not matter.
However, suppose you choose optimally to some point k < n . Now you need to decide which of the two cats with the same ratio to move on. As we already mentioned, for a problem with two cats it’s washing: so I think the answer is that it doesn’t matter which one you choose, as either order between them will go at the same time and " look at the same thing after that. To see that two cats that start with the same ratio keep the same ratio:
v(i) / x(i) = c; X(i) = x(i) + v(i)t = x(i) + x(i)ct = x(i)(1 + ct) v(j) / x(j) = c; X(j) = x(j) + v(j)t = x(j) + x(j)ct = x(j)(1 + ct)
Thus, the ratio changes over time (if you take x as the new initial offset), but two cats that start with the same ratio will keep it. The new ratio will be:
v / x = c; v / X = v / x(1 + ct) = c / (1 + ct)
It is important to note that these relationships do not “overlap” with each other; if you start with a higher or lower ratio, it will change over time, but it will not become higher or lower than the ratios of other cats:
c(i) / (1 + c(i)t) > c(j) / (1 + c(j)t) <=> c(i) + c(i)c(j)t > c(j) + c(i)c(j)t <=> c(i) > c(j)
Based on all these considerations, my best answer is:
Sort cats according to v / x metric in descending order. No matter how you break the connection. Get cats in that order.