Library / Estonian Math Competitions /31 of 148

Estonian Math Competitions

Algebra Difficulty 5.0 AIME, harder Prove it Estonia

An inventor presented to the king a new exciting board game on a $9 \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 $2015^4$ grains.

Solution

Enumerate all squares with $1, \ldots, 90$ . Let the number of rice grains promised for the $n$ -th square be $F_n$ ; then according to the problem $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n > 2$ . Notice that $F_n > F_{n-1}$ if $n > 2$ , hence $F_{2(n+1)} = F_{2n+2} = F_{2n+1} + F_{2n} > F_{2n} + F_{2n} = 2 \cdot F_{2n}$ for all $n$ . This implies $F_{2 \cdot 4} > 2 \cdot F_{2 \cdot 3} = 2 \cdot 8 = 2^4$ and by mathematical induction $F_{2n} > 2^n$ for all $n > 3$ . Therefore $F_{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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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