A woman watches her cats leave one by one with different speeds in different directions. She took a motorcycle with one extra seat and follows the cats and picks up one cat at a time and brings them back home. Each cat moves with constant individual speed $V_i$ and left home at time $T_i$. In which order the woman should bring the cats back in order to minimize the time?

I am trying to solve this problem but do not know how to begin.


I would suggest considering simple example with two cats first. Suppose the women is deciding which cat to go after first. Currently, both cats have already left and are $D_{1}$ and $D_{2}$ far away. Suppose the women decided to go after cat $1$ first and then after $2$. What time she needs to be done? (Assume the women's speed is $V_{0}$ and is larger than any of the cats.)

To catch up with the first cat she needs $t_{1}$ that solves $t_{1}V_{0}=D_{1}+t_{1}V_{1}$, or, equivalently, $t_{1}=\frac{D_{1}}{V_{0}-V_{1}}$. By $2t_{1}$ she is back home with the first cat at which point the second cat is $D_{2}+2t_{1}V_{2}$ far away. To catch up with the second cat she needs $t_{2}$ that solves $t_{2}V_{0}=D_{2}+2t_{1}V_{2}+t_{2}V_{2}$, or, equivalently, $t_{2}=\frac{D_{2}+2t_{1}V_{2}}{V_{0}-V_{2}}$. Hence the entire operation takes $2(t_{1}+t_{2})$.

Substituting in the model parameters, the length of the operation is $$2\frac{D_{2}(V_0-V_1)+D_{1}(V_0+V_2)}{(V_0-V_1)(V_0-V_2)}=2\frac{V_{0}(D_{1}+D_{2})+D_{1}V_{2}-D_{2}V_{1}}{(V_0-V_1)(V_0-V_2)}$$ Similarly, if the women chooses the other order, the operation takes $$2\frac{D_{1}(V_0-V_2)+D_{2}(V_0+V_1)}{(V_0-V_1)(V_0-V_2)}=2\frac{V_{0}(D_{1}+D_{2})+D_{2}V_{1}-D_{1}V_{2}}{(V_0-V_1)(V_0-V_2)}$$

Therefore, the $(1,2)$ order is optimal if $\frac{D_{1}}{V_{1}}>\frac{D_{2}}{V_{2}}$. My conjecture is that the general solution goes after the cats in the decreasing order of $\frac{D_{i}}{V_{i}}$, which, note, equals $\frac{tV_{i}}{V_{i}}=t$ at time $t$ for all the cats if all the cats left at the same time. In other words, what I am conjecturing is that if all the cats left at the same time, the order does not matter. In fact (further supportive evidence, not a proof), Mathematica thinks so as well for $5$ casts:

t1 = d1/(v0 - v1);
t2 = (d2 + 2*t1*v2)/(v0 - v2);
t3 = (d3 + 2*(t1 + t2)v3)/(v0 - v3);
t4 = (d4 + 2(t1 + t2 + t3)v4)/(v0 - v4);
t5 = (d5 + 2(t1 + t2 + t3 + t4)v5)/(v0 - v5);


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.