Euler – Problem 2

April 1, 2010

It’s been a couple of days since I finished Problem 1 of Project Euler and I did in fact finish Problem 2 the very next day. Unfortuantely, I must admit that I have been making some very basic maths quite complicated in the hopes of understanding how some people have solved Problem 2.

Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

At first this seems like an insurmountable task because four million is quite a large number and common sense leads us to believe that there will be hundreds of numbers in the Fibonacci sequence below four million. Fortunately this is a paradox as there are only a mear 33 numbers below four million in the Fibonacci sequence.

I spent quite some time looking for a formulae that would let me work out all the even numbers in the fibonacci sequence (i.e. even numbers are always three terms apart, so F(3n) is always an even number). Not being a mathematician and not having done any kind of maths for several years I gave up (I also do not have that much time on my hands) and found a list of Fibonacci numbers and used a calculator to add up all the numbers below four million.

After getting the correct answer I did however look in to other peoples solutions, and there are some quite facinating solutions indeed. It’s made me learn about the Golden Ratio and how it links to the Fibonacci sequence, though I have not delved too far, see previous comment about not being a mathematician.

I’m going to very briefly go over one of the properties of the Fibonacci sequence and how it can be used to find the answer to this problem.

Golden Ratio

Something can be said to have the Golden Ratio if the ratio between two things is the same as the ratio between the larger of the two things and the sumation of the two things. Given that B is greater than A, B and A are in the Golden Ratio when:

A:B = B:(A+B)

This is also known as Φ (phi) and is the irrational (cannot be expressed as a proper fraction) number 1.6180339887…

Fibonacci Sequence
This links to the Fibonacci sequence because the ratio between two consecutive terms in the Fibonacci sequence is close to the Golden Ratio (it is more complicated than this, but for our purposes this is all we need to know). I’m going to express Fibonacci numbers as Fib(n) where n is the term, so F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2… F(10) = 55.

The nth term of the Fibonacci sequence can be expressed as so:

Fib(n) = Fib(n-1) + Fib(n-2)

And so the Ratio between two consecutive terms n and n-1 is as phi.

Fib(n)/Fib(n-1) = Φ

Eventually we want the ratio between three terms, because we know that even numbers are three terms apart.

Fib(n)/Fib(n-3) = ?

We can immediately infer that the ratio is going to be 3Φ because we know that the ratio between any Fibonacci number is going to be Φ, but for sake of argument I’ll show you what took me so long to work my head around. The ratio between three Fibonacci numbers is given by the following:

  1. Fib(n)/Fib(n-2)
  2. ( Fib(n) / (Fib(n-1) ) / ( Fib(n-2) / Fib(n-1) )

Now this is the point where I got confused, how can the first part be transformed into the second part? I tried many different ways, thinking it was a ratio of ratios, or an inverse ratio of the ratio or some crazy things like that and finally someone on the irc channel #maths helped me out with the simple answer of “that’s how fractions work”. If you Divide top and bottom by Fib(n-1) then you get part 2. The use of this is because we know that Fib(n)/Fib(n-1) is Φ, and because Fib(n-2)/Fib(n-1) is basically the inverse of Fib(n)/Fib(n-1) it is 1/Φ. This gives us the last two steps which are a replacement

  1. (Φ)/(1/Φ) : Replace Fib(n)/Fib(n-1) and Fib(n-2/Fib(n-1) with Φ and 1/Φ respectively
  2. 2Φ : x/(1/Φ) can also be written as x * Φ.

Finally, we want to know what Fib(n)/Fib(n-3) is, which can also be written like this:

( Fib(n) / Fib(n-2) )/ ( Fib(n-3) / Fib(n-2) )

  1. 2Φ / (1 / Φ) : Fib(n) / Fib(n-2) = 2Φ (From earlier) and Fib(n-3) / Fib(n-2) is 1/Φ (From earlier).
  2. 3Φ : As earlier, x/(1/Φ) = x*Φ.

And we’re done, we now know that even Fibonacci numbers are a ratio of 3Φ apart and use a calculator to work out the sum of all the even terms under four million.

There is one other solution that I don’t really understand that I might put some work into understanding, but I will have to see how much time I have, before that…

Problem 3:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Advertisements

Game Theory – Nash Equilibrium

April 24, 2009

In my last post on Game Theory I started by introducing Game Theory and the Matching Pennies game. In this post I’m going to explore the Nash Equilibrium to try and further my knowledge about Game Theory. In a game of two or more players where there isn’t a definative winner and looser the two players might be able to find a middle ground. This ‘middle ground’ might be described as the Nash Equilibrium, it occurs when all the players in a game are getting the best payoff for the move they make (i.e. no player can benefit by deviating from his strategy).

An example of this can be found in a Game where a couple who fail to make a decision about what to do in the evening get split up and so they each have to decide which event to go to. It just so happens that each person in the couple has a favourite activity which they may have wanted to do in the eveing. The man favours going to watch sports and the woman favours going to the cinema. If the man chooses to go to watch sports then he is getting the most enjoyment out of the activity and likewise, if the woman goes to the cinema she will get her best payoff.  If they meet then the woman will enjoy the sports slightly and the man will enjoy the cinema slightly, however, if they fail to meet then they will both not enjoy the activity.

Following is the payoff table for this game.

Male
Sport
Male
Cinema
Female
Sport
+2
+1
0
0
Female
Cinema
0
0
+1
+2

Here you can see that there are two Nash Equilibrium for this Game if either player knows what the other person is going to do. If the Male knows the Female will go to the Cinema it is in his best interest to go to the Cinema as well. This simply shows what a Nash Equilibrium is and it requires that each participant knows what the other persons best payoff is and so what they are going to do.


Game Theory – An Introduction

March 27, 2009

Game theory, as with most logical and mathematical disciplines has interested me for a long time but until recently I haven’t had time or the motivation to look in to it very far. On my reading list from Christmas I have a small introduction to Game Theory. So far it’s been really quite interesting, I’ve lost the plot a few times and not understand one of the very basic concepts because of some of the wording, but it’s got all the information and there are no hard to understand formula.

Game Theory then, from what I understand of it so far, is the maths that can be used to determine what a ‘rational’ thing (or things) would do in a given situation. It’s applied across the board from the decisions animals and insects make and why they should make one decision over another all the way to what I should do in a game of poker.

In a basic game like Matching Pennies you can explain the very basics of Game Theory. The game involves two players, each has to choose either Heads or Tails on a penny and when they reveal their choice the first player wins if both pennies are the same (Heads, Heads/Tails, Tails) and the second player wins if the pennies are missmatched (Heads, Tails/Tails, Heads). It is known as a Zero-Sum Game because one player wins and the other player loses, i.e both players ‘payoffs’ are balanced, I win, you lose, visa versa, or a draw occurs in which all players get 0 payoff. A Zero-Sum game is therefore a game of pure-conflict, to maximize my payoff I have to try and make you lose by winning and visa versa. You could change Matching Pennies so that it was no longer Zero-Sum by giving some of the options benefit for both parties or the opposite. If we say that anything with a Tail in it means that both players win then it might be beneficial, if you know your opposition will play Heads, to always play Tails.

Game Theory is used to demonstrate what the best strategy is for both players, should the first player always go Heads, choose Heads two-thirds, one-half, one-quarter of the time, or maybe not at all? A decision matrix can be drawn up for the Matching Pennies game whereby if you win you get 1 and if you lose you get -1, that way the payoffs are balanced at a round 0.

Player 1
Heads
Player 1
Tails
Player 2
Heads
+1
-1
-1
+1
Player 2
Tails
-1
+1
+1
-1

In the top left you can see that if both player choose Heads then player one gets +1 and player two gets -1. We can understand from simple common sense that there isn’t really a best strategy unless you know what the other player is going to do, so I’m best off choosing Heads/Tails with an equal probability of 50%. This is called a mixed strategy as opposed to a pure strategy which will determine what a rational person should do in any situation of a Game.

Game Theory seems like it could be very useful in lots of situations where one should make a decision, the more I think about it the more I believe I’m going to start pondering options I take in terms of Game Theory.