An inventor presented to the king a new exciting board game on a 9×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 20154 grains.
Solution
Enumerate all squares with 1,…,90. Let the number of rice grains promised for the n-th square be Fn; then according to the problem F1=F2=1 and Fn=Fn−1+Fn−2 for all n>2. Notice that Fn>Fn−1 if n>2, hence F2(n+1)=F2n+2=F2n+1+F2n>F2n+F2n=2⋅F2n for all n. This implies F2⋅4>2⋅F2⋅3=2⋅8=24 and by mathematical induction F2n>2n for all n>3. Therefore F90>245>244=(211)4=20484>20154.
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.