wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Four people need to cross a bridge in 17 minutes
        
(Message started by: oceanvibe on Dec 9^th, 2015, 11:04pm)

Title: Four people need to cross a bridge in 17 minutes
Post by oceanvibe on Dec 9^th, 2015, 11:04pm

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?

Title: Re: Four people need to cross a bridge in 17 minut
Post by rmsgrey on Dec 10^th, 2015, 7:06am

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 brute-forced to prove the minimum.

Title: Re: Four people need to cross a bridge in 17 minut
Post by rloginunix on Jul 12^th, 2016, 4:24pm

Would you accept as formal a [hide]graph[/hide]-based proof constructed thus:

1) A [hide]vertex captures the entire state of transitions - distribution of travellers across the banks, L for left, initial, and R for right, destination, bank[/hide]

2) An [hide]edge between any two vertexes exists iff the transition from one vertex to another does not violate the problem statement[/hide]

3) A [hide]cost/weight of an edge is the slowest traveller's speed[/hide]

4) A [hide]weight is further subindexed by the trip's participants, for clarity[/hide]

The task then is reduced to [hide]computing the shortest path through the graph[/hide].

Here (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_general;action=display;num=1396709569;start=175#181)

is a sample [hide]graph[/hide] I constructed for a smaller, [5, 2, 1], set, from where we see that the costs distribute as: 15, 15, 9, 9, 8, 8.

Title: Re: Four people need to cross a bridge in 17 minut
Post by dudiobugtron on Aug 15^th, 2016, 7:24pm

on 12/10/15 at 07:06:54, 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 brute-forced 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:
D|ABC*
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 ABD|C situation would be at least:
??|?B*
ACD*|B
D|ABC*
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 ABD|C via these steps:
BD|CA*
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
AB|CD*
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 AB|CD*, ie:

ABCD*|
AB|CD*
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.

Title: Re: Four people need to cross a bridge in 17 minut
Post by rmsgrey on Aug 16^th, 2016, 3:08pm

on 08/15/16 at 19:24:45, 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.