2008 iTest Problems/Problem 97
Problem
(storyline deleted) Let be the number of students in a circle. Then let be the number of ways they can rearrange ourselves so that each of them is in the same spot or within one spot of where they started, and no two people are ever on the same spot. If leaves a remainder of when divided by , how many possible values are there of , where is at least and at most ?
Solution
We first consider the following related problem: How many ways are there to rearrange students in a line, where each student can either not move or move to one spot of where that student started? Let be the number of ways to do so with students. Then, if we add a st student at the right end, that student can either stay still, for which the number of rearrangements is simply the number of rearrangements for the other students (or ); or that student can move one spot to the left, in which case the second rightmost student must move to the right end, and there are ways to rearrange the remaining students. Thus, we have the recursion
and . Hence where is the Fibonacci sequence, defined with .
Returning to the original problem, suppose we have students arranged in a circle. We now add a th student anywhere in the circle. If that student remains still, then there are simply ways to rearrange the other student (as the two students next to this student cannot move beyond the student). If the student exchanges spots with one of his adjacent neighbors (of which there are ), the remaining students can be rearranged in ways. Finally, if all of the students shift to their left or right, there are two ways. Hence, the number of ways to rearrange students is .
Then, itself satisfies the recursion , with . Then cycles as , so we require that . There are such values from .