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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum