Who is asking: Student
Hi, I've been given a problem that I'm having some trouble with. I'd really appreciate any help. Here's the question (it's called the Pay Phone Problem)
A pay phone will take only 10p, 20p, 50p, and £1 coins"(It's British).
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.
To make a call costing 50p, she could put the coins in the order
20p, 20p, 10p
10p, 20p, 20p
10p, 10p, 20p, 10p
There are more ways of making 50p with only 10p and 20p coins" (I worked out that there was 8 ways)
A man also wants to use the pay phone. He has plenty of 10p and 50p coins. He has no other coins. He wishes to make a phone call costing any multiple of 10p.
For no.1 I've worked out a general equation where the next number in the series can be found if the previous two are known. The equation is:
f of n = (f of n - 1)+(f of n - 2) where f=the number of ways of making (in this case) "n"
For example, I found the 1st number in the series to be 1 (i.e. she can only enter 10p in one way) The second number in the series was found to be 2 (i.e. she can enter 20p using 10p, 10p OR 20p)
Using the general equation the third number in the series was found to be 3, i.e.
f of n = 2+1 = 3
I know the equation works but I have no proof for it.
What I've got for #2 is pretty similar, except the general equation is:
f of n= (f of n - 1)+(f of n - 5) Before this equation could be used, the first five in the series had to be found out first. As with #1, I have no proof for this.
The part that I'm really having trouble with is #3. I've got no idea what to do.
Your help would really be appreciated in finding a proof for the equations in #1 and #2, and also in whatever way you can help in #3.
The sequence that you found for problem number 1 is called the fibonacci sequence. It starts f(1) = 1, f(2) = 2 and then f(n) = f(n-1) + f(n-2) for n larger than 2. The way to see that this sequence gives a solution to problem #1 is illustrated in a similar problem, called
Stairs, which is the Quandaries and Queries database.
To return to the previous page use your browser's back button.