Counting Pennies, Generating Functions and STEP

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

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

There is an interesting way of approaching this question using generating functions.

A generating function is of the form:

$a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}+\dots$

where the coefficients of $t$ count various problems and issues of convergence are unimportant.

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

This will be the co-efficient of $t^{10}$ in,

$(1+t+t^{2}+t^{3}+\dots+t^{10})(1+t^{2}+t^{4}+\dots+t^{10})(1+t^{5}+t^{10})(1+t^{10})$

by way of explanation:

$\overset{\textnormal{the 1p s}}{\overbrace{(1+t+t^{2}+t^{3}+\dots+t^{10})}}\overset{\textnormal{the 2p s}}{\overbrace{(1+t^{2}+t^{4}+\dots+t^{10})}}\overset{\textnormal{the 5p s}}{\overbrace{(1+t^{5}+t^{10})}}\overset{\textnormal{the 10p s}}{\overbrace{(1+t^{10})}}$

The candidate still needs to expand the function to get the answer, but having changed the problem to one of algebra, they might enjoy the benefits of practice and familiarity in the manual computation.

For those of at liberty to explore the question at leisure, a Computer Algebra System (CAS) is useful. In fact, the website Wolfram Alpha will expand the brackets for us, computing the answers to all similar counting problems in the process. The Wolfram Alpha query box understands the latex code if this is just pasted in, but only if it is presented in an explicit form, that is without the dots.  In order to simplify the question for the CAS notice that each bracket is a geometric progression, which can be summed using standard A level theory reducing the function to:

$\dfrac{(1-t^{11})}{(1-t)}\dfrac{(1-t^{12})}{(1-t^{2})}\dfrac{(1-t^{15})}{(1-t^{5})}\dfrac{(1+t^{10})}{1}$

Use of Wolfram Alpha then gives the following:

which contains our answer to the first part: 11.

Equipped with some methods and machinery we can now proceed to the second part of the question.  In fact, we can adapt the method and functions to count any similar loose change problem.

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

This will be the coefficient of $t^{20}$ in,

$(1+t+t^{2}+t^{3}+\dots+t^{20})(1+t^{2}+t^{4}+\dots+t^{20})(1+t^{5}+t^{10}+\dots+t^{20})(1+t^{10}+t^{20})(1+t^{20})$

$\overset{\textnormal{the 1 p s}}{\overbrace{(1+t+t^{2}+t^{3}+\dots+t^{20})}}\overset{\textnormal{the 2 p s}}{\overbrace{(1+t^{2}+t^{4}+\dots+t^{20})}}\overset{\textnormal{the 5 p s}}{\overbrace{(1+t^{5}+t^{10}+\dots+t^{20})}}\overset{\textnormal{the 10p s}}{\overbrace{(1+t^{10}+t^{20})}}\overset{\textnormal{the 20p s}}{\overbrace{(1+t^{20})}}$

which is equal to

$\dfrac{(1-t^{21})}{(1-t)}\dfrac{(1-t^{22})}{(1-t^{2})}\dfrac{(1-t^{25})}{(1-t^{5})}\dfrac{(1+t^{10}+t^{20})(1+t^{20})}{1}$

and which Wolfram Alpha gives and expansion of:

Differentiation From First Principles

The gradient of a smooth curve, $\textnormal{f}(x)$, at a point $x$ is the gradient of the tangent to the curve at the point $x$. Point $P$ is on the curve and $Q$ is a neighbouring point whose $x$ value is displaced a small quantity, $\delta x$.

The idea behind differentiation is that as $\delta x$ becomes very small, the gradient of $PQ$ tends towards the gradient of the curve. In the limit as $\delta x$ becomes infinitesimally close to zero, the gradient $PQ$ becomes the gradient of the curve.

We write:

$\textnormal{gradient f}(x)=\dfrac{\textnormal{d}y}{\textnormal{d}x}=\lim_{\delta x \rightarrow 0}\left(\dfrac{\delta y}{\delta x}\right)=\lim_{\delta x \rightarrow 0}\left(\dfrac{\textnormal{f}(x+\delta x)-\textnormal{f}(x)}{\delta x}\right)$

there is a fair bit of analytic work missing (higher education) to make these ideas sound.

We also write:

$\dfrac{\textnormal{d}y}{\textnormal{d}x}=\textnormal{f}'(x).$

STANDARD RESULTS

Standard results can be proved for different functions.

If $\textnormal{f}(x)=x^{n}$ then

If $\textnormal{f}(x)=\sin x$, then we need to consider the small angle approximation that is if $\delta x$ radians is very small (infinitesimal), then $\delta x\approx\sin \delta x$ and $\cos \delta x \approx 1$, and compound trigonometry from which follows,

The differentiation process described above is linear and extends to more complicated functions. That is to say that if, $y=a\textnormal{f}(x)+b\textnormal{g}(x)$ where $a,b \in \mathbb{R}$,
$\dfrac{\textnormal{d}y}{\textnormal{d}x}=a\textnormal{f}'(x)+b\textnormal{g}'(x)$

Carr’s Synopsis and Sixth Term Entrance Papers

Students in search of extension work in maths, particularly as far as Sixth Term Entrance Papers (STEP) are concerned, should peruse Carr’s Synopsis of results in Elementary Pure Mathematics.

This book is famous for being the volume used by the autodidact Ramanujan to teach himself mathematics.  The book is merely a list of results and student how works through them, proving each one, will develop a strong ability in the subject.  This life line into higher mathematics could not be produced in the same form in today’s educational and publishing context but, perhaps, Carr deserves a place as one of the subject’s great educators.

Higher mathematics is about generalisation and abstraction.  Because of this, school mathematics students can find university text books unreadable.  In such a context how can harder, higher level questions be set using the frame work of sixth form mathematics? The answer to this question is to wind the clock back to the 1880s and see how the subject was constructed then.  Carr does this for us; many useful stages in school mathematics are listed here with extensions and generalisation written in generally sixth form recognisable form.

Take question 1 from this year’s (2016) STEP I exam.  Pupils will only have to be familiar with the first six results to tackle this quickly.

The question play is all about the divisibility of,

$x^{2n+1}+1$

which result 6, above, tells us is

$(x+1)(x^{2n}-x^{2n-1}+\dots+1)$.

Question game play leads us to factorise large numbers (without use of calculator):

$\dfrac{300^{3}+1}{301}=89911\times 90091$

and

$\dfrac{7^{49}+1}{7^{7}+1}=[(7^{7}+1)^{3}-7^{4}(7^{14}+7^{7}+1)][(7^{7}+1)^{3}+7^{4}(7^{14}+7^{7}+1)]$

in a difference of two squares (result 1) construction.

Full solution is attached.

step-i-2016-q1

Transformations of Sine

Functional notation and transformations is always tricky to teach and understand.  GCSE students will meet this in Year 11.   In general, transformations applied after the function are more easily understood:

$y=f(x)+a$  or  $y=af(x)$

Something very un-intuitive happens when the transformation is applied to the argument of the function:

$y=f(x-a)$  or  $y=f(ax)$

with things stretching when they look like they should be compressing and other things moving the wrong way.

Mathematics is not always obvious, if it were we wouldn’t need it.

Try this for transformations of Sine.

The linear combination of a sine and a cosine is itself a sine wave

A linear combination of two functions, $f(x)$ and $g(x)$ is a sum involving constant multiples of the functions.  That is,

$a f(x)+b g(x)$

where $a, b \in \mathbb{R}$.

So, in the case of $\sin x$ and $\cos x$, we would have,

$a\sin(x)+b\cos(x)$.

It is a slightly surprising fact that the linear combination of two sine waves is itself a sine wave.  The set of sine waves is closed under linear combination.

The in the featured animation, $a\sin(x)$ is green and dotted and $b\cos(x)$ is red and dotted.  The resulting linear combination is the continuous blue line.  The value $a$ is set to 2.5, whereas the value $b$ is animated.

This principle occurs in A level maths, Core 3, and is responsible for many long and complex questions.

third century wisdom of Diophantus gives us the essential truth about teaching and learning mathematics

The Google facsimile of the 1621 edition of Diophantus’s Arithmetica lays out, in original Greek and Latin translation, the essentials for success in teaching and learning mathematics.  Also included is the translation of the second half by Heath.

When I first studied and learned to love mathematics I was beset by friends and family who stridently claimed that this field of study was closed to them because of some biological, or other, reason.  This always seemed to undervalue my own effort in getting off the first page.

Teachers of mathematics cannot be permitted to admit that nature is able to restrict the ability to learn the subject but the oriental wisdom of the student making their way to the master is a precondition for success when things seem difficult; in tales of martial arts the student must somehow prepare themselves to learn.

So,

1.  Mathematics appears rather difficult if one is not familiar with it.
2. Students need energy, eagerness and enthusiasm.
3. When such motivation is backed up by good teaching rapid learning results.

In school we struggle because of item 1 and bear our hearts to gain item 2, being so often rebuffed.  I suppose that we get paid for 1 and 2 because, when item 3 is achieved the job is it’s own reward.