Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 iTest Problems/Problem 97"

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

Latest revision as of 12:29, 20 October 2019

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 rearrange $n$ students in a line, where each student can either not move or move to one spot of where that student started? 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$.

Then, $C_n$ itself satisfies the recursion $C_{n+1} = F_{n} + 2F_{n-1} + 2$ $= (F_{n-1} + 2F_{n-2} + 2) + (F_{n-2} + 2F_{n-3} + 2) - 2$ $= C_{n} + C_{n-1} - 2$, with $C_3 = 6, C_4 = 9$. Then $C_n$ cycles $\mod{5}$ as $\{C_n\} \equiv 1,4,3,0,1,4 \cdots \pmod{5}$, so we require that $k \equiv 3 \pmod{4}$. There are $\boxed{502}$ such values from $3 \le k \le 2008$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_iTest_Problems/Problem_97&oldid=110475"