Name: Shameq

Who is asking: Student
Level: Secondary

Question:
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
OR
10p, 20p, 20p
OR
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)

1. The woman is going to make a phone call costing any multiple of 10 (i.e. 10p, 20p, 30p, 40p, etc.). INVESTIGATE the number of different ways, she could put the 10p and 20p coins into the pay phone.

   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.

2. INVESTIGATE the number of different ways he has of entering the 10p and 50p coins into the phone.

3. INVESTIGATE the more general case.

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.

Thanks alot,

Hi, 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.   The key is to look at the procedure in a backwards fashion. Using your notation that f(n) is the number of was of putting in coins for a call costing nx10p (x is multiplication), suppose that you have just completed such a call. Your last coin was either a 10p coin or a 20p coin so f(n) is the number of was of putting in coins for a call costing (n-1)x10p plus the number of was of putting in coins for a call costing (n-2)x10p, i.e. f(n) = f(n-1) + f(n-2).    Similarily, looking at problem #2 in the same way, you get f(n) = f(n-1) + f(n-5). The expressions f(n) = f(n-1) + f(n-2) and f(n) = f(n-1) + f(n-5) are called two term recurrences since f(n) can be determined from two previous terms in the sequence. For the case where you have 10p, 20p and 50p coins a similar argument will give a three term recurrence. Cheers Penny