The Coin Problem

I missed #beingmathematical the other week but I was working with some year 12 students at an event soon afterwards and I had given the title 'Number Theory for my workshop. I felt that serendipitously it was a perfect moment to try out some of the things I had seen.

I had been thinking of using The Coin Problem and this convinced me that it would be a perfect choice. I decided to present the idea in the more traditional way which was different to the above. This was because the students I was working with were about 17 and studying maths  A-Level.

I started by asking what would happen if we got rid of the 1 pence piece, which values would we no longer be able to make. I was intrigued by the answers. "We can't make 6", "No prime numbers", "No way of making 11". I let the students discuss and debate for a few minutes. They concluded that actually using just the 2 pence piece and the 5 pence piece they could make all numbers other than 1 and 3. I felt that this was an important thing to notice and I felt that students convincing themselves and each other was more valuable than me telling them. Their responses started with specific solutions, "we can make 11 with 5p 3 lots of 2p", but interestingly some of the students quickly generalised. "We can make all even numbers with just 2 pence pieces", "We can make 5 and then every odd number after by adding 2 pence pieces."

I then asked: "What numbers could we make with coins of other values? Imagine we had coins for 4p and 7p. What values could we make then?"

I gave them time to work on the problem for a while and listed the numbers up to 50 on the board. After a while I asked for suggestions of which numbers were possible. I ticked off the numbers that they suggested. For a few of the suggestions I asked for clarification as to how the number could be made. We had ticked off 20, 21, 22 and 23 and then one student said "We can make all other numbers..."

I was like "WHAT?! How can you be sure if you haven't checked them all?"

I probed with some questions and it was suggested that once we had 4 in a row we could then make all other numbers by adding multiples of 4 to each of these numbers. We thought on this for a moment.

I then noted that there was a largest number that we couldn't make. It was 17. We had shown that we could make all larger numbers.

I asked whether we might be able to find the largest impossible number for other pairs of numbers for example 3 & 11, 5 & 6 or 4 & 8.

Wandering round the room I head some great discussions, but very few representations other than lists of numbers. I wondered whether I had lead them astray by giving a not particularly useful representation when I was requesting responses so I paused their working and said that I thought they might like a tool to use. I wrote up the numbers in an array as below and briefly explained that I'd arranged them by their remainder when divided by 4 and that this was part of an area of maths called modular arithmetic.

Some groups jumped on this arrangement and quickly realised that if you could make a number then you could make all other numbers in the column. This is some working out from a group looking at 5p and 9p coins:

"How can we work out when the first full row will occur?"
"Can we find a generalised answer?"

Some students came up with formula to calculate the largest number that was impossible and I kept on wandering round saying "Ooh, thats an interesting conjecture. Does it always work? Does it work if we have a 4 pence piece and an 8 pence piece? Have you checked all possible numbers?" ... so much fun.

Some students realised that you couldn't have 2 even numbers as then you'd never make any odd numbers.
Some students wondered whether you needed one of the coins to be a prime number.

There is a nice proof using modular arithmetic but its a bit tricky if you haven't had much experience in this area of maths. I think I would have organised the order a bit differently if I had had more time. In this session I did want to get to the proof. When most students had found some kind of conclusion, whether a formula, or a pattern in the grid or a way of working out where the first complete row of possible numbers was in the table, I drew the group together and the students shared their findings. Interestingly many had found the same expression with different rearrangements. Some had looked at patterns they had seen in the answers and others had figured their expressions out from the structure of the grid.

Several of the group explained the limitations of the expression that they had found. Some had figured out that the two numbers couldn't be multiples of each other but we tightened the constraints and decided the numbers had to be co-prime.

Finally I talked through the proof. Many groups had got the outline of the proof so really I just had to fill in a bit of rigour. It was so lovely that they had noticed a whole bunch of useful points which I just had to tie together into a meaningful argument!

I have a new found love of this problem and I think it may become part of my regular repertoire!!