33
$\begingroup$

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?

$\endgroup$
  • 29
    $\begingroup$ You and d'alar'cop need to stop taking other puzzlers hostage. You're creating an atmosphere of fear. $\endgroup$ – Engineer Toast May 18 '15 at 13:05
  • 2
    $\begingroup$ So I assume the time you're looking for satisfies "a solution exists with this time in which all except the slowest one escape, but no solution with all 10 escaping with this time exists" and that the goal of "preventing #10 from escaping" is just fluff. Otherwise, as soon as you allow at least time $t_10$, the slowest one can always escape and leave one or more others behind. $\endgroup$ – Angew May 18 '15 at 15:02
  • 4
    $\begingroup$ To make it more difficult for you, rand al'thor, I am willing to sacrifice myself and allow Moderator Kevin to get across if it means I stay behind. (I'll count on him sending help after he revenge-bans you.) ;-) $\endgroup$ – Kevin May 18 '15 at 19:21
  • 6
    $\begingroup$ @Kevin Which of you (294, 1497, or both?) got a notification from this comment? (And yes, that was the real reason I posted this puzzle - to get 2 users with the same username to leave comments in the same place so I could do this experiment! ;-) ) $\endgroup$ – Rand al'Thor May 18 '15 at 19:40
  • 2
    $\begingroup$ @randal'thor I'm 249 and got your message. (Wait a second - why am I helping you out? You kidnapped me!) $\endgroup$ – Kevin May 18 '15 at 19:44
19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perfect answer! Well-described and well-referenced. Trust a mathematician to do the general case... :-) $\endgroup$ – Rand al'Thor May 19 '15 at 8:30
18
$\begingroup$

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$

$\endgroup$
  • 11
    $\begingroup$ This method is not necessarily the fastest. An alternative is to have Kevin 1 carry the torch back and forth, escorting the other Kevins, which would take time $7t_1+t_2+t_3+t_4+t_5+t_6+t_7+t_8+t_9$. If $t_2,\ldots,t_9$ are all about the same size and $t_1$ is much smaller, this is faster than your strategy. $\endgroup$ – Julian Rosen May 18 '15 at 14:27
  • 1
    $\begingroup$ @JulianRosen Well seen. With only the provided information, it's impossible to tell which strategy is the better. In order to be my strategy better than the one you propose, it should be true that $3t_1+t_4+t_6+t_8>6t_2$. And to simplify, that's true if $\frac{t_1+t_4}{2}\geq t_2$. And that's not something we can assume true. $\endgroup$ – Masclins May 18 '15 at 14:37
14
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.