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
.