How much can we spend?

A country has decided to have just two different coins, 3z and 5z coins. Which totals can be made? Is there a largest total that cannot be made? How do you know?

Age

11 to 14

Challenge level

Secondary

NUMBER

Factors, Multiples & Primes

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving

Being curious Being resourceful Being resilient Being collaborative

Problem

How Much Can We Spend? printable worksheet

A country has decided to have just two different coins.

It has been suggested that these should be 3z and 5z coins.

The shops think this is a good idea since most totals can be made.

Image		Image
$2\times3z+1\times 5z=11z$		$7 \times 3z + 2 \times 5z = 31z$

Unfortunately some totals can't be made, for example 4z.

Which totals can be made?

Is there a largest total that cannot be made?

How do you know?

They have decided that they will definitely have 3z coins but can't make up their minds about the other coin.

Experiment with other pairings containing 3z, and explore which totals can be made.

Can you find a relationship between 3z, the second coin, and the totals that can and can't be made?

In other countries they have also decided to have just two coins, but instead of the 3z coins they have chosen a different prime number.

Can you find a relationship between pairs of coin values and the totals that can and can't be made with them?

NOTES AND BACKGROUND

The coin problem (also referred to as Frobenius coin problem or Frobenius problem) is a mathematics problem associated with the German mathematician Ferdinand Georg Frobenius and often introduced in the context of making exact change given the availability of coins of specific denominations. To read about it go to Wikipedia.

Student Solutions

Adam and Dylan had some great ideas, Sam explains his thoughts clearly:

The largest number that can't be made is 7. This is because the lowest run of three numbers you can make is 8,9 and 10. If you make this using 5 or 3 and then keep adding different quantities of 3 to them you should be able to make every number higher than them.

Using $3z$ and $4z$ the highest number that can't be made is 5. This is because you can make 6, 7 and 8.

Mrs Dillon's year 7 class had a different way of showing 7 is the largest amount that can't be made;

We think using a $3z$ & $5z$ coin you can make all numbers except: 1, 2, 4, 7

We know you can make all other numbers because: we made all of the numbers from 11 to 20, and we can then get the rest by adding multiples of 10 (two 5z coins) onto any of these numbers.

We have also noticed that if you could get change, the 1, 2, 4 & 7 could also be made. So if you had to pay $1z$ then you could pay $6z$ and be given $5z$ back.

You can make $2z$ by paying $5z$ and getting $3z$ in change.

For $4z$ you can pay $9z$ and get $5z$ back.

Finally $7z$ can be paid by you paying $10z$ and getting $3z$ change.

Fantastic!

Tze Liang Chee looked into other possible combinations for other countries:

For a pairing such as 2 and 7, then any number of the form $2X + 7Y$ can be made, where $X$ and $Y$ are whole numbers. Eg $10 = 2 \times 5 + 7 \times 0 = 2 + 2 + 2 + 2 + 2$ or $16 = 2 \times 1 + 7 \times 2 = 2 + 7 + 7$

The numbers that can't be made are any $C$ where for $C = 2X + 7Y$ means that $X$ and $Y$ are not whole numbers.

For this if you can make 2 consecutive numbers, then you can make everything higher by adding multiples of 2. So here the lowest consecutive numbers that can be made are $6 = 2 + 2 + 2 = 2 \times 3$ and $7 = 7 = 7 \times 1$ so everything higher than 6 can be made by adding multiples of two. So you can't make 1, 3, 5 and that's it.

Generally if your two coins are $a$ and $b$, where $a$ and $b$ are coprime (their only common factor is 1) and $a$ is smaller than $b$, then as soon as you can make $a$ consecutive numbers, then you can make everything higher by adding multiples of $a$.

Eg. If you have $4z$ and $5z$ then you need to make 4 consecutive numbers.

The lowest ones are

$12 = 4 + 4 + 4$,

$13 = 4 + 4 + 5$,

$14 = 4 + 5 + 5$,

$15 = 5 + 5 + 5$,

so every number bigger than 12 can be made.

If your numbers $c$ and $d$ are not coprime (they have a common factor greater than 1), then there will never be a highest number that they cannot make, as they will only be able to make multiples of their highest common factor, and never be able to make a set of consecutive numbers.

Eg. If you have $4z$ and $6z$, their highest common factor is 2, and so you can only make numbers in the 2 times table, and never make any odd numbers.

If you have $40z$ and $60z$, their highest common factor is 20, and so you can only make multiples of 20.

Teachers' Resources

Why do this problem?

This problem offers students opportunities to explore fundamental ideas about number theory in a simple context. They are encouraged to explore, conjecture, generalise and justify.

There are opportunities for older students who are familiar with algebraic manipulation or modulo arithmetic to produce rigorous proofs.

Possible approach

This printable worksheet may be useful: How Much Can We Spend?

Introduce the context, just two coins 3z and 5z.

Ask students to combine these to make totals up to 20z.

Which totals can they make? Ask them to keep a record of their working.

Bring the class together to share results. Did anyone have strategies for working these out?

Ask for strategies for making totals greater than 20z.

It can be hoped that some students will have noticed that once they have found three consecutive totals they can make all successive numbers by adding on three.

There should now be agreement that:

7 is the largest total that cannot be made
8 and all numbers above can be made

'Could we have predicted this?'

Are there any conjectures?

'What do you think would happen if the two coins were 3z and 6z?'

'What about 3z and 7z? 3z and 8z? 3z and 9z?......'

Allow some time for the students to test and refine their conjectures.

Bring the students together to share their findings and display their results, focussing on the largest total that cannot be made and the number that follows.

Were any of the original conjectures correct? Which?

Can they now use the combined results to make some generalisations?

Can they use their generalisations to predict what will happen for any pairing of 3z with another coin?

With older students who are familiar with algebraic manipulation, there is an opportunity here to express the findings algebraically in different ways and convince themselves that they are equivalent.

Ask students to consider now what would happen when the pairings contain:

5z and another coin

7z and another coin...

any prime number value and another coin.

Working in twos or threes, ask students to make a display of their results.

Key questions

How do you know you can make all the totals after a certain total?

What happens when the other coin is a multiple of 3z? (or 5z or 7z...)

Does it make a difference if the other coin is 1 more or 2 more than a multiple of 3z? (or 5z or 7z...)

Possible support

The whole class introductory activity as described above should provide the necessary support for all students to access this problem.

Possible extension

Can students explain/justify/prove their findings?

Ask students to consider what happens if neither coin is a prime number.

Or search by topic

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners