IMO 2000 SL A4

Origin: GBR | Category: Algebra

Problem

The function F is defined on the set of nonnegative integers and takes nonnegative integer values satisfying the following conditions: For every n \geq0, (i) F(4n) = F(2n) + F(n); (ii) F(4n + 2) = F(4n) + 1; (iii) F(2n + 1) = F(2n) + 1. Prove that for each positive integer m, the number of integers n with 0 \leqn < 2m and F(4n) = F(3n) is F(2m+1).

Solution

Clearly F(0) = 0 by (i). Moreover, it follows by induction from (i) that F(2n) = fn+1 where fn denotes the nth Fibonacci’s number. In general, if n = ϵk2k+ϵk−12k−1+\cdot \cdot \cdot+ϵ1\cdot2+ϵ0 (where ϵi \in{0, 1}), it is straightforward to verify that F(n) = ϵkfk+1 + ϵk−1fk + \cdot \cdot \cdot + ϵ1f2 + ϵ0f1. (1) We observe that if the binary representation of n contains no two adjacent ones, then F(3n) = F(4n). Indeed, if n = ϵkr2kr + \cdot \cdot \cdot + ϵk02k0, where ki+1 −ki \geq2 for all i, then 3n = ϵkr(2kr+1 + 2kr) + \cdot \cdot \cdot + ϵk0(2k0+1 + 2k0). According to this, in computing F(3n) each fi+1 in (1) is replaced by fi+1 + fi+2 = fi+3, leading to the value of F(4n). We shall prove the converse: F(3n) \leqF(4n) holds for all n \geq0, with equality if and only if the binary representation of n contains no two adjacent ones. We prove by induction on m \geq1 that this holds for all n satisfying 0 \leqn < 2m. The verification for the early values of m is direct. Assume it is true for a certain m and let 2m \leqn \leq2n+1. If n = 2m + p, 0 \leqp < 2m, then (1) implies F(4n) = F(2m+2 + 4p) = fm+3 + F(4p). Now we distinguish three cases: (i) If 3p < 2m, then the binary representation of 3p does not carry into that of 3 \cdot 2m. Then it follows from (1) and the induction hypothesis that

F(3n) = F(3 \cdot2m)+F(3p) = fm+3 +F(3p) \leqfm+3 +F(4p) = F(4n). Equality holds if and only if F(3p) = F(4p), i.e. p has no two adjacent binary ones. (ii) If 2m \leq3p < 2m+1, then the binary representation of 3p carries 1 into that of 3\cdot2m. Thus F(3n) = fm+3+(F(3p)−fm+1) = fm+2+F(3p) < fm+3 + F(4p) = F(4n). (iii) If 2m+1 \leqp < 3 \cdot 2m, then the binary representation of 3p caries 10 into that of 3 \cdot 2m, which implies F(3n) = fm+3 + fm+1 + (F(3p) −fm+2) = 2fm+1 + F(3p) < F(4n). It remains to compute the number of integers in [0, 2m) with no two adjacent binary 1’s. Denote their number by um. Among them there are um−1 less than 2m−1 and um−2 in the segment [2m−1, 2m). Hence um = um−1 + um−2 for m \geq3. Since u1 = 2 = f3, u2 = 3 = f4, we conclude that um = fm+2 = F(2m+1).