Maths Olympiad Prep

Library / /404 of 520

Combinatorics Difficulty 3.6 AMC 10/12 Find the answer

Ten women sit in 1010 seats in a line. All of the 1010 get up and then reseat themselves using all 1010 seats, each sitting in the seat she was in before or a seat next to the one she occupied before. In how many ways can the women be reseated?

Pick one

Solution

Notice that either a woman stays in her own seat after the rearrangement, or two adjacent women swap places. Thus, our answer is counting the number of ways to arrange 1x1 and 2x1 blocks to form a 1x10 rectangle. This can be done via casework depending on the number of 2x1 blocks. The cases of 0, 1, 2, 3, 4, 5 2x1 blocks correspond to 10, 8, 6, 4, 2, 0 1x1 blocks, and so the sum of the cases is
(100)+(91)+(82)+(73)+(64)+(55)=1+9+28+35+15+1=89.\binom{10}{0} + \binom{9}{1} + \binom{8}{2} + \binom{7}{3} + \binom{6}{4} + \binom{5}{5} = 1 + 9 + 28 + 35 + 15 + 1 = \boxed{89}.

Solution 1 Shortcut
Recall that the number of ways to arrange 1x1 and 2x1 blocks to form a 1xn rectangle results in Fibonacci numbers. Clearly, 89\boxed{89} is the only fibonacci number, so no calculation is needed for this problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.