wilmott.com

A pay phone will take only 10p, 20p, 50p and £1 coins.A woman has plenty of 10p and 20p coins. She has no other coins. She can put the coins into the pay phone in any order.Question?1. The woman is going to make a phone call costing any multiple of 10p. Investigate the number of different ways she could put 10p and 20p coins into the payphone.

you say to investigate the number of ways she can put coins into the phone (assuming it doesn't give change and she doesn't want to overpay). I'm therefore assuming that order is relevance - ie 10 then 20 is different to 20 then 10.let g(n) be the number of ways she can put in 10n cents. She can either put in a 10 cent piece or a 20, hence g(n) = g(n-1) + g(n-2). This is the same recurrence relation as the Fibonacci sequence, except here g(1)=1 and g(2)=2, suggesting that g(n)=f(n+1).The solution to the fibonacci sequence being f(n)= [ (1+root 5)^n - (1-root 5)^n]/[2^n x root 5]=g(n-1).

QuoteOriginally posted by: gjlipmanyou say to investigate the number of ways she can put coins into the phone (assuming it doesn't give change and she doesn't want to overpay). I'm therefore assuming that order is relevance - ie 10 then 20 is different to 20 then 10.let g(n) be the number of ways she can put in 10n cents. She can either put in a 10 cent piece or a 20, hence g(n) = g(n-1) + g(n-2). This is the same recurrence relation as the Fibonacci sequence, except here g(1)=1 and g(2)=2, suggesting that g(n)=f(n+1).The solution to the fibonacci sequence being f(n)= [ (1+root 5)^n - (1-root 5)^n]/[2^n x root 5]=g(n-1).how did you get the solution f(n)= [ (1+root 5)^n - (1-root 5)^n]/[2^n x root 5]=g(n-1)plugging in the values gives g(1)= -1 ang g(2)=1 into g(n)=g(n-1) + g(n-2)

plugging in the values:g(0)=f(1)=(2 root 5/2 root 5)=1g(1)=f(2)=(4 root 5/4 root 5)=1g(2)=f(3)=(16 root 5 / 8 root 5)=2 Also, it is really bad form to post the same question on several forums - it is a pain when you spend time answering a question on one forum, only to find that it has already been answered on another forum.

Can anyone explain why the solution has this form???

You just search for g(n) in the form of x^n(which gives quadratic equation in this case) and then the general solution is Ax_1^n + Bx_2^n where A and B can be determined from starting values

sorry, double post

This is the same question as:There are n steps, you can either make one or two steps a time, how many different ways to reach the top

I guess this should help,http://www.wilmott.com/messageview.cfm? ... adid=50558

I guess this should help,http://www.wilmott.com/messageview.cfm? ... adid=50558

write it as:(sum x^n)*(sum x^(2n)) = sum A_k*x^kwhere A_k is the number of different ways to obtain k*10 p ..