## 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: ## 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

## Before the beginning – Euclid’s Common Notions

This preamble from Euclid’s Elements is where mathematics education still goes wrong, even after 2000 years or so.

Sound notions of what equality is are required as a bedrock of algebra.  Dynamic approaches of teaching equation solving, in which terms and numbers move and change sign, seem to work at first but lack the simplicity of mathematical logic and create all sorts of problems when randomly, but apparently sensibly, applied.

## Conic sections in the sand give shipwrecked philosophers good hope

Conic sections in the sand give shipwrecked Socratic philosopher, Aristippus, good hope.

I wonder if this ancient tale, in which the mathematics of planetary motion some 2000 years prior to it’s application in space travel, is used to signify the presence of intelligent life and therefore hope of salvation has some echo in our modern era.

What obscure and impenetrable modern theorems could be left on a 21st century beach to do the same job?

## Conic Sections Tangent/Normal Locus

A level further mathematics question animated.  Mid point of Normal x-intercept and Tangent y-intercept traces out another curve as original point moves round an ellipse.

## Hyperbola – Focus Directrix

Hyperbola – locus of points in which ratio of distance from a focus point to the perpendicular distance to a line (directrix) is constant and greater than 1.  Staple diet of school Further Mathematics.

## Algebraic Form of the Modulus Function

Sneaky play with algebraic notation and function definition lays traps for scholarship students in school maths.

## Functional Transfromations – Core Maths into STEP

Linking core maths 3 functional transformations to Step algebra and solutions of equations.