9 Jan 2013

Fibonacci 2013: Guided Solution

This is the solution to the Fibonacci 2013 problem I posted a few days ago. If you haven't had a go yet, then please try it for yourself first before reading any further!

The reason I call these Guided Solutions is that you will see below both the solution as one would write it down and also some 'thinking boxes' which explain the thought processes that should be going through one's mind. I also include some background information in case you haven't come across such problems before.

So, let's get on with it!

The question is about a Fibonacci sequence for which we are not given the first two terms. This is fairly common in competition questions as it forces you to think of how a general Fibonacci sequence works, rather than the standard 1, 1, 2, 3, 5... and so on.

The question gives us two pieces of information. the most obvious one is that the 7th term is equal to 2013. The second piece of data is less obvious but equally important; that the sequence is of positive integers. The significance of this will become obvious in a moment.

The way to start the question is to write out a general Fibonacci sequence with unknown starting values, lets call them p and q. The question only goes up to the 7th term so it will not take long to list each term. Note that if you get a question about a very high nth value then you may need to rely on some other property of the sequence. Also note that traditionally sequences are labelled as T(n), with the T standing for Term. You will also see it written like Tn. Fibonacci sequences are so important they are usually written as F(n).

F(1) = p
F(2) = q
F(3) = p + q
F(4) = p + 2q
F(5) = 2p + 3q
F(6) = 3p + 5q
F(7) = 5p + 8q
Phew! We can stop now. What we now have to do is equate F(7) with 2013.

Hence 5p + 8q = 2013

What do we do now? We have one equation with two unknowns, and no further information to guide us. This form of equation is known as a Diophantine equation, which sounds very grand but you probably came across such things in primary school questions about buying two different products with a fixed amount of money. Although it may not appear immediately obvious, the numbers in this problem yield quite a quick and easy solution.

Let's go back to the original question; we need to find the minimum value of F(3) which is equivalent to finding (p + q). If p and q could be any real numbers we would have an infinite number of solutions and be genuinely stuck! However, we are told that the numbers are positive integers; this means we have a finite (although maybe large) set of answers. Let's proceed with confidence!

We want the minimum value of F(3). We can write this as min(p + q) or min(F(3)). Let's try the most obvious numbers and see what happens.

Let p=1, so that
5x1 + 8q = 2013
8q = 2008 so q = 2008/8 = 251

p=1 and q=251 so that p + q = 1 + 251 = 252

So we have found one solution. But is this our required minimum? Let's try the same thing but looking at q first.

Let q=1 then
5p + 8x1 = 2013
p = 2005/5 = 401
so p + q = 402 > 252
so min(p+q) = 252
Check for other solutions.

Again, we have lucked out and setting q=1 gives us an integer solution to p. Note that this is not always the case and you may need to test higher values until you find the first integral solution.

Going back to the question, our min(p+q) with q=1 is now 402. This is higher than our first attempt of 252. So it looks as if our required answer is indeed 252. We have calculated the two extreme solutions and found that one of them is far smaller than the other. Is it possible that an even smaller solution exists somewhere in the middle? 

As this is a linear Diophantine equation with positive integral solutions, if we plot the points (p,q) on a graph we will get a linear sequence of dots going through the points (1,251) and (401,1). Note that the next integral solution after p=1 is p=9, giving q=246 and p+q=255, higher than the minimum so far of 252. Why does this happen?

Look again at the equation 5p+8q=2013. If we increase p by 8 and decrease q by 5 we obtain the same total of 2013. Look at the algebra:
5(p + 8) + 8(q - 5) = 5p + 40 + 8q - 40 = 5p + 8p = 2013

Now let's define p' and q' as our required solutions (so that p'=1 and q'=251). Then we can define linear functions

p(n) = p' + 8n and q(n) = q' - 5n (for p(n),q(n)>0)

Note that in this notation p(0)=p' and q(0)=q'.

Now we have a function that describes how the sum (p+q) varies, that is

p(n) + q(n) = p' + 8n + q' - 5n = p' + q' + 3n > p' + q' for all n apart from n=0.

What this last line tells us is that all if we start from our assumed minimum solution of 252, the next value of (p + q) will be 252+3=255 (which we already know!) and the next ones will be 258, 261, 264, and so on till we reach 402.

One question that wasn't asked here, but might be in another similar problem, is how many solutions there are in total to the original Diophantine equation, still with the condition that p and q are positive integers. We can easily solve that now with:

min(p+q) + 3n = max(p+q)

252 + 3n = 402 or 3n=150, n=50.

There are 51 different solutions to 5p + 8q = 1203 (Easy to forget that n runs from 0 to 50, so takes 51 values.)

So that n=0 is indeed our solution, which means that p'+q' is our min(p+q) and our final answer is 252!

Answer = 252


In a test situation with multiple choice answers you obviously wouldn't need this last proof showing that there isn't some other solution lurking in between our two extremes. You would, in such a case, realise that this is a linear equation and that the solutions would form a linear sequence between the two extremes. However, if the test requires fully written answers, then you would be expected to show some kind of proof that all the other solutions are greater than your minimal solution.

Hope this guided solution helps. Please leave some feedback as to whether the layout makes sense. I personally feel that the 'thinking boxes' provide a commentary as to what should be going on your mind whilst doing similar questions. As always in mathematics, there will be slightly different ways of doing this. If anybody has a completely different solution method then, again, please share it with us.

* * * Follow-up * * *

What if this was next year? What is the min(p+q) such that 5p+8q=2014, with p and q both positive integers?

What about extending this problem to a general F(m)=2013, again find min(F(3)). Is there any pattern? Can we predict the answer and create a simple function such that min(p+q)=f(m,2013)?

Let me know how you get on?

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...