crossing the bridge
Problem
Crossing the Bridge printable worksheet
Four friends need to cross a bridge.
They start on the same side of the bridge.
A maximum of two people can cross at any time.
It is night and they have just one lamp.
People that cross the bridge must carry the lamp to see the way.
A pair must walk together at the speed of the slower person:
- Rachel: - takes 1 minute to cross
- Ben: - takes 2 minutes to cross
- George: - takes 7 minutes to cross
- Yvonne: - takes 10 minutes to cross
The second fastest way of getting the friends across takes 21 minutes.
The fastest takes 17 minutes. Can you work out how it is done?
You can use the interactivity below to experiment with different strategies.
By clicking on the purple cog you can enter the settings menu and change how long it takes each person to cross.
There are two optimal strategies for solving this type of problem:
Strategy 1 solves the original problem in 17 minutes
Strategy 2 solves the original problem in 21 minutes
Experiment with different speeds and work out when to use Strategy 1 and when to use Strategy 2.
Is there a way of determining which strategy will be best?
Can you find sets of speeds for which both strategies give the same crossing time?
Getting Started
Try different possible starting pairs and work systematically from there.
If one person takes 10 minutes to cross the bridge, and another takes 7 minutes, how can they all cross in just 17 minutes?
If A is the quickest to cross, then B, then C, then D, can you describe each of the strategies in terms of As, Bs, Cs and Ds, and then identify the difference?
Student Solutions
Well done and thank you for the many solutions we received to this problem.
Miraya and Charlie from Heckmondwike Grammar School, Mohsin from Oasis Academy Hadley, Mohit from Burnt Mill Academy, Harlow, Nayanika from the Tiffin Girls' School and Naima from Bexley Grammar School, all in the UK, Pat, Pair and Korya from Rugby School Thailand, Giacomo and Kairui from Headstart International School in Thailand, Yingge from Headstart in China, Ariel from Diocesan Girls' School in Hong Kong and Mahdi from Mahatma Gandhi International School in India found the second-best strategy (21 minutes). This is Mohit's work:
[This strategy] involves using the person with the shortest crossing time (Rachel with 1 minute) to accompany each person across the bridge so the solo return time will always be the shortest possible.
This means the total time taken will be the sum of each person's crossing time (as they have a crossing time higher than that of Rachel's) + the 2 return journeys that Rachel must take to collect the next person.
It will be 2+7+10+1+1 = 21 minutes total time taken for everyone to be together on the other side of the bridge.
Nithya from the Tiffin Girls' School, Olivia from Stafford Grammar School, Evie and Imogen from Wycombe High School, Wikor and Casano from LAE Tottenham, Isaac, Mr Robinson and Miss Morgans from St. Joseph's RC Primary School, Newbury, Naima, Aaron, Diego and Rafael from Bexley Grammar School, Alex from Thomas Tallis, Zavya, Miraya and Charlie from Heckmondwike Grammar School and Lucas from Leeds, all in the UK, Maggie W from the Village High School in Australia, Elliot, Peter, Pair, Korya, Ysabel and Pat from Rugby School Thailand, Sunhari from Oman, Sanika from PSBBMS,OMR in India, Yeojun from SSIS in Korea, Vince from St Charles Primary School Ryde in Australia, CLIP from Portugal, Harrington Park Public School in Australia, Oscar from Ramon Rebolledo Solano in Mexico, James and Oais and Shruthi from the UK, Marc from Cambridge, Nayanika, Ariel, Mahdi, Jack, Mohsin, Giacomo, Kairui, Yingge, Mohit and Rik found the best strategy (17 minutes). This is Ysabel's work:
A=1 min, B=2 mins, C=7 mins, D= 10 mins
To get 17 minutes, first I thought of what wouldn't be possible. As C and D have a total time of 17 minutes, that means they shouldn't cross separately since more time will be required to go back for others. Therefore, they need to cross together. If C and D go first, one person needs to go back for the rest which will take at least 7 minutes, so they should not go first.
With that information, that only leads me to believe A and B need to cross first. After they have crossed, I chose A to return the torch because he is quicker (although it does not matter because later on, the person who does not return now will need to be the one to return later, adding the same to the sum). At this point, only 3 minutes have passed. As I earlier mentioned, C and D need to go together so less time will be taken. This is the appropriate time for them since now we do not have the problem of taking an additional 7 minutes to cross back because B may return instead. So after C and D cross, as well as B after to return for A, the total time will be 15 minutes, and after A and B finally cross together, the total time will be 17 minutes, with everyone safe and happy on the other side!
Kairui and Nayanika tried out some different sets of numbers to see whether strategy 1 (two fastest people, then two slowest people, then two fastest people) is always faster than strategy 2 (fastest person goes back to collect each of the other people). Kairui wrote:
Random number testing:
1,2,7,10 strategy 1 works the fastest
2,3,5,8 strategy 1 works the fastest
2,2,2,3 strategy 1 works the fastest (the strategies take the same amount of time)
1, 97, 10, 980 strategy 1 works the fastest
3,9,9,9 strategy 1 works not the fastest / but the strategy 2 [also] works the fastest
Nayanika found several examples where the two strategies take the same amount of time:
With the times 7 minutes, 12 minutes, 17 minutes and 24 minutes, strategy 1 works to produce the quickest total time. (In fact the strategies take the same amount of time for this example)
Meanwhile, with the times 1 minute, 2 minutes, 3 minutes and 4 minutes, strategy 2 works best. (In fact the strategies take the same amount of time for this example)
The times 8 minutes, 14 minutes, 20 minutes and 26 minutes also [make the two strategies take the same amount of time].
When all 4 people take the same amount of time, or just one person takes a different amount of time, both strategies are equally as efficient, and take the shortest amount of time.
Giacomo and Yingge tried out sets of numbers where some of the numbers were equal. Giacomo wrote:
If there are 3 numbers that are the same and one is bigger than the others then you can use either strategy.
If there are 3 numbers that are the same and one is smaller than the others, you need to use strategy 2.
Pat, Mahdi, Ariel, Sunhari, Sanika and James and Oais used algebra. Ariel found a quick way to test which strategy is quicker:
The first one is using the faster two people to pass the lamp and let the slower two walk together. The steps are like this (using 1, 2, 7, 10, bracket shows the tally):
c d $\rightarrow$ a b (2 min)
a c d $\rightarrow$ b (3 min)
a $\rightarrow$ b c d (13 min)
a b $\rightarrow$ c d (15 min)
$\rightarrow$ a b c d (17 min)
Time taken = a + 3b + d
The second one is using the fastest person to pass the lamp and let others walk one by one. The steps are like this (also using 1, 2, 7, 10):
c d $\rightarrow$ a b (2 min)
a c d $\rightarrow$ b (3 min)
d $\rightarrow$ a b c (10 min)
a d $\rightarrow$ b c (11 min)
$\rightarrow$ a b c d (21 min)
Time taken = 2a + b + c + d
If we take out a+b+d [from] both equations, the first one leaves us with 2b and the second leaves us with a+c, which is what you need to calculate for comparing which strategy is faster (I call this the determining factor).
Take 2, 6, 7, 10 as an example, the determining factor of the first method is 6$\times$2=12 while for the second one it’s 2+7=9. Therefore, the second strategy is faster and it takes 2$\times$2+6+7+10=27 min, which is the shortest possible.
James and Oais used the expressions to create an example where strategy 2 is better:
We spotted that [strategy 1] was usually quicker, but it had more "b's" in it, so we created a problem where b was high:
a = 1 min
b = 20mins
c = 21mins
d = 22mins
This makes [strategy 2] nearly 20 minutes quicker!
Sunhari, Sanika and James and Oais wrote this as an inequality. This is Sanika's work:
Strategy [2] will be used if $$2a+b+c+d\lt3b+a+d\\ \Rightarrow a+c\lt2b$$
Strategy [1] will be used if $$2a+b+c+d\gt3b+a+d\\ \Rightarrow a+c \gt 2b$$
Pat and Mahdi found an equation that is true when the two strategies take the same amount of time. This is Pat's work:
My first strategy = my second strategy
$A+3B+D = 2A+B+C+D$
$2B-A-C = 0$
$2B = A+C$
Therefore, the sets of speeds for which both strategies give the same crossing time has to have $2B = A+C$
Teachers' Resources
Why do this problem?
This problem offers an interesting challenge which can be used to develop mathematical thinking.
Students reaction to the problem has often been "It's impossible!". Once the problem has been solved it can provided a useful vehicle for discussing what mathematicians do when they are stuck: experiment, explore dead ends, discuss with friends, walk away from the problem and return to it later... Teachers may want to use this problem to help students think about what they do when they want
to give up.
Possible approach
This problem featured in an NRICH Secondary webinar in June 2021.
You could use the interactivity to introduce the problem and make sure that students understand the constraints.
Ask the students to tackle the problem in pairs, either at computers or on paper. Challenge them to find a strategy for getting the friends across in just 17 minutes. As they experiment, circulate around the classroom and listen in on conversations. Some might suggest that it's impossible...
We experience pleasure and satisfaction when solving problems, so you may want to ensure that those who solve this problem quickly, do not deny the rest of their classmates that satisfaction ("let's not spoil anyone's fun").
Consider giving everyone as much time as they need to work on the first part of this problem, and rather than bringing the whole class together and inviting the fastest pairs to demonstrate their strategy, introduce the second part of the problem which challenges students to determine the criteria for selecting when to use each of the two optimal strategies. If students are using the interactivity they can click on the purple cog to enter the settings menu and change how long it takes each person to cross the bridge.
As students go solving the first part of the problem they can then progress onto the second part.
The second part of the problem will require clear recording of results and careful analysis of the different possibilities.
To help with this analysis you may like to suggest that students consider the time taken by each strategy when A is the quickest to cross, followed by B, then C, then D. So for example, if A and C cross together, the time taken would be determined by C.
So Strategy 2 would have a total crossing time of B + A + C + A + D.
Bring the class together at the end of the lesson to share discoveries and explanations.
Key question
If one person takes 10 minutes to cross the bridge, and another takes 7 minutes, how can they all cross in just 17 minutes?
Possible extension
The second part of this problem challenges students to provide clear and convincing justifications.
Possible support
Students could have a go at River Crossing before embarking on this problem.