Problem 2:  Partitions of 10 and 20 ($✓$) 1997 Paper I

(i)

Show that you can make up 10 pence in eleven ways using 10p, 5p, 2p and 1p coins.

(ii)

In how many ways can you make up 20 pence using 20p, 10p, 5p, 2p and 1p coins?

Comments

I don’t really approve of this sort of question, at least as far as STEP is concerned, but I thought I’d better include one in this collection. The one given above seems to me to be a particularly bad example, because there are a number of neat and elegant mathematical ways of approaching it, none of which turn out to be any use.

The quickest instrument is the bluntest: just write out all the possibilities. Two things are important. First you must be systematic or you will get hopelessly confused; second, you must lay out your solution, with careful explanations, in a way which allows other people (examiners, for example) to understand exactly what you are doing. You can probably lay it out using pen and paper much better than I have overleaf, using a wordprocessing package. If you get an answer and, looking back, find that your work lacks clarity, then do it again.

Since different parts of STEP questions are nearly always related, you might be led to believe that the result of the second part follows from the first: you divide the required twenty pence into two tens and then use the result of the first part to give the number of ways of making up each 10. This would give an answer of 66 (why?) plus one for a single 20p piece. This would be neat, but the true answer is less than 67 because some arrangements are counted twice by this method — and it is not easy to work out which ones.

Solution to problem 2

Probably the best approach is to start counting with the arrangements which use as many high denomination coins as possible, then work down.

(i)  We can make up 10p as follows:

10  (one way using only one 10p coin);

5+5  (one way using two 5p coins and no 10p coins);

5+2+2+1,   5+2+1+1+1,   5+1+1+1+1+1  (three ways using one 5p coin and no 10p coins);

2+2+2+2+2,   2+2+2+2+1+1,   etc  (six ways using no 5p or 10p coins).

That makes 11 ways altogether.

(ii)   We can make up 20p as follows:

20  (one way using only a 20p coin);

10 + any of the 11 arrangements in the first part of the question  (11 ways using one or two 10p coins);

5+5+5+5   (one way using four 5p coins and no 10p or 20p coins);

5+5+5+2+2+1,   etc  (3 ways using three 5p coins and no 10p or 20p coins);

5+5+2+2+2+2+2,   5+5+2+2+2+2+1+1,   etc  (6 ways using two 5p coins and no 10p or 20p coins);

5+2+2+2+2+2+2+2+1,   etc  (8 ways using one 5p coin and no 10p or 20p coins);

2+2+2+2+2+2+2+2+2+2,   etc  (11 ways using no 5p, 10p or 20p coins).

That makes 41 ways altogether.

Post-mortem

As in the previous question, the most important lesson to be learnt here is the value of a systematic approach and clear explanations. You should not be happy just to obtain the answer: there is no virtue in that. You should only be satisfied if you displayed your working at least as systematically as I have, above.

On reflection, this question is not quite as bad as I thought. I did in fact use the first part to help with the second. And in the second part I certainly used the method of setting out the different ways systematically that I developed in the less complicated first part.

Here is an interesting thought. For the part (i), consider the expansion of

in powers of $x$. This we can obtain from the binomial expansion of each of the four terms in the denominator, giving $\left(1+x^{10}+x^{20}+\cdots \right)\left(1+x^5+x^{10}+\cdots \right)\left(1+x^2+x^4+\cdots \right)\left(1+x+x^2+\cdots \right).$ Now if we multiply out these brackets and find that the term in $x^{10}$ (say) is the sum of terms of the form $x^{10a}\times x^{5b}\times x^{2c}\times x^d$, one from each bracket, where $a$, $b$, $c$ and $d$ are non-negative integers such that $10a+5b+2c+d=10$. It is not hard to see that there is exactly one possibility for these integers for each of the arrangements of the coins in part (i), so the number of arrangements is exactly equal to the coefficient of $x^{10}$ in $\left(\ast \right)$.

Although this is neat, it doesn’t help, because there is no easy way of obtaining the required coefficient. Formally, though, we could obtain the coefficient using Taylor series, which involves differentiating $\left(\ast \right)$ 10 times and setting $x=0$. This is interesting, because we have converted a problem in discrete mathematics, involving only integers, to a problem in calculus involving only smooth functions.