7
$\begingroup$

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!

  • 2
    Even though it is not the question, I want to point out [this interesting article](http://www.inf.fu-berlin.de/inst/ag-ti/uploads/tx_tipublications/Crossing_the_bridge_at_night.pdf) how to find the solution for the generalized problem.2012-11-09

2 Answers 2

2

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[ \text{time} ] = E[ \text{one person trip} ] * N[ \text{one person trip} ] + E[ \text{two person trip} ] * N[ \text{one person trip} ]$$ and you know that: $$N[ \text{one person trip} ]=N-2 \\ E[ \text{one person trip} ]=\frac{\sum_i x_i}{N} \\ N[ \text{two person trip} ]=N-1 \\ E[ \text{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$.

This method works for the mean, for other statistic (like the median) I think a computational approach should be used.

2

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$.