Maths Olympiad Prep

Library / /9 of 10

Algebra Difficulty 6.5 National Olympiad Prove it Philippines

Problem:

Define a sequence of integers as follows: a1=1a_{1}=1, a2=2a_{2}=2, and for kNk \in \mathbb{N}, ak+2=ak+1+aka_{k+2}=a_{k+1}+a_{k}. How many different ways are there to write 20172017 as a sum of distinct elements of this sequence?

Solution

Solution:

Note that these aka_{k}'s are in fact the Fibonacci numbers. Denote by f(n)f(n) the number of distinct ways to express a number as a sum of aka_{k}. Note that 2017=1597+377+34+8+1=a15+a12+a8+a5+a12017=1597+377+34+8+1=a_{15}+a_{12}+a_{8}+a_{5}+a_{1}.

We prove the following lemma:
a1+a2++ak=ak+22 a_{1}+a_{2}+\cdots+a_{k}=a_{k+2}-2
This follows simply from induction. It is true for k=1k=1; adding ak+1a_{k+1} to both sides and using the fact that ak+1+ak+2=ak+3a_{k+1}+a_{k+2}=a_{k+3} gives the result.

Now, denote by f(n)f(n) the number of ways to express nn as a sum of distinct aka_{k}'s; we are looking for f(2017)f(2017). Now, note that any such sum must contain either 15971597 or 987987. If the sum does not contain 15971597, it must certainly contain 987987; otherwise, from the lemma, the sum would be at most 1+2++610=15951+2+\cdots+610=1595. Moreover, if the sum contains 987987 (but not 15971597), it must also contain 610610; otherwise, it will be at most 987+(1+2++377)=987+985=1972987+(1+2+\cdots+377)=987+985=1972.

Hence, f(2017)=2f(420)f(2017)=2 f(420).

By a similar argument, any sum of 420420 must contain either 377377 or 233233. However, this time, it is perfectly possible for this sum to contain 233233 but not 144144, since 233+(1+2+3++89)=464>420233+(1+2+3+\cdots+89)=464>420. We thus have two cases to deal with.

Case 1: If the sum contains 377377, then we have to compute f(43)f(43). Now, note that as in the argument from earlier, any sum adding up to 4343 contains either 3434 or 13+2113+21. Hence f(43)=2f(9)f(43)=2 f(9). Repeating this argument, we get f(9)=2f(1)=2f(9)=2 f(1)=2. This gives us f(43)=4f(43)=4.

Case 2: The sum does not contain 377377. In this case, the sum must contain 233233. We then have to compute f(187)f(187). Any sum adding up to 187187 must contain either 144144 or 8989; moreover, if it contains 8989, it must contain 5555 as well. Hence, f(187)=2f(43)=8f(187)=2 f(43)=8 by our previous computation.

Thus, f(420)=3f(43)=12f(420)=3 f(43)=12, and f(2017)=24f(2017)=24.

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.