2008 iTest Problems/Problem 97

From AoPSWiki

Problem

(storyline deleted) Let $k$ be the number of students in a circle. Then let $m$ 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 $m$ leaves a remainder of $1$ when divided by $5$ , how many possible values are there of $k$ , where $k$ is at least $3$ and at most $2008$ ?

Solution

We first consider the following related problem: How many ways are there to rearranged $n$ students in a line, where each student can either not move or move to one spot of where that student srated? Let $L_n$ be the number of ways to do so with $n$ students. Then, if we add a $n+1$ 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 $n$ students (or $L_n$ ); 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 $L_{n-1}$ ways to rearrange the remaining $n-1$ students. Thus, we have the recursion

$L_{n+1} = L_n + L_{n-1}$

and $L_1 = 1, L_2 = 2$ . Hence $L_n = F_{n-1}$ where $F_n$ is the Fibonacci sequence, defined with $F_1 = F_2 = 1$ .

Returning to the original problem, suppose we have $n$ students arranged in a circle. We now add a $n+1$ th student anywhere in the circle. If that student remains still, then there are simply $L_n$ ways to rearrange the other $n$ 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 $2$ ), the remaining $n-1$ students can be rearranged in $2L_{n-1}$ ways. Finally, if all of the students shift to their left or right, there are two ways. Hence, the number of ways to rearrange $n$ students is $C_n = L_n + 2L_{n-1} + 2 = F_{n-1} + 2F_{n-2} + 2$ .