Problem:
Three different pairs of shoes are placed in a row so that no left shoe is next to a right shoe from a different pair. In how many ways can these six shoes be lined up?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
There are arrangements of the letters LLLRRR representing the positions of 3 left shoes and 3 right shoes in the row of 6 shoes. Of the 20 , any sequence containing LRL or RLR will violate the condition given in the problem. There are 8 arrangements that avoid these two sequences. Call a pair of shoes matched if the 2 shoes in the pair are next to each other. There are three sets of possibilities.
Thus there are arrangements satisfying the conditions of the problem.
Label the shoes and for . By symmetry it suffices to count the number of arrangements with first in line and multiply by 6 . There are 2 choices for a left shoe coming next, say
, after which the only continuations are for or 2 , or ; this gives arrangements. Otherwise comes second, followed by either or for or 3 , another arrangements. This gives a total of 10 , so there are ways to line up the six shoes.
Note: Generalized to pairs of shoes, the sequence of answers to this question starts , 17520. This is sequence A096121 in the On-Line Encyclopedia of Integer Sequences, which is listed as counting the number of paths of a rook on a board, where the rook must land on each square exactly once. The sequence satisfies the recurrence .
The problems on this page are the property of the MAA's American Mathematics Competitions