Maths Olympiad Prep

Library / /33 of 158

Algebra Difficulty 5.0 AIME, harder Prove it Estonia

An inventor presented to the king a new exciting board game on a 9×109 \times 10 squared board. The king promised to reward him one rice grain for the first square, one rice grain for the second square, and for each following square the same number of grains as for the two preceding squares together. Prove that for the last square the inventor gets at least 201542015^4 grains.

Solution

Enumerate all squares with 1,,901, \ldots, 90. Let the number of rice grains promised for the nn-th square be FnF_n; then according to the problem F1=F2=1F_1 = F_2 = 1 and Fn=Fn1+Fn2F_n = F_{n-1} + F_{n-2} for all n>2n > 2. Notice that Fn>Fn1F_n > F_{n-1} if n>2n > 2, hence F2(n+1)=F2n+2=F2n+1+F2n>F2n+F2n=2F2nF_{2(n+1)} = F_{2n+2} = F_{2n+1} + F_{2n} > F_{2n} + F_{2n} = 2 \cdot F_{2n} for all nn. This implies F24>2F23=28=24F_{2 \cdot 4} > 2 \cdot F_{2 \cdot 3} = 2 \cdot 8 = 2^4 and by mathematical induction F2n>2nF_{2n} > 2^n for all n>3n > 3. Therefore F90>245>244=(211)4=20484>20154F_{90} > 2^{45} > 2^{44} = (2^{11})^4 = 2048^4 > 2015^4.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.