# [seqfan] River Crossing Puzzle (Flash)

Creighton Kenneth Dement creighton.k.dement at mail.uni-oldenburg.de
Fri Jan 8 16:22:15 CET 2010

```Dear Seqfans,

The "River Crossing Game" (which I found located about halfway down the
page at the following link http://brainden.com/crossing-river.htm )
is a neat little puzzle that seems to, at least initially, boggle the mind
to think that a solution is possible. Unfortunately, I have no idea
whether this problem is equivalent to other famous or well-studied
problems.

*********

You must transfer all the people across the river in this flash game
respecting the following rules:

1. The ferry can carry no more than 2 people.
2. Only the adults (mom, dad and policeman) can operate the ferry.
3. Dad can not be in the presence of the girls w/out Mom
4. Mom can not be in the presence of the boys w/out Dad
5. The thief can not be alone with any of the family w/out the policeman.

*********

Surely there are more than a few ways to "milk" an interesting number
sequence out of that puzzle. I'm open to any suggestions for improvements
to my own. The first 3 sequences (a(n)), (b(n)), (c(n)) that come to mind
for me are:

To calculate the n-th term of the above sequences, start with n mothers, n
fathers, n police officers, n thieves, 2*n daughters and 2*n brothers on
one side of the river. Define a(n) as the least number of times the
raft/ferry must cross to get all 8*n people to the other side (It seems to
be an easy exercise to show that this number exists for all n based on the
fact that a(1) exists).

Let b(n) be the least number of times the raft can cross with two people
on board which leads to all 8*n people getting to the other side.
Similarly, let c(n) be the least number of times the raft can cross with
one person on it which leads to all 8*n people getting to the other side.

To make sure everything is well-defined, I suggest extending the rules as
follows:

*********

1. The ferry can carry no more than 2 people.
2. Only the adults (moms, dads and policemen) can operate the ferry.
3. A dad can not be in the presence of any girls w/out at least one mom.
4. A mom can not be in the presence of any boys w/out at least one dad.
5. A thief can not be alone with any of the family w/out at least one
policeman.

*********

Is b(n) always equal to the number of times two people crossed on the raft
in a solution of a(n)? Stated differently, is a(n) = b(n) + c(n)?

If it turns out that, based on a simple strategy, all the above sequences
are somehow trivial to calculate, then I assume all we are left with is a
nifty little puzzle.

Sincerely,
Creighton

```