Answer to Question #6389 in Combinatorics | Number Theory for David T

Question

Ten women are fishing all in a row in a 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 person can move from her seat to the next empty seat or she can step over one person without capsizing the boat. What is the minimum number of moves needed for the five women in front to change places with the five women in back?
_1 _2 _3 _4 _5 __ _6 _7 _8 _9 _10

Answer 1

Initial position:

_1 _2 _3 _4 _5 __ _6 _7 _8 _9 _10

Move 5 to the
most right place (10 steps):

_1 _2 _3 _4 __ _5 _6 _7 _8 _9 _10
_1 _2
_3 _4 _6 _5 __ _7 _8 _9 _10
_1 _2 _3 _4 _6 __ _5 _7 _8 _9 _10
_1 _2 _3
_4 _6 _7 _5 __ _8 _9 _10
_1 _2 _3 _4 _6 _7 _5 _8 __ _9 _10

_1 _2 _3
_4 _6 _7 __ _8 _5 _9 _10
_1 _2 _3 _4 _6 _7 _8 __ _5 _9 _10
_1 _2 _3 _4
_6 _7 _8 _9 _5 __ _10
_1 _2 _3 _4 _6 _7 _8 _9 _5 _10 __
_1 _2 _3 _4 _6
_7 _8 _9 __ _10 _5

Move 7 to the most left place (+10 steps)

_1
_2 _3 _4 _6 _7 __ _9 _8 _10 _5
_1 _2 _3 _4 __ _7 _6 _9 _8 _10 _5
_1 _2
_3 _4 _7 __ _6 _9 _8 _10 _5
_1 _2 _3 __ _7 _4 _6 _9 _8 _10 _5
_1 _2 _3
_7 __ _4 _6 _9 _8 _10 _5

_1 _2 __ _7 _3 _4 _6 _9 _8 _10 _5
_1 _2 _7
__ _3 _4 _6 _9 _8 _10 _5
_1 __ _7 _2 _3 _4 _6 _9 _8 _10 _5
__ _1 _7 _2
_3 _4 _6 _9 _8 _10 _5
_7 _1 __ _2 _3 _4 _6 _9 _8 _10 _5

Move 4 to the
most right place before 5 (+8 steps)

_7 _1 _3 _2 __ _4 _6 _9 _8 _10
_5
_7 _1 _3 _2 _6 _4 __ _9 _8 _10 _5
_7 _1 _3 _2 _6 __ _4 _9 _8 _10
_5
_7 _1 _3 _2 _6 _9 _4 __ _8 _10 _5
_7 _1 _3 _2 _6 _9 __ _4 _8 _10
_5

_7 _1 _3 _2 _6 _9 _8 _4 __ _10 _5
_7 _1 _3 _2 _6 _9 _8 _4 _10 __
_5
_7 _1 _3 _2 _6 _9 _8 __ _10 _4 _5


Move 6 to the most left
place after 7 (+6 steps)
_7 _1 _3 _2 _6 __ _8 _9 _10 _4 _5
_7 _1 _3 __
_6 _2 _8 _9 _10 _4 _5
_7 _1 _3 _6 __ _2 _8 _9 _10 _4 _5
_7 _1 __ _6 _3
_2 _8 _9 _10 _4 _5
_7 __ _1 _6 _3 _2 _8 _9 _10 _4 _5
_7 _6 _1 __ _3 _2
_8 _9 _10 _4 _5


Move 2 to the most right place before 4 (+5
steps)

_7 _6 _1 _3 __ _2 _8 _9 _10 _4 _5
_7 _6 _1 _3 _8 _2 __ _9 _10
_4 _5
_7 _6 _1 _3 _8 _9 _2 __ _10 _4 _5
_7 _6 _1 _3 _8 _9 _2 _10 __ _4
_5
_7 _6 _1 _3 _8 _9 __ _10 _2 _4 _5



Move 8 to the most left
place after 6 (+3 steps)

_7 _6 _1 _3 _8 __ _9 _10 _2 _4 _5
_7 _6 _1
__ _8 _3 _9 _10 _2 _4 _5
_7 _6 __ _1 _8 _3 _9 _10 _2 _4 _5


Move 3
to the most right place before 2 (+4 steps)

_7 _6 _8 _1 __ _3 _9 _10 _2
_4 _5
_7 _6 _8 _1 _9 _3 __ _10 _2 _4 _5
_7 _6 _8 _1 _9 _3 _10 __ _2 _4
_5
_7 _6 _8 _1 _9 __ _10 _3 _2 _4 _5

final moves (+4
steps)

_7 _6 _8 __ _9 _1 _10 _3 _2 _4 _5
_7 _6 _8 _9 __ _1 _10 _3 _2
_4 _5
_7 _6 _8 _9 _10 _1 __ _3 _2 _4 _5
_7 _6 _8 _9 _10 __ _1 _3 _2 _4
_5


Total number of steps: 10+10+8+6+5+3+4+4 = 50 steps