Author 
Topic: Four people need to cross a bridge in 17 minutes (Read 1010 times) 

oceanvibe
Junior Member
This is, my personal, text
Gender:
Posts: 59


Four people need to cross a bridge in 17 minutes
« on: Dec 9^{th}, 2015, 11:04pm » 
Quote Modify

Four people need to cross a bridge in 17 minutes in the middle of the night. The bridge can only hold two or less people at any time and they only have one flashlight so they must travel together (or alone). The flashlight can only travel with a person so every time it crosses the bridge it must be carried back. Tom can cross in 1 minute, John can cross in 2 minutes, Sally can cross in 5 minutes, and Connor can cross in 10 minutes. If two people cross together they go as fast as the slower person.How can they cross the bridge in 17 minutes or less?


IP Logged 
4k wallpapers, my favorite space wallpapers, 1366x768 wallpaper



rmsgrey
Uberpuzzler
Gender:
Posts: 2819


Re: Four people need to cross a bridge in 17 minut
« Reply #1 on: Dec 10^{th}, 2015, 7:06am » 
Quote Modify

I prefer this puzzle when it doesn't tell you the target time. Oddly the hardest part about proving an optimal time rigorously is proving how many trips it takes  the best I've come up with is proving that more than 7 crossings must take more than 17 minutes, leaving only a finite number of possibilities at 5 and 7 crossings, which can be bruteforced to prove the minimum.


IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Four people need to cross a bridge in 17 minut
« Reply #2 on: Jul 12^{th}, 2016, 4:24pm » 
Quote Modify

Would you accept as formal a graphbased proof constructed thus: 1) A vertex captures the entire state of transitions  distribution of travellers across the banks, L for left, initial, and R for right, destination, bank 2) An edge between any two vertexes exists iff the transition from one vertex to another does not violate the problem statement 3) A cost/weight of an edge is the slowest traveller's speed 4) A weight is further subindexed by the trip's participants, for clarity The task then is reduced to computing the shortest path through the graph. Here is a sample graph I constructed for a smaller, [5, 2, 1], set, from where we see that the costs distribute as: 15, 15, 9, 9, 8, 8.


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: Four people need to cross a bridge in 17 minut
« Reply #3 on: Aug 15^{th}, 2016, 7:24pm » 
Quote Modify

on Dec 10^{th}, 2015, 7:06am, rmsgrey wrote:Oddly the hardest part about proving an optimal time rigorously is proving how many trips it takes  the best I've come up with is proving that more than 7 crossings must take more than 17 minutes, leaving only a finite number of possibilities at 5 and 7 crossings, which can be bruteforced to prove the minimum. 
 For four people A, B, C and D, with crossing times Ta, Tb, Tc and Td respectively, the minimum number of crossings is 5. This is where you take 2 across each time, and one person comes back each time. To get to seven crossings, at some point you would either have to bring 2 people back, or, only take 1 person across. Bringing 2 people back There's no point in bringing two people back if you only have 2 on the right (final) side of the bridge, since that brings us back to our starting position. And of course there's no need to bring anyone back if you have 4 people on the right side. So the only time you would want to bring 2 people back is if there are 3 on the right side. This would then bring us to the position with one person on the right side. Wolog, let's say that A, B and C are on the right side. This can be represented as: DABC* If we take A and B back, C will be left: ABD*C (The * is for the flashlight) Obviously we can't have just taken A and B over beforehand (otherwise we'd return to a previous position), so C must have just arrived with A or B. Let's choose A (wolog again). This means B must have arrived on a previous trip. So, the steps needed to create this ABDC situation would be at least: ???B* ACD*B DABC* ABD*C The time for this would be at least: Tb + min(Ta,Tc,Td) + max(Ta,Tc) + max(Ta,Tb) This is strictly larger than the time it would take to reach ABDC via these steps: BDCA* ABD*C Which is max(Ta,Tc) + Ta max(Ta,Tc) + Ta is at most max(Ta,Tc) + max(Ta,Tb) Therefore it is pointless to bring 2 people back. Taking 1 person across There's no point in taking only 1 person across if you have two people already on the right side, since you could just take two people across and finish there. ie: from position: AB*CD Taking one person across would mean the time to get to ABCD* would be at least Ta + Tb. Whereas taking both across would take at most max(Ta,Tb). And if there are no people on the other side, it's obviously pointless to take one person across, and then bring them straight back. So the only time this might be useful is if you have one person on the other side already. wolog, let's say we are in position: ABC*D If we take one person across (and then a different one back, since taking the same person back is pointless)  let's say that person is C  then we would have this set of positions: ABC*D ABCD* ABD*C The time to create these positions (from ABCD* ) is at least Td + min (Ta,Tb,Tc) + Tc + Td So instead, we could just have gone straight to ABCD*, ie: ABCD* ABCD* ABD*C Which would take Td + max(Tc,Td). This is of course less than Td + Tc + Td. Therefore there's no point in taking only one person across. Therefore, there is no need to use 7 crossings.  PS: Note, I'm not confident that this shows that there's no need to use more than 7 crossings  although rmsgrey has apparently already shown this, so I only worried about the 7 situation.

« Last Edit: Aug 15^{th}, 2016, 7:27pm by dudiobugtron » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2819


Re: Four people need to cross a bridge in 17 minut
« Reply #4 on: Aug 16^{th}, 2016, 3:08pm » 
Quote Modify

on Aug 15^{th}, 2016, 7:24pm, dudiobugtron wrote:PS: Note, I'm not confident that this shows that there's no need to use more than 7 crossings  although rmsgrey has apparently already shown this, so I only worried about the 7 situation. 
 It's trivial that the trip which gets the slowest guy across must take 10 minutes. Each other trip must take at least 1 minute, so in 17 minutes, you can make at most 8 trips if the slow one is to end up on the far side. Since the torch has to make an odd number of trips, you end with an upper bound of 7 trips.


IP Logged 



