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 $m$ th 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 98th 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(2m) = r(m) \), and \( r(2m+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(2m+1) = 2t(m) + m + 1 \) and consequently \( t(2m) = 2t(m) + m - r(m) \). We then have, by induction on \( p \), \( t(2^p m) = 2^p t(m) + p \cdot m \cdot 2^{p-1} - (2^p - 1) 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{111111111}_2 = 511 \); hence the required \( m \) is 510.

(b) We must calculate \( t(98) \). Using the recursive formulas we have \( t(98) = 2t(49) + 49 - r(49) \), \( t(49) = 2t(24) + 25 \), and \( t(24) = 8t(3) + 36 - 7r(3) \). Since we have \( t(3) = 4 \), \( r(3) = 2 \), and \( r(49) = r(\overline{110001}_2) = 3 \), it follows \( t(24) = 54 \Rightarrow t(49) = 133 \Rightarrow t(98) = 312 \).

(c) We must find \( m_c \) such that \( t(m_c) \leq 1999 < t(m_c + 1) \). One can estimate where this occurs using the formula \( t(2^p (2^q - 1)) = (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 \).