IMO 1979 SL 19

Origin: ROM

Problem

Consider the sequences (an), (bn) defined by a1 = 3, b1 = 100, an+1 = 3an, bn+1 = 100bn. Find the smallest integer m for which bm > a100.

Solution

Let us define ij for two positive integers i and j in the following way: i1 = i and ij+1 = iij for all positive integers j. Thus we must find the smallest m such that 100m > 3100. Since 1001 = 100 > 27 = 32, we inductively have 100j = 10100j−1 > 3100j−1 > 33j = 3j+1 and hence m \leq99. We now prove that m = 99 by proving 10098 < 3100. We note that (1001)2 = 104 < 274 = 312 < 327 = 33. We also note for d > 12 (which trivially holds for all d = 100i) that if c > d2, then we have 3c > 3d2 > 312d = (312)d > 10000d = (100d)2. Hence from 33 > (1001)2 it inductively follows that 3j > (100j−2)2 > 100j−2 and hence that 10099 > 3100 > 10098. Hence m = 99.