There are at least three Kevins on Puzzling. I plan to trap them in my labyrinth

Question

Note: please do not edit the title! It originates in a challenge in Stack Overflow chat.

I have rounded up all ten (currently) of the Puzzling SE users named Kevin and trapped them in my labyrinth. The only way out is across a narrow bridge which can bear the weight of at most two Kevins at a time. It is pitch dark and the bridge has no handrails, so they will need a torch in order to be able to cross at all. Each Kevin will take a different amount of time to cross the bridge; let these times be $t_1,t_2,\dots,t_{10}$ in increasing order. Moderator Kevin is the slowest, taking time $t_{10}$ to cross, because he has to carry his diamonds with him. I'll supply them with a torch so that they can see to cross the bridge, but it will only last for a finite period of time.

My aim is to allow all the Kevins except the slowest to escape the labyrinth (if the moderator escapes, he'll give me a 365-day suspension for moderator entrapment as soon as he gets back to his computer). I want to ensure the torch will last exactly long enough to allow the nine non-moderator Kevins to escape but not all ten. How long (in terms of the times $t_1,\dots,t_{10}$) should I make the torch last?

Answer 1

You should make the torch last the minimum amount of time to allow nine of the Kevins to escape. This will ensure that all ten cannot escape. We will compute this time in terms of $t_1,\ldots,t_9$. Actually, we will describe a computation that is valid for any finite number of Kevins.

Suppose there are $n$ Kevins, call them $K_1$, $\ldots$, $K_n$ from fastest to slowest. Let $K_i$ and $K_j$ be a pair of Kevins, with $3\leq i<j\leq n$. There are two reasonable-sounding strategies for getting $K_i$ and $K_j$ across the bridge. The first strategy, which I will call Strategy A: Kevins $K_1$ and $K_2$ cross, and $K_1$ returns with the flashlight. Then Kevins $K_i$ and $K_j$ cross, and $K_2$ returns with the light. This takes total time $$ t_1+2t_2+t_j. $$ The second strategy, which I will call Strategy B: $K_1$ keeps the flashlight, and escorts $K_i$ and $K_j$ across one at a time. This takes total time $$ 2t_1+t_i+t_j. $$ Strategy A is faster than Strategy B if and only if $$ t_i>2t_2-t_1. $$

Set Kevins $K_1$ and $K_2$ aside, and group the remaining Kevins into pairs: $\{K_n,K_{n-1}\}$, $\{K_{n-2},K_{n-3}\}$, and so on (there may be an odd Kevin out who is unpaired). Call a pair of Kevins slow if the faster member of the pair takes longer than $2t_2-t_1$ to cross the bridge, otherwise call the pair fast (the odd Kevin out, if there is one, will be considered fast).

Each slow pair of Kevins will cross the bridge using Strategy A. After all of the slow pairs have crossed, $K_1$ will escort every remaining Kevin across the bridge one by one. The total time for this is $$ (n-2-k)t_1 + (2k+1)t_2 + \sum_{i=1}^k t_{n+1-2i} + \sum_{i=3}^{n-2k}t_i, $$ where $k$ is the number of slow pairs. The paper [1] gives a rigorous proof that this is optimal.

[1] Rote, Günter. Crossing the bridge at night. Bulletin of the European Association for Theoretical Computer Science, no. 78, 2002, pp. 241--246.

Answer 2

The fastest I found:

For notation, $K_n$ is the Kevin whose time for crossing is $t_n$. $\rightarrow$ means he/they cross the river. $\leftarrow$ means he crosses back.

$K_1,K_2\rightarrow;\ K_1\leftarrow;\ t_2+t_1;\\ K_8,K_9\rightarrow;\ K_2\leftarrow;\ t_9+t_2;\\ K_1,K_2\rightarrow;\ K_1\leftarrow;\ t_2+t_1;\\ K_6,K_7\rightarrow;\ K_2\leftarrow;\ t_7+t_2;\\ K_1,K_2\rightarrow;\ K_1\leftarrow;\ t_2+t_1;\\ K_4,K_5\rightarrow;\ K_2\leftarrow;\ t_5+t_2;\\ K_1,K_2\rightarrow;\ K_1\leftarrow;\ t_2+t_1;\\ K_1,K_3\rightarrow;\ t_3; $

I believe this is the fastest 9 can cross, so that'd make impossible to cross with a slower Kevin. So the torch shall last $4t_1+7t_2+t_3+t_5+t_7+t_9$

Answer 3

The solution to the simple form of this problem (get $t_1$, $t_2$, $t_5$ and $t_{10}$ across a bridge in 17 time units) requires that:

You send the two longest times across together, so that only the longer of the two affects the score.
So, send $t_1$, $t_2$ across (2)
Send $t_1$ back with the torch (3) Send $t_5$ and $t_{10}$ across (13) Send $t_2$ back with the torch (15) Send $t_1$, $t_2$ across again (17)

For more bridge-crossers, this strategy requires remarkably little adaptation.

To start, you need a pair of torch-runners - the two people who can carry the torch back-and-forth most quickly across the bridge. Logically, these should be $t_1$ and $t_2$. The others will cross in pairs, with $t_1$ and $t_2$ crossing the bridge between each pair to ensure speedy delivery of the torch.

Send $t_1$, $t_2$ across (2)
Send $t_1$ back with the torch (3)
Send $t_3$ and $t_4$ across (7)
Send $t_2$ back with the torch (9)
Send $t_1$, $t_2$ across again (11)
Send $t_1$ back with the torch (12)
Send $t_5$ and $t_6$ across (18)
Send $t_2$ back with the torch (20)
Send $t_1$, $t_2$ across again (22)
Send $t_1$ back with the torch (23)
Send $t_7$ and $t_8$ across (31)
Send $t_2$ back with the torch (33)
Send $t_1$, $t_2$ across again (35)
Send $t_1$ back with the torch (36)
Send $t_9$ and $t_{10}$ across (46)
Send $t_2$ back with the torch (48)
Finally, send $t_1$, $t_2$ across again (50)

This would yield a time of 50 units for everyone to cross - in a bid to avoid moderator rage and the dreaded banhammer, we don't want the torch to last for that long.

So:

Once $t_7$ and $t_8$ have crossed (at time 31), we once again send $t_2$ back (33), send $t_1$ and $t_2$ across again (35) and $t_1$ back one final time (36).
This time, however, rather than allowing moderator Kevin and his diamonds to cross (for fear that the bridge will not hold the weight of such riches), $t_1$ and $t_9$ run off together, reaching the other end of the bridge at a time of 45 units, scant seconds before the torch flickers and dies out.

This solution assumes that $Kevin_1$ and $Kevin_2$ do not tire in their travels, and can maintain a consistent pace throughout. It also assumes that moderator Kevin upholds the logical foundation of this site, and doesn't simply insist upon crossing first.

It also assumes that (e.g.) $t_9$ = $t_8$ + $t_1$, which is probably not the case, in which case your torch time will actually be 4$t_1$ + 7$t_2$ + $t_4$ + $t_6$ + $t_8$ + $t_9$

EDIT: After seeing Albert Masclans' answer, I realise I've made a mistake. I tried to build travelling pairs from the bottom up, when I should have worked top-down, pairing $t_9$ and $t_8$, $t_7$ and $t_6$, and $t_5$ and $t_4$

This allows the last trip to be $t_3$ and $t_1$, and gives a total of 4$t_1$ + 7$t_2$ + $t_3$ + $t_5$ + $t_7$ + $t_9$, or 42 by my previous assumptions