SAT1000 - P928

The sequence the girls yell is called the Fibonacci sequence . Study the numbers divisible by three in the sequence. $1,1,2,\color{#D61F06}3\color{#333333},5,8,13,\color{#D61F06}21\color{#333333},34,55,89,\color{#D61F06}144...$ We see that there is a period of 4. Since $\text{LCM} (4,5)=20$ and her first clap will be on the sixteenth number, Alice will clap at the $16,36,56,76,96^{th}$ times. Hence the answer is $\boxed{5}.$

The numbers yelled by the five girls are the Fibonacci numbers $F_n = F_{n-1} + F_{n-2}: 1, 1, 2, \boxed{3}, 5, ...$ \[ \begin{align} F_n &= \textcolor{blue}{F_{n-1} }+ F_{n-2} = \textcolor{blue}{(F_{n-2} + F_{n-3} )} + (F_{n-3} + F_{n-4}) \\ &= \textcolor{blue}{(F_{n-3} + F_{n-4} + F_{n-3} )} + (F_{n-3} + F_{n-4}) \\ &= 3F_{n-3} + 2F_{n-4} \\ \therefore F_n &\cong 2 \cdot F_{n-4} \pmod 3

\end{align} \]

The first number is divisible by $3$ at $4^{th}$ position,

In $\{F_1, F_2, F_3, F_4\}$ , only $F_4$ is divisible by 3. Therefore, only $F_{4n}$ is divisble by $3$ for any positive integer $n$ .

Within first $100^{th}$ number, Alice starts at the $1^{st}$ position and repeat at $(1+5m)$ position where $m = 0, 1, 2....,19$ .

Alice yells at $(1+5m)$ position and she claps also when m $\cong 3 \pmod 4$ where $m = 0, 1, 2....,19$ .

There are $5$ such $m = \{3, 7, 11, 15, 19\}$ corresponding to $F_{16}, F_{36}, F_{56}, F_{76}, F_{96}$ . So, she clapped $\boxed{5}$ times.

The numbers yelled by the five girls are the Fibonacci numbers $F_n$ . Alice yells $F_1$ , Betty yells $F_2$ , Cathy yells $F_3$ and so on. We note hat $F_n$ is divisible by $3$ , when $n$ is divisible by $4$ or in modular arithmetic , $F_n \equiv 0 \text{ (mod 3)}$ when $n \equiv 0 \text{ (mod 4)}$ . Since Alice is the first to yell, her sequence of yelling is given by $5k+1$ , where $k = 0, 1 , 2, \cdots$ . And she needs to clap when:

$\begin{aligned} 5k + 1 & \equiv 0 \text{ (mod 4)} \\ k + 1 & \equiv 0 \text{ (mod 4)} \\ k & \equiv -1 \equiv 3 \text{ (mod 4)} \\ \implies k & \equiv 4\blue m + 3 & \small \blue{\text{where }m = 0, 1, 2, \cdots} \end{aligned}$

So Alice claps when $n = 5k+1 = 5(4m + 3) + 1 = 20m + 16$ , where $20m + 16 \le 100$ , $\implies m \le 4$ . Therefore Alice claps $\boxed 5$ times, when $m=0, 1, 2, 3, 4$ for $F_{16}, F_{36}, F_{56}, F_{76}, F_{96}$ .