Question

A game board consists of 64 squares that alternate in color between black and white. The figure below shows square $P$ in the bottom row and square $Q$ in the top row. A marker is placed at $P$. A step consists of moving the marker onto one of the adjoining white squares in the row above. How many 7-step paths are there from $P$ to $Q$ ? (The figure shows a sample path.)

Answer 1

9514 1404 393

Answer:

A) 28

Explanation:

Of the seven moves, 3 must be to the left, and 4 must be to the right. That is, we end up exactly one space right of where we started, so there must be exactly one more move to the right than to the left.

The number of permutations of LLLRRRR is 7!/(4!·3!) = 35. Of those, several must be eliminated, because they result in a path that goes off the right side of the board.

The discounted sequences are ...

• LRRRRLL
• RLRRRLL
• RRLRRLL
• RRRLLLR
• RRRLLRL
• RRRLRLL
• RRRRLLL"

With these 7 possibilities eliminated from the list, there are 35 -7 = 28 possible paths from P to Q.