2024 AMC 10B Problem 20

P16-20~7 minPrint

Arrangements with Restrictions Split into exhaustive cases and handle each Exploit symmetry to reduce work or pair up objects

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?

Show solution without answering

Key insight

A left shoe next to a right shoe must be its own mate. First find the allowed left-right patterns, then see which pairs are forced into place.

Solution

Call the pairs $A$ , $B$ , $C$ , with shoes $A_L, A_R$ and so on. First decide which spots hold left shoes (L) and which hold right shoes (R). Then place the actual shoes.

Step 1: which L/R patterns are allowed?

1. Wherever an L sits next to an R, those two shoes must be a pair.
2. A shoe has only one mate. So a shoe cannot have an opposite-type shoe on both sides. The patterns $LRL$ and $RLR$ can never appear.
3. List the patterns of three L's and three R's that avoid $LRL$ and $RLR$ :
- Split once: $LLLRRR$ , $RRRLLL$ .
- Split twice: $LLRRRL$ , $LRRRLL$ , $RRLLLR$ , $RLLLRR$ .
- Split three times: $LRRLLR$ , $RLLRRL$ .

That is $8$ patterns.

Step 2: place the shoes. Every place where L meets R must hold a matching pair.

Split once, like $LLLRRR$ . The pair at the meeting point (spots $3$ and $4$ ) can be any of $3$ pairs. The other two left shoes fill spots $1$ and $2$ in $2$ ways, and the other two right shoes fill spots $5$ and $6$ in $2$ ways. That is $3 \cdot 2 \cdot 2 = 12$ ways. With $2$ such patterns: $24$ .
Split twice, like $LLRRRL$ . The two meeting points (spots $2$ – $3$ and $5$ – $6$ ) need two different pairs: $3 \cdot 2 = 6$ ways. The last pair must fill spots $1$ and $4$ , which are an L spot and an R spot, in $1$ way. That is $6$ ways. With $4$ such patterns: $24$ .
Split three times, like $LRRLLR$ . The three meeting points (spots $1$ – $2$ , $3$ – $4$ , $5$ – $6$ ) each take a whole pair, in $3 \cdot 2 \cdot 1 = 6$ ways. With $2$ such patterns: $12$ .
Total: $24 + 24 + 12 = 60$ .

The answer is $\boxed{\textbf{(A)}\ 60}$ .

Why this works

Break a lineup problem into two layers: first the rough pattern (left or right), then the exact shoes. The rule rules out many rough patterns right away, and in the ones that are left it forces certain pairs to sit together. Counting each layer separately is much easier than handling all six shoes at once.

Alternative approach

Build the row from the left. The first shoe can be any of $6$ , and by symmetry each choice leads to the same number of rows. Say it is $A_R$ .

If the second shoe is $A_L$ : the third must be another left shoe, $B_L$ or $C_L$ ( $2$ ways). Say $B_L$ . Then the row ends $B_R, C_R, C_L$ or $C_L, C_R, B_R$ : $2$ ways. That gives $2 \cdot 2 = 4$ .
If the second shoe is another right shoe, $B_R$ or $C_R$ ( $2$ ways), say $B_R$ . Then either $B_L, A_L, C_L, C_R$ follows ( $1$ way), or $C_R, C_L$ follows and then $A_L, B_L$ in either order ( $2$ ways). That gives $2 \cdot 3 = 6$ .

So each first shoe leads to $4 + 6 = 10$ rows, and the total is $6 \cdot 10 = 60$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Record each position as $L$ or $R$ . Whenever an $L$ and an $R$ are adjacent they must be mates. Since a shoe has only one mate, no shoe can be adjacent to two shoes of the opposite type: the patterns $LRL$ and $RLR$ cannot appear anywhere. Equivalently, every run of identical letters that is not at an end of the row has length at least $2$ .

With three $L$ 's and three $R$ 's, the allowed patterns are:
- one boundary: $LLLRRR$ , $RRRLLL$ ;
- two boundaries: $LLRRRL$ , $LRRRLL$ , $RRLLLR$ , $RLLLRR$ ;
- three boundaries: $LRRLLR$ , $RLLRRL$ .

Now assign actual shoes. Each $L$ – $R$ boundary forces the two shoes on either side to be a pair.

One boundary (2 patterns): pick the pair straddling the boundary ( $3$ ways). The other two left shoes fill the remaining $L$ slots in $2$ ways, the other two right shoes fill the remaining $R$ slots in $2$ ways: $3 \cdot 2 \cdot 2 = 12$ per pattern.
Two boundaries (4 patterns): the two boundaries use two different pairs ( $3 \cdot 2 = 6$ ways to assign them), and the third pair's shoes fill the two remaining slots, one $L$ and one $R$ , in exactly $1$ way: $6$ per pattern.
Three boundaries (2 patterns): each boundary holds a whole pair, assigned in $3! = 6$ ways: $6$ per pattern.

Total: $2 \cdot 12 + 6 \cdot 6 = 24 + 36 = 60$ .

The answer is $\boxed{\textbf{(A)}\ 60}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
Prealgebra, Chapter 14: Counting (§14.3)