Crossing the River Story Problem

Question

A group of adults and children go on a camping trip. On the first day, they come to a river too deep to wade across. They find a small canoe which can carry either one adult or up to two children at a time. The canoe cannot hold one adult and one child at the same time. They only have this one canoe to transport the entire group across the river.

Recall from HoM#3 that when there were A adults, where A is some number, and 2 kids that it took 4A+1 one-way trips to get everyone across the river.

1. What if there are A adults and 3 kids?
2. What if there are A adults and 4 kids?
3. What if there are A adults and an unknown number or kids on the trip? Can you come up with a formula for the fewest number of one-way trips it will take them to get across the river?

Answer 1

Note first that it never makes sense to have an adult return the canoe because that just undoes a trip, so whenever you send anyone across, there has to be a kid available on the far side to return the canoe. Note, too, that the last trip must be made by two kids: whoever brought the canoe back for the last adult has to stay on the starting side while that adult crosses.

So, it takes four trips for each adult that crosses: two to deposit a kid on the far side and bring the canoe back, and another two for the adult to cross and the waiting kid to return the canoe. Once all of the adults are across, it takes one round trip for each kid except the last two to cross. Thus, the minimum number of trips is $4A+2(K-2)+1$.

Finally, note that there must be at least two kids present in order to get everyone across the river.

Answer 2

Note that there are 3 possibilities for the boat when going in either direction: 1 adult, 2 children or 1 child. Except for maybe the last crossing, we will only allow 1 adult or two children to cross and 1 child to come back, because all other possibilities just cancel one of previous moves and hence will certainly not help in getting the least possible amount of one-way trips. So consider

$\alpha$: 2 children cross, 1 child comes back,

$\beta$: 1 adult crosses, 1 child comes back.

Denote by $A_1$ and $C_1$ the number of adults resp. children on the starting side and by $A_2$ and $C_2$ the number of adults resp. children who got across the river. Then $\alpha$ will result in:

$$A_1\rightarrow A_1, C_1\rightarrow C_1-1, A_2\rightarrow A_2, C_2\rightarrow C_2+1.$$

On the other hand, move $\beta$ gives

$$A_1\rightarrow A_1-1, C_1\rightarrow C_1+1, A_2\rightarrow A_2+1, C_2\rightarrow C_2-1.$$

Since in particular we have to move all adults across the river, checking what happens to $C_1$ and $C_2$ implies that to do $x$ times $\beta$, you also need to do $x$ times $\alpha$. So suppose we have $A$ adults and $C$ children to start with, then among the moves we need $A$ times $\beta$ and $A$ times $\alpha$. These moves result in

$$A_1\rightarrow A_1-A, C_1\rightarrow C_1, A_2\rightarrow A_2+A, C_2\rightarrow C_2.$$

After that (or in between) you still need to get the remaining children across the river, which is only possible by subsequent applications of $\alpha$ and 1 last crossing with only the last child.

Noting that both $\alpha$ and $\beta$ take two one-way trips, we conclude: If you want to bring $A$ adults and $C$ children across the river, you need $4A+2C-1$ one-way trips.