# Mean and Median in a Classic River Crossing Problem

Consider the following classic problem:

Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the time it takes to get across will be the time preferred by the slower occupant. The time preferences are: $1, 2, 5$ and $10$ minutes. What is the minimal amount of time in which you can get all four people across the river, where an eastbound trip must have two occupants and a westbound trip must have one occupant?

Answer: $17$ minutes. (Though many mistakenly believe it is $19$ minutes.)

Question 1: If you look at all possible ways of ferrying these four people across the river, subject to the above constraints, what would the average (mean and median) times be?

Question 2: What if you replace the time preferences with $x_1, x_2, x_3$ and $x_4$ minutes?

Question 3: What if you have time preferences $x_1, \ldots, x_n$ minutes for $n$ people, respectively?

Probably the easiest way to broach Question 1 would be to write a quick program to compute the answer, and perhaps doing this for several different time preferences would give some insight into the mean and median in the general four person case. I'm not quite sure how I would start thinking about the general $n$ person case; perhaps by solving it for $n = 1, 2, 3, 4$.

Answers (even partial ones) to any or all of my questions would be greatly appreciated!

• I count 108 protocols for $n=4$, so it shouldn't be too hard to find answers for that case. – Gerry Myerson Nov 6 '12 at 5:18
• 6 ways to choose the 1st eastbound, 2 ways the 1st westbound, 3 ways the 2nd eastbound, 3 ways the 2nd westbound; $6\times2\times3\times3=108$. – Gerry Myerson Nov 6 '12 at 6:08
• The mean should be calculable without going through case by case. You have $108$ total "journeys" each journey involves three eastbound trips occupied by two people. This gives a total of $324$ eastbound trips. By symmetry, we expect each pair of passengers to have the same number of trips as a whole, so each pair takes $324/6 = 54$ trips together. Since the slow ones dominate, we have a total time of $3\times 10 \times 54 + 2\times 5 \times 54 + 2 \times 54$ for eastbound trips over all possible journeys. The same analysis can be done for westbound. The average comes out to be $30$ minutes. – EuYu Nov 6 '12 at 7:08
• Even though it is not the question, I want to point out this interesting article how to find the solution for the generalized problem. – A.Schulz Nov 9 '12 at 12:58

Using @EuYu idea that fixing a single trip (eg. the third trip) each subset of the right cardinality have the same probability, you can write the average traversing time as: $$E[time] = E[one person trip] * N[one person trip] + E[two person trip] * N[one person trip]$$ and you know that: $$N[one person trip]=N-2$$ $$E[one person trip]=\frac{\sum_i x_i}{N}$$ $$N[two person trip]=N-1$$ $$E[two person trip]=\frac{\sum_{i,j} min(x_i,x_j)}{N*(N-1)/2}=\frac{\sum_i(x_i*(i-1))}{N*(N-1)/2}$$
For example, for the case $N=4$ and $x_i=1,2,5,10$, you have 2 one person trip with a mean time of $(1+2+5+10)/4=18/4=4.5$, 3 two person trip with a mean of $(1*0+2*1+5*2+10*3)/(4*3/2)=42/6=7$ for a total expected time of $2*4.5+3*7=30$.
There are $N!(N-1)!^2/2^{N-1}$ different schedules. The average for the generalized problem has already been calculated in carlop's answer. I suspect that calculating the median for the generalized problem in closed form is intractable. Here's code that checks the average of $30$ and determines the median. The time taken for the schedule just below the middle is $27$, the time taken for the schedule just above the middle is $30$. According to the usual definition of the median of an even number of numbers as the mean of the two central ones, the median is therefore $28\frac12$.