Sunday 18 September 2011

crossing the bridge

Four friends A,B,C and D are at one end of bridge and it's night. They have one torch to be used while crossing the bridge. All four have different speeds of walking and they take 1, 2, 5 and 10 minutes respectively to cross the bridge. At a time, at most two people can be crossing the bridge (walking on either of the sides). If say A and D walk together, A has to slow down because they have to go together using just one torch. Let them show how they can cross the bridge given that the torch battery will last only for 17 minutes.

\via{Prashant}, \thanks_for_hint{Prashant}

The starting approach could be trivial in which we try to send 2 of them on other side, let one of them come back with torch and take another guy from first side to second side. Initially we may think that A will be the speediest person to go back to give torch back. With this we will always end up in using torch for at least 3 times for A's back journey.
For example->
A,B,C,D ------------------ None
B,C ---------------------- A,D
A,B,C -------------------- D
....
....
and so on.
But this is not the optimal way because the time when two of them go together is lower bounded by the person who is slower amongst the two. If every time, A takes one of them to the other side, each trip will take 2,5 and 10 minutes respectively. Note that this itself sums up to 17 minutes, but as we saw earlier, at least 3 minutes are required for A's back journey. Thus, this kind of approach will not work.

The quick hint that helps solving this is let C and D go together and keep them steady, as in don't let them come back. If that is to be done, we can send C and D initially itself; but that will require one of them (of course C) to come back which we don't want. So, let's send A and B first and let A_the_speediest come back. Now it can wait and let C and D cross the bridge with the torch. This way C and D cross together and B already on other side can quickly take torch back.

Thus, the scheme will be->
A,B,C,D --------------- None
C,D ------------------- A,B (takes 2 mins)
A,C,D ----------------- B (takes 1 min)
A --------------------- B,C,D (takes 10 mins)
A,B ------------------- C,D (takes 2 mins)
None ------------------ A,B,C,D (takes 2 mins)
Total takes 17 mins.

No comments:

Post a Comment