Optimal strategy for river crossing game

Background: the bridge-and-torch game

In this bridge-and-torch game, $n$ people are trying to cross a river on a boat that carries at most two people. Each person takes a different amount of time to cross the river alone, and when two people are in the boat together, their combined crossing time is the maximum of their individual crossing times. The idea is that at each step, one or two people will cross the river by boat, and then if not everyone is across, someone (or two someones) will row the boat back.

The usual purpose of this game is, given transit times $0 < t_1 \leq t_2 \leq \ldots \leq t_n$, determine a crossing strategy that minimizes the total amount of time. (In general, the crossing strategy will depend on the exact times: for example, the optimal move sequence for times [1,2,5,10] is different from the optimal move sequence for [1,4,5,10].)

I am not interested in finding optimal solutions to this puzzle. Rather, I think I know a property that characterizes all optimal solution paths, and I am trying to prove that it is true.

Specifically, I think there are three primitive move types such that, for any optimal path, there is an equivalent path which costs the same amount but which is built only using those primitives. I'm looking for a proof that these three primitives are indeed complete—you can never make a strictly cheaper solution than the cheapest solution you can make using these primitives.

The question: Proving a conjecture about optimal solutions

Now, I suspect that the following is true:

Let the people be indexed in order from fastest to slowest, and let the notation $(a,b)$ mean a move in which person $a$ and person $b$ travel together.

Conjecture: For all $n>1$, and for any fixed choice of timing values $t_1\leq \ldots \leq t_n$, you can always make an optimal strategy out of the following three primitive move sequences. The first is a quick escort $(1, k), (1)$---where the fastest person takes some other person across and returns. The second is a one-two ratchet (1,2), (1), $(k,\ell)$,(2), where the first and second fastest people work together to get two slower people $k,\ell$ across in a timely manner. The third is a finishing move (1,2), where the fastest two people cross and don't return, completing the solution.

I have been struggling to prove this. I'd like some help with how I might approach it—perspectives, hints, and insights are much more useful to me than full solutions, as I'd enjoy figuring out most of the proof myself.

My basic approach has been to prove various necessary properties of optimal strategies (such as the fact that in an optimal strategy, the return boat is always piloted by one person, never two) and attempt to show that any candidate strategy that satisfies these necessary properties can be converted, by surgery, into a strategy made up of only escorts and ratchets, in a way that can never raise the cost.

I have also attempted to tally the different properties of my proposed strategy (each person except the two fastest travel rightward exactly once and never return, and the sum of the number of times the fastest two people travel rightward is $n$) and compare them against the properties of all other candidate strategies to show that mine is faster—but it's difficult to turn such aggregated tallies into crossing costs because of that "max" property.

In contrast, I am looking for a (1) proof that (2) my particular primitives---ratchets and escorts---(3) suffice to build an optimal solution no matter what the setup is.

In fact, I had already written a search algorithm which, given $n$, finds the set of all minimal path costs. These minimal path costs are represented as linear combinations of the individual crossing times.

For example, when $n=4$, the program finds $2t_1 + t_2 + t_3 + t_4$ and $t_1 + 3t_2 + 0t_3 + t_4$.

Such minimal path costs are incomparable to one another without knowing the specific values of the crossing times. Given a particular set of transit time values, you can evaluate all of these expressions and whichever evaluates to the lowest number corresponds to the minimal cost solution path.

It was by observing patterns in these cost expressions that I came up with the primitives for this question.

The conjecture is true.

Indeed, you can always obtain an optimal strategy by iteratively sending the two slowest people across, using a ratchet (1,2),(1),(p,q),(2) or a pair of quick escorts (1,p),(1),(1,q),(1), whichever is faster. When only three people remain, you finish the puzzle with escorts: (1,3),(1),(1,2).

A graph-based solution

Solution adapted from Crossing the Bridge at Night, Günter Rote

Defining the graph. In reasoning about the proof, a key trick is to represent each candidate solution as a graph rather than a sequence of moves. To represent a solution involving $n$ people, use a graph with vertices $1\ldots n$, and a distinct edge $i-j$ for each time $i$ and $j$ travel together. This unordered representation abstracts away from messy problems of interleaving.

The total trip cost can be read off the graph

You can prove that, in an optimal solution, the boat always carries two people going forward and one person going back. This means that in the graph of an optimal solution, the edges correspond exactly to the forward trips.

This gives us a way to calculate the total trip cost from the graph. Let's suppose we have the graph of an optimal solution. Then:

1. The edges of the graph correspond to the forward trips.

2. Hence the number of forward trips that $k$ makes is equal to the degree of vertex $k$.

3. In any complete solution, each person travels forward exactly one more time than they travel back. Hence the number of $k$'s return trips is one less than the degree of vertex $k$.

4. Hence, suppose we have a problem involving $n$ people with travel times $t_1,\ldots,t_n$. Given a graph representation of an optimal solution, the total cost $C$ of the solution can be computed from the vertices $V$ and edges $E$ as: $$C \equiv \sum_{\langle i, j\rangle \in E} \max{(t_i,t_j)} + \sum_{k \in V} (\deg{(k})-1) t_k$$ The first term represents forward trips and the second term represents backward trips. (Note that if there are multiple edges between $i$ and $j$, they count multiple times in this sum.)

5. Of course, instead of counting the degree separately, we could fold it into our sum over edges. Hence another way to write the cost $C$ of the solution is: $$C \equiv \sum_{\langle i, j\rangle \in E} \left[\max{(t_i,t_j) } + t_i + t_j \right] - \sum_{k\in V} t_k$$ Note that this second term doesn't depend on the choice of solution; it's just the sum of everyone's individual travel times. Hence we'll minimize cost $C$ if we minimize this first term.

Cost-cutting surgery on optimal solutions In this section, we will start with a graph representing a candidate solution. I will introduce several graph transformations that will convert the graph into one with a ~lower cost, while preserving the number of edges. Although we will have no prior guarantee that the resulting transformed graph will correspond to a realizable, actual sequence of moves across the river, I will prove in the end that it does. In fact, the transformed graph can always be realized as a sequence of ratchets and escorts; this will complete the proof.

Let's start with the graph of a candidate solution. We'll prove that this solution is either suboptimal, or that it can be transformed without raising its cost.

1. Fixed number of edges. We know that in an optimal solution, the boat takes two people across each time and one person back. Hence an optimal solution for $n\geq 2$ people must end in exactly $2n-3$ steps—$(n-1)$ going forward, and $(n-2)$ going back.

   We can therefore assume that this graph has exactly $n-1$ edges.

2. Let the fastest people escort. Let $e$ be any edge that shares a vertex $v$ with another edge. If the shared edge $v=1$ or if both edges are equal to $\langle 1,2\rangle$, we'll leave them alone. Otherwise, we can always reroute $e$ so that instead of going to vertex $v$, it goes to vertex 1 or 2 instead, lowering the total cost of this solution.

   When you apply this process repeatedly, to exhaustion, you convert the graph into one with the following properties: (1) If two edges have exactly one vertex $v$ in common, that vertex is $v=1$. (2) If two edges are parallel—that is, they have two vertices in common— then those edges are $\langle 1,2\rangle$. Hence in this transformed graph, (3) Each vertex has degree one, except perhaps vertices 1 and 2.

   In terms of boat trips, these properties translate into a solution where (1) Each person makes exactly one trip across the river, except perhaps the two fastest people "1" and "2". (2) Although the second-fastest person "2" can make multiple trips across the river, that person only travels with the fastest person. (3) Hence the only person who escorts multiple different people across the river is the fastest person "1".

   Hence

   Each person $k>2$ travels across the river exactly once, either with the fastest person (1,k) or with some other $\ell>2$, (k,l).

3. Reassign pairs Pick any two edges with no vertices in common. Without loss of generality, say the vertices are $i < j < k < \ell$. Observe that out of all possible ways the edges might be arranged, you'll get the lowest cost if the edges are $i-j$ and $k-\ell$; therefore, arrange the edges to be $i-j$ and $k-\ell$.

   In terms of boat trips, this means that whenever you have four distinct people in two boat trips, the two fastest and two slowest people are paired up.

4. Here's an interesting consequence: Each person $k>2$ travels across the river exactly once, either with the fastest person (1,k) or with some other $\ell>2$, (k,l). Now suppose $a$ is a person who is escorted (1,a), and $b$ is a person who travels with someone else, (b,c). As a result of our pair-swapping transformation above, we must have that $a<b$ and $a<c$. This means that in this graph, all the escorted people are faster than the paired-up people.

We have transformed the graph, preserving the number of edges and preserving (or lowering) the total cost. But is the result even realizable anymore as a sequence of moves?

The streamlined solution can be realized using ratchets and escorts

We have to show that this transformed graph can be realized as an ordered list of trips across the river— more specifically, we want to show that it can be realized as a sequence of ratchets and escorts. This will establish that for every candidate solution, there is a cheaper (no-more-expensive) solution in terms of ratchets and escorts, which was to be shown.

Indeed, let's tally up the edges. There are $n-1$ in total. Consider the people k>2. Each of them travels across the river exactly once. Some of them are paired up the fastest person, (1,k). Call these escort-type edges. Others are paired up with someone else l>2, (k,l). Call these ratchet-type edges.

• There are $n$ people and $n-1$ edges in total.
• Let $m$ denote the number of ratchet-type edges.
• Then there are $n-2m-2$ escort-type edges. This is because there are $n-2$ people besides 1 and 2, and $2m$ of them have a trip already accounted for by a ratchet edge.
• This leaves $m + 1$ edges: we started with $n-1$ edges and have accounted for $m$ ratchet-type edges and $n-2m-2$ escort-type edges. All the remaining edges must be of type (1,2).

You can see how any such trip can be realized as a sequence of moves using $m$ ratchets (1,2),(1),(p,q),(2) and $n-2m-2$ escorts (1,p) (their order doesn't matter), finishing with a final (1,2). Q.E.D.

Qualitatively, it turns out that a ratchet is better for slower people, and an escort is better for faster people. In fact, the cutoff time, $\Delta \equiv 2t_2 - t_1$ determines numerically which is better: Suppose you're sending (p,q) across the river. If neither individual could cross the river in time $\Delta$, you're better off with a ratchet. Otherwise, you're better off with two quick escorts. Hence the strategy above, which considers the slowest people first, will generally start by sending people using ratchets, then eventually transition to sending people using escorts.

As for the proof that in an optimal solution, two people travel forward and one person travels back:

1. Use the notation $+\{a,b\}$ to mean $a$ and $b$ travel forward, and $-\{a,b\}$ to mean $a$ and $b$ travel back. Given a sequence of moves, consider the first place where it deviates from the pattern of "two forward, one back".

2. Suppose the first deviation is that one person travels forward $+\{a\}$. This cannot be the first move in an optimal solution, because the return trip would make a loop. Therefore, there must have been a return move, just before this: $-\{b\}$. And note that $a\neq b$ to avoid a loop. Before $b$ returned, one of the following must have happened most recently: $a$ returning, or $b$ setting out with someone. In either case, we can simplify the path, lowering its cost. If the path looked like this, we transform it like that: $$\ldots +\{b,c\}, \ldots, +\{a\}, -\{b\} \Longrightarrow \ldots +\{a,c\}, \ldots, \emptyset, \emptyset$$ $$\ldots -\{a\}, \ldots, +\{a\}, -\{b\} \Longrightarrow \ldots -\{b\}, \ldots, \emptyset, \emptyset$$ Both of these adjustments strictly lower the cost.

3. Suppose the first deviation is that two people travel back. Then find which one of them traveled forward most recently and you can safely delete them from that entire round trip: $$+\{a,c\}, \ldots, -\{a,b\} \Longrightarrow +\{c\}, \ldots, -\{b\}$$

The main point is convincing yourself that these adjustments preserve the legality of all the moves, e.g. don't end up trying to move someone who isn't on the proper side.