IMO 1999 SL C3

Origin: GBR | Category: Combinatorics

Problem

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 2mth fly is the same as the resting period before catching the mth fly and one minute shorter than the resting period before catching the (2m + 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?

Solution

Let r(m) denote the rest period before the mth catch, t(m) the number of minutes before the mth 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) = m i=1 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(2pm) = 2pt(m) + p \cdot m \cdot 2p−1 −(2p −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 1111111112 = 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(1100012) = 3, it follows t(24) = 54 ⇒t(49) = 133 ⇒t(98) = 312. (c) We must find mc such that t(mc) \leq1999 < t(mc + 1). One can estimate where this occurs using the formula t(2p(2q −1)) = (p + q)2p+q−1 −p 2p−1 −q 2p + q, provable from the recursive relations. It suffices to note that t(462) = 1993 and t(463) = 2000; hence mc = 462.