From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Mathematics > STEP > STEP I 1997 question 1 solution

---

Solution 1

Possibilities to obtain 10p by using coins of 1, 2, 5 and 10p

10

5+5

5+2+2+1

5+2+1+1+1

5+1+1+1+1+1

2+2+2+2+2

2+2+2+2+1+1

2+2+2+1+1+1+1

2+2+1+1+1+1+1+1

2+1+1+1+1+1+1+1+1

1+1+1+1+1+1+1+1+1+1

Possibilities to obtain 20p by using 1, 2, 5 and 10p coins:

20=10+10

Hence we can see that there are 11 possibilities to obtain it if added with a 10.

Now we will have;

5+5+5+5

5+5+5+2+2+1 etc. 2 times more

5+5+2+2+2+2+2, 5+5+2+2+2+2+1+1 etc. 4 times more

5+2+2+2+2+2+2+2+1 etc. 7 times more

2+2+2+2+2+2+2+2+2+2 etc. 10 times more

i.e. total answer =41

Solution by nota bene

Solution 2

Let P(n,k) be the no. of ways of making n using coins <=k. We make the following observations:

P(n,1) = 1 for all n.

P(1,2) = 1, P(2,2) = 2, P(n,2)=floor(n/2)+1 (using 0,1,2,...,floor(n/2) 2's).

P(10,5) = P(10,2)+P(5,2)+1 = 6 + 3 + 1 = 10 (first term is using no 5's, second term is using one 5, last term is using 2 fives. We will use a similar construction repeatedly later).

P(10,10) = P(10,5)+1 = 11. (first term using no 10s, 2nd term using 1 10).

For the 2nd part:

P(20,5)=P(20,2)+P(15,2)+P(10,2)+P(5,2)+1 = 11 + 8 + 6 + 3 + 1 = 29

P(20,10) = P(20,5)+P(10,5)+1 = 29 + 10 + 1 = 40

P(20,20) = P(20,10)+1 = 41.

Solution by DFranklin

Solution 3

There is also a solution on page 21 of Stephen Siklos' Advanced Problems in Core Mathematics.