Shortest bridge crossing
Search the finite states of three people and a torch to find the least total time.
The video could not load. Check your connection and try again, or download it directly.
Download video
Open Chinese transcript
- 三人单独过桥要一、二、五分钟,手电必须随人,每次最多两人,同行用较慢者的时间。
- 先让一分和二分的人一起到对岸,手电也在对岸。这一步用较慢者的两分钟,累计两分。
- 还要接五分的人,所以一分的人带手电返回起岸,用一分钟,累计变成三分。
- 接着一分和五分的人一起过桥,用五分钟。现在三个人和手电都在对岸,累计八分。
- 把每一种允许的过桥办法都算一遍,没有哪一种少于八分钟;刚才的八分钟走法也符合全部规则。
- 最短时间是八分钟。每一步都要同时记录三个人和手电在哪一岸,方向不能画反。
Sources for this explanation
Logical thinking
Record who and the torch are on each bank, expand legal moves by accumulated time, and keep the least time per state.
Worked example
Three people take 1, 2 and 5 minutes. They and the torch start together. At most two cross, one may cross, the torch must travel, and a pair takes the slower time. What is the minimum?
The shortest plan is 1 and 2 across (2), 1 back (1), then 1 and 5 across (5): 8 minutes.
Try one question
The displayed valid plan totals 2+1+5=8 minutes.