2019 AMC 10C Problems/Problem 22

Problem

$100$ chicks are sitting in a circle. The first chick in the circle says the number $1$, then the chick $2$ seats away from the first chick says the number $2$, then the chick $3$ seats away from the chicken that said the number $2$ says the number $3$, and so on. The process will always go clockwise. Some of the chicks in the circle will say more than one number while others might not even say a number at all. The process stops when the $1001$th number is said. How many numbers would the chick that said $1001$ have said by that point (including $1001$)?


$\mathrm{(A) \ } 20\qquad \mathrm{(B) \ } 21\qquad \mathrm{(C) \ } 30\qquad \mathrm{(D) \ } 31\qquad \mathrm{(E) \ } 41$

Solution

The $n^{th}$ number is said by chick $\frac{n(n+1)}{2} \pmod{100}$. Note that when $n=1001$, the first chick said the number. Thus, we are looking for $\frac{n(n+1)}{2}\equiv{2} \pmod{100}$, or $\frac{(n+2)(n-1)}{2}\equiv{0} \pmod{100}$. This is equivalent to stating that $(n+2)(n-1)\equiv{0} \pmod{8}$ and $(n+2)(n-1)\equiv{0} \pmod{25}$. It is clear that there are $2*2=4$ numbers that the first chick says every $8*25=200$ numbers said by all chicks, so our answer is $4\cdot{1000/200}+1=\boxed{21}$