23. C3 (GBR) A biologist watches a chameleon. The chameleon catches flies and rests after each catch. The biologist notices that:
(i) the first fly is caught after a resting period of one minute;
(ii) the resting period before catching the $2 m$ th fly is the same as the resting period before catching the mth fly and one minute shorter than the resting period before catching the $(2 m+1)$ th fly;
(iii) when the chameleon stops resting, he catches a fly instantly.
(a) How many flies were caught by the chameleon before his first resting period of 9 minutes?
(b) After how many minutes will the chameleon catch his 98 th fly?
(c) How many flies were caught by the chameleon after 1999 minutes passed?
23. Let $r(m)$ denote the rest period before the $m$ th catch, $t(m)$ the number of minutes before the $m$ th catch, and $f(n)$ as the number of flies caught in $n$ minutes. We have $r(1)=1, r(2 m)=r(m)$, and $r(2 m+1)=f(m)+1$. We then have by induction that $r(m)$ is the number of ones in the binary representation of $m$. We also have $t(m)=\sum_{i=1}^{m} r(i)$ and $f(t(m))=m$. From the recursive relations for $r$ we easily derive $t(2 m+1)=2 t(m)+m+1$ and consequently $t(2 m)=2 t(m)+m-r(m)$. We then have, by induction on $p, t\left(2^{p} m\right)=2^{p} t(m)+p \cdot m \cdot 2^{p-1}-\left(2^{p}-1\right) r(m)$.
(a) We must find the smallest number $m$ such that $r(m+1)=9$. The smallest number with nine binary digits is $\overline{11111111}_{2}=511$; hence the required $m$ is 510 .
(b) We must calculate $t(98)$. Using the recursive formulas we have $t(98)=$ $2 t(49)+49-r(49), t(49)=2 t(24)+25$, and $t(24)=8 t(3)+36-7 r(3)$. Since we have $t(3)=4, r(3)=2$ and $r(49)=r\left(110001_{2}\right)=3$, it follows $t(24)=54 \Rightarrow t(49)=133 \Rightarrow t(98)=312$.
(c) We must find $m_{c}$ such that $t\left(m_{c}\right) \leq 1999<t\left(m_{c}+1\right)$. One can estimate where this occurs using the formula $t\left(2^{p}\left(2^{q}-1\right)\right)=(p+$ $q) 2^{p+q-1}-p 2^{p-1}-q 2^{p}+q$, provable from the recursive relations. It suffices to note that $t(462)=1993$ and $t(463)=2000$; hence $m_{c}=462$.