А как доказать, что быстрее нельзя?
Я кстати и не знаю совершенно строгого доказательства.
Ну то есть для этого конкретного примера конечно доказательством может служить перебор. 
А вот, что для общего случая справедлив такой алгоритм - тут сложнее.
Сам алгоритм собственно такой. Пусть у нас есть N>1 человек с временами a[1], a[2], ..., a[N]. Если a[N-1]>2*a[2]-a[1], то сначала идут самые быстрые (1 и 2), один из них (1) - возвращается с фонариком, затем идут самые медленные (N-1 и N), а второй шустрый (2) - возвращается с фонариком. Так отводятся все пары "тормозов", у которых более быстрый удовлетворяет указанному выше неравенству. Всех последующих водит самый шустрый по забавно-засательному методу Катенки - идут 1 и i, и затем 1 возвращается обратно с фонариком.
Могу привести в некотором смысле обоснование правдоподобности этого алгоритма от автора этой задачи Это профессор Gordon V. Cormack. Собственно, как я понимаю, он не был автором задачи как таковой, но он первый предложил ее на какой-то олимпиаде по программированию. А сам он утверждал, что задача является обобщением задачи, которая была в каком-то из тестов Microsoft'а. (вполне возможно, что как раз в варианте 1, 2, 5, 10).
Собственно вот его обоснование, оформленное в виде нескольких "наблюдений"
Observation 1: somebody has to get the flashlight back after every forward trip. This should obviously be the fastest person on the far shore.
Observation 2: in the general case, we have 4 or more people, the flashlight is on the starting side.
Consider the two slowest people. there are 2 sensible strategies; we pick the fastest:
1. we can send each with the fastest person, who returns with the flashlight. this takes 2a+x+y time where a is the fastest and x and y are the two slowest
2. we can send the fastest & 2nd fastest person, have the fastest return with the flashlight, send the slowpokes together, have the 2nd fastest return with the flashlight. This takes a+2b+y where a is fastest, b second fastest, and y slowest
BUT WAIT, you say. What if strategy 1 is better than 2 for x and y but perhaps x or y could have been paired with somebody else. We already know that
2a+x+y <= a+2b+y
x <= 2b - a
Now if we had a different x' and y', it would be the case that x' <= x and y' <= y so
x' <= 2b - a
so for any other pair 1 will be the best strategy.
BUT WAIT, you say again. What if strategy 2 is better than strategy 1, but prevents strategy 2 from being used later, which would have been even better.
Let a,b be the 2 fastest and w,x,y be the slowest. If we do x,y together we (may) force w to be done alone.
x,y together: a+2b+y
w alone: a+w
total: 2a+2b+w+y
If we do y alone, then w,x together.
y alone: a+y
w,x together: a+2b+x
total: 2a+2b+x+y
Since x >= w, this is worse so there's no point in deferring the pairing.
Observation 3: The end game. If there are 3 people left, the fastest shuttles them across. If there are 2 people left, they go together.
Observation 4: One person alone is a special case. Happens only if this person started alone.
По видимому, это можно сделать основой строгого доказательства, но у меня не хватило для этого то ли ума, то ли терпения. Ну первое наблюдение вроде понятно как - надо доказать какую-нибудь лемму вроде того, что если есть два набора людей a[1], ..., a[N], и b[1], ..., b[N], причем a[i]<=b[i], то для перевода первого набора потребуется не больше времени, чем для второго.
