Ten women sit in seats in a line. All of the get up and then reseat themselves using all 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
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, 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.