19
$\begingroup$

Two thieves (Rod and Lia) carry out a big heist and steal 16 gold bars. They get away in their car when they run into a bad accident and the car is completely wrecked. Luckily they survive with their loot intact.

They are at point A and must go to point B which is 1 mile away. At B is a small train station where the train will arrive at 6:10 AM exactly. They must catch this train as the next train comes the following day. They can start from point A at 12 AM midnight. So they have 6 hours and 10 minutes to take as many bars as they can.

• Rod can carry 1 bar at 2 mph but he can also carry 2 bars at 1 mph. Without bars he can go 3 mph.

• Lia can carry only 1 bar at 1.5 mph. She cannot carry 2 bars. Without bars she can go at 2 mph.

Assuming they can walk non-stop and do not use any other tools/method to carry those bars, how can they maximize the number of bars before they board the train? How many bars can they take? Can they take all 16 bars to B before 6:10 AM? What is the optimal strategy? Please also assume that they can safely leave the bars at A or B or in between without any risk of stealing.

enter image description here

Please answer all questions with explanation. No partial answers and no programming please.

$\endgroup$
2
  • 7
    $\begingroup$ Interesting problem! Rod is the GPU, and Lia is the CPU, and we have to parallelize computations between the two! $\endgroup$
    – Stef
    Sep 13 at 15:06
  • $\begingroup$ Can they Bury the gold bars and pick them up later? seems like the most economical soluiton. $\endgroup$
    – tuskiomi
    Sep 15 at 14:34
9
$\begingroup$

Rod can transport 2 bars the distance in an hour if he takes two at a time. After each pair, he uses 1/3 hr to go back. So he can do that 3 times in 4 hours and is back at the starting point, where he can take another pair. After 5 hours he is at B with 8 bars. He can go back (20 min), get one more bar and hot-foot it (30 min) back to B at 5 hrs 50 minutes with 9 bars.

Lisa needs 2/3 hr (40 min) to carry 1 bar and 1/2 hr (30 min) to come back for a total of 1 hr 10 min. After 4 hr 40 min, she would be back at the start having taken 4 bars. She can then bring her 5th bar arriving at 5 hr 20 minutes.

This approach brings 14 bars and leaves them 20 minutes before the train arrives.

It's tempting to try to use Lisa's spare 50 minutes and Rod's spare 20 minutes to bring another bar. But Lisa can't get back to A and then to B even empty handed in that time.

If at the start, Lisa carried 1 bar for 25 minutes, it would be 25/40ths or 5/8 mile between A and B. Walking empty handed back to A would take her 5/8th of her usual 30 minutes, almost 19 minutes. She then does as above for 5 hr 20 min, finishing with 6 minutes to spare. At the end, Rod needs (3/8)(1/3) = 1/8th hr (7.5 min) to go back the 3/8 mile, and (3/8)(1/2) = 3/16th hr = a little over 11 min to bring it back. He has time to do that.

This lets them bring a 15th bar and catch the train with less than 5 minutes to spare.

$\endgroup$
0
17
$\begingroup$

It is not possible to move all 16 bars.

Consider the total distance that each person moves, in each direction, carrying each possible number of bars. For example $R_2^+$ is the total distance that Rod moves forward while carrying 2 bars. We can set up a system of equations. Both Rod and Lia must move a net distance of $1$ mile forwards: $$ R_0^+ - R_0^- + R_1^+ - R_1^- + R_2^+ - R_2^- = 1 \\ L_0^+ - L_0^- + L_1^+ - L_1^- = 1 $$ Both of them must spend less than $370$ minutes moving (note we have taken the reciprocals of their speeds in minutes per mile): $$ 20(R_0^+ + R_0^-) + 30(R_1^+ + R_1^-) + 60(R_2^+ + R_2^-) \le 370 \\ 30(L_0^+ + L_0^-) + 40(L_1^+ + L_1^-) \le 370 $$ Finally, the total net distance moved by all the bars must be $16$ miles forwards: $$ R_1^+ - R_1^- + 2(R_2^+ - R_2^-) + L_1^+ - L_1^- = 16 $$ And of course each distance must be nonnegative.

Next (thanks to RobPratt) we multiply these equations by $\frac{1}{2}$, $\frac{3}{7}$, $\frac{1}{40}$, $\frac{1}{70}$, and $-1$ respectively, and sum them, yielding:

$$ \phantom{+}\left(\dfrac{1}{2}+\dfrac{20}{40}\phantom{-0}\right)R_0^+ + \left(-\dfrac{1}{2}+\dfrac{20}{40}\phantom{-(-0)}\right)R_0^- \\ + \left(\dfrac{1}{2}+\dfrac{30}{40}-1\right)R_1^+ + \left(-\dfrac{1}{2}+\dfrac{30}{40}-(-1)\right)R_1^- \\ + \left(\dfrac{1}{2}+\dfrac{60}{40}-2\right)R_2^+ + \left(-\dfrac{1}{2}+\dfrac{60}{40}-(-2)\right)R_2^- \\ + \left(\dfrac{3}{7}+\dfrac{30}{70}\phantom{-0}\right)L_0^+ + \left(-\dfrac{3}{7}+\dfrac{30}{70}\phantom{-(-0)}\right)L_0^- \\ + \left(\dfrac{3}{7}+\dfrac{60}{70}-1\right)L_1^+ + \left(-\dfrac{3}{7}+\dfrac{60}{70}-(-1)\right)L_1^- \\ \le \dfrac{1}{2} + \dfrac{3}{7} + \dfrac{370}{40} + \dfrac{370}{70} - 16 $$

Which simplifies to:

$$ R_0^+ + \frac{1}{4}R_1^+ + \frac{5}{4}R_1^- + 3R_2^- + \frac{6}{7}L_0^+ + \frac{8}{7}L_1^- \le -\frac{15}{28} $$

Since the left hand is a sum of nonnegative terms, it must be nonnegative; but a nonnegative number cannot be less than or equal to a negative number. Therefore the system of equations has no solution, and the puzzle has no solution for 16 bars.


If the number of bars is reduced to 15, the right-hand side of the final equation increases by one and becomes positive, meaning that a solution for 15 bars is not ruled out. The maximum amount of extra time available is: $$\frac{-\frac{15}{28}+1}{\frac{1}{40}+\frac{1}{70}}=\frac{\frac{13}{28}}{\frac{11}{280}}=\frac{130}{11}$$

Therefore the minimum time required is: $$370-\frac{130}{11}=\frac{3940}{11}=5\text{h}58\tfrac{2}{11}$$

To achieve this minimum time all the terms on the left-hand side of the equation must be zero. Also, the inequalities will become equalities. This yields the following system of equations:

$$ - R_0^- + R_2^+ = 1 \\ - L_0^- + L_1^+ = 1 \\ 20R_0^- + 60R_2^+ = \frac{3940}{11} \\ 30L_0^- + 40L_1^+ = \frac{3940}{11} \\ 2R_2^+ + L_1^+ = 15 $$

This system of five equations in four variables has a unique solution:

$$ R_0^- = \frac{41}{11},\ R_2^+ = \frac{52}{11},\ L_0^- = \frac{50}{11},\ L_1^+ = \frac{61}{11} $$

Since the distances are not integers, the thieves must drop the bars off somewhere in the middle. Their movements will look like this:

Lia (gold line) carries 1 bar all the way to the station, then carries 12 bars from the midway point to the station in 12 trips. Rod (blue line) carries 12 bars to the midway point in 6 trips and then carries 2 bars all the way to the station. The total number of bars moved is 15: the one Lia carries plus the 2 Rod carries plus the 12 they both carry.

Rod makes 6 return trips with a total distance of $R_0^-=\frac{41}{11}$, so the midway point is $\frac{41}{66}$ miles from the start. Lia makes 12 return trips with a total distance of $L_0^-=\frac{50}{11}$, so the midway point is $\frac{25}{66}$ miles from the end. $\frac{41}{66}+\frac{25}{66}=1$ so this checks out. The total time taken by Rod is $6\left(60+20\right)\frac{41}{66}+60=\frac{3940}{11}$ and the total time taken by Lia is $40+12\left(30+40\right)\frac{25}{66}=\frac{3940}{11}$, which also checks out. Finally, looking at the plot, each of the times that Rod drops off a pair of bars comes before the two corresponding times when Lia picks up the bars.

$\endgroup$
6
  • $\begingroup$ Terng nanylfvf. Tb Greencvaf! $\endgroup$
    – DrD
    Sep 13 at 20:38
  • $\begingroup$ Even without the guesses, you can derive this upper bound from your first four original constraints by multiplying them by $1/2$, $3/7$, $1/40$, and $1/70$, respectively, and adding them up. $\endgroup$
    – RobPratt
    Sep 14 at 16:04
  • $\begingroup$ @RobPratt Thanks, that's way cleaner! I incorporated your method into the answer. $\endgroup$ Sep 14 at 17:49
  • $\begingroup$ I confirmed your minimum time for 15 bars via linear programming. $\endgroup$
    – RobPratt
    Sep 14 at 22:30
  • 1
    $\begingroup$ @RobPratt That's how I originally found it =) I added all the "by hand" work because of the [no-computers] tag $\endgroup$ Sep 14 at 22:33
2
$\begingroup$

An alternative method to Kate's to get the same amount of bars.

Rod carrying 1 bar is 1.25 bars/h round trip, 2 bars is 2b/h, and Lisa is 0.875b/h so we should maximise the time Rod carries 2 bars.

Rod can do 3 round trips and a half trip with 1.1666 hours left for 8 bars and Lisa can do 4 round trips and a half trip with 0.8333 hours left for 5 bars, 13 total.

In that last bit of time Lisa can travel 0.71 miles back towards A and would still have time to carry a bar back to B. So we need Rod to get back to A, with 0.8333 hours left. Then carry 2 bars to Lisa's max point, 0.29 miles, so he'll have 0.5433 hours left to carry 1 bar which leaves him with 0.1883 hours or 11.3 mins left when he's carried the bar to B. Lisa then carries her bar back to B with only 0.3 mins spare. For 15 bars total, 8+5+1+1.

The meeting point can be decreased to ~0.67 miles from B, Rod must arrive first so that the bar is there for Lisa to pick up, and 0.67 miles Rod arrives with 0.5033 hours left and Lisa arrives with 0.4983 hours left. This gives Lisa ~3 extra mins (and takes them off Rod).

$\endgroup$

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.