Exchanging Seats in a Boat

Date: 06/08/2001 at 23:10:06
From: Beth
Subject: Problem solving

This is an assignment for bonus points for a class I had at college 
last semester. Several different people tried to solve it by modeling 
it with objects and drawing pictures, but everyone came up with 
different answers (I got 54).  

Here is the problem:

Ten women are fishing in a long, narrow boat. One seat in the center 
of the boat is empty. The five women in the front of the boat want 
to change seats with the five women in the back of the boat. A woman 
can move from her seat to an adjacent empty seat, or she can step over 
one person without capsizing the boat. What is the minimum number of 
moves needed for the ten women to exchange seats?

Date: 06/09/2001 at 00:00:49
From: Doctor Schwa
Subject: Re: Problem solving

Hi Beth,

I'd approach this problem with the strategy of trying an easier 
problem. That is, with zero people in the boat, zero steps are 
required. That was easy! Next, with two people, it takes three steps:
one person moves to the center, then one step over, then the first
person moves to the end.

With four people, it gets a little trickier, but:
ab.cd
a.bcd
acb.d
acbd.
ac.db
.cadb
c.adb
cda.b
cd.ab

seems to be the best way to do it (is it the only way?)
and it takes 8 steps.

I don't see any obvious pattern yet (though +3, +5 makes me wonder if
it's +7 next, so I'll guess 15 steps next).

Let's try six people:
abc.def
ab.cdef
abdc.ef
abdce.f
abd.ecf
a.dbecf
.adbecf
da.becf
daeb.cf
daebfc.
daebf.c
dae.fbc
d.eafbc
de.afbc
defa.bc
def.abc

It is indeed 15 steps, so my guess of the pattern is probably right.  

Now there's the question of whether you can *prove* that pattern ... 
but following my guess, you'll get a number quite a bit smaller than 
54 (assuming my guess is really correct).

I hope that helps. Feel free to write back if you'd like to talk more 
about this problem. For a similar problem with a link to an applet, 
see

  Traffic Jam - Suzanne Alejandre, for the Math Forum
  http://mathforum.org/alejandre/frisbie/student.jam.html   

Enjoy,

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/