Making Change

[Charlie Reams]

Making change in England is easy. To give someone 99p of change, you first give them as many of the largest denomination as possible (50p), then as many of the next (2x 20p), and so on (no 10p's, 1 5p, 2 2p's.) This simple method guarantees that you will hand over the smallest number of coins possible.

There are some coin systems where this is not so easy. Imagine the basic units were 1p, 5p and 6p. The naive way to make 10p is [6p, 1p, 1p, 1p, 1p]. But clearly [5p 5p] is much more efficient. So the "greedy" method falls down for this coin system, and it's difficult to see a fast method to make change efficiently in this system.

So the question is, how can you tell which coin systems have the nice property that the English system has?

[Jon O'Neill]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

[Charlie Reams]

I don't actually know the answer. That seems like a good start, but can you prove it?

[Jon O'Neill]

I'm an ideas man, not a proofs man.

[Steven Tew]

You need a proper mathematician on this one.

[Howard Somerset]

I haven't looked carefully at this one yet, but some of us can remember when we had the half crown in the uk currency. The ratio of the value of the half crown to the florin, the next coin down, was 5:4. Shopkeepers were well acquainted with giving something like two half crowns and three florins when a customer needed eleven shillings change and there wasn't a ten shilling note in the till.

I'll come back to this one soon.

[Howard Somerset]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

To answer Charlie's question, I would modify Jono's response slightly.

I'd say if you put the coins in ascending order, then each coin's value has to be a multiple of the value of the previous coin.

I'm not convinced yet, but I've a gut feeling that it's correct.

[Matt Morrison]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

To answer Charlie's question, I would modify Jono's response slightly.
I'd say if you put the coins in ascending order, then each coin's value has to be a multiple of the value of the previous coin.
I'm not convinced yet, but I've a gut feeling that it's correct.

Doesn't apply to English currency though - 50p not a multiple of 20p, 5p not a multiple of 2p.

[Michael Wallace]

My first instinct was Jono's suggestion, but proving it is probably nontrivial, but I'm taking a 5 minute break from trying to work to give it a go.

Start off with your smallest coin, and let it have value a. Now to make your currency efficient under the greedy algorithm, your next coin value must be such that to make the value 2a requires at most two coins under that method. If your coin is greater than or equal to 2a in value, than that's fine. But what if it is smaller than 2a (but still greater than a)?

Let this value be b, so that a < b < 2a. Can we find a b such that 2a can be made by 2 coins? Yes, but only if we make 2a by a + b or b + b, in either case b = a and we've contradicted ourselves. So for a 2 coin currency, b must be greater than or equal to 2a.

I'd go on, but I do actually need to get back to work (or to put it another way, make tea and get back to work).

edit: Actually, isn't that it? It's true for 2 coins, and then suppose you have a set of n coins and want to add another coin to that set, by the same argument your n+1th coin must be at least double the largest coin in your set (i.e. induction). But that seems remarkably straightforward, so I've probably got something wrong.

[Howard Somerset]

I''d say if you put the coins in ascending order, then each coin's value has to be a multiple of the value of the previous coin.
I'm not convinced yet, but I've a gut feeling that it's correct.

Doesn't apply to English currency though - 50p not a multiple of 20p, 5p not a multiple of 2p.

er - how true.

[Matt Morrison]

I''d say if you put the coins in ascending order, then each coin's value has to be a multiple of the value of the previous coin.
I'm not convinced yet, but I've a gut feeling that it's correct.

Doesn't apply to English currency though - 50p not a multiple of 20p, 5p not a multiple of 2p.

er - how true.

Could be really anal and mention the £5 coin not being a multiple of £2 too
Damn 5s and 2s eh.

[Howard Somerset]

Having made a total idiot of myself in my earlier post, I'll try to regain some credibility now.

I can demonstrate that Jono's suggestion is not correct, by showing a counter example.

Suppose there is a currency containing three coins: 1p, 4p and 9p. This meets the criterion than each is at least double the next smallest.

However, if we try to make up the sum of 34p, the "biggest first" algorithm gives us 3 9p coins, 1 4p coin and 3 1p coins, making 7 coins in total. 34p can be obtained more efficiently by using 2 9p coins and 4 4p coins - 6 coins in total.

[Michael Wallace]

Having made a total idiot of myself in my earlier post, I'll try to regain some credibility now.

I can demonstrate that Jono's suggestion is not correct, by showing a counter example.

Suppose there is a currency containing three coins: 1p, 4p and 9p. This meets the criterion than each is at least double the next smallest.

However, if we try to make up the sum of 34p, the "biggest first" algorithm gives us 3 9p coins, 1 4p coin and 3 1p coins, making 7 coins in total. 34p can be obtained more efficiently by using 2 9p coins and 4 4p coins - 6 coins in total.

Excellent, I thought my 'proof' was too straightforward.

edit: and now I think about it, it obviously was too straightforward since it didn't take into account the effects of the lower denominations

[Jon Corby]

I'm gonna guess that the next coin up has to be equal to or greater than [next lowest coin + two times the next lowest coin after that].

I have no proof/reason whatsoever for this at the moment

[Howard Somerset]

Excellent, I thought my 'proof' was too straightforward.

edit: and now I think about it, it obviously was too straightforward since it didn't take into account the effects of the lower denominations

I'd been looking the same way that you were going - prove it for just two coins, and then apply the principle of induction. But I had trouble moving from n to n+1. And then realised the conjecture was wrong, and it didn't take too long to find the counter-example.

I think that the actual requirement is far more complicated, and each gap depends on the other gaps in the series.

[Matt Morrison]

I'm gonna guess that the next coin up has to be equal to or greater than [next lowest coin + two times the next lowest coin after that].
I have no proof/reason whatsoever for this at the moment

There's a distinct possibility you just wanted to come up with some crazy formula to see some numpty try and work it out. If so, I'm your numpty.

Anyway, by 'work it out' I mean 'attempt to disprove it' which is the way this thread has been going.

I think what you mean is, if you have coins 1, 2, 3, and 4, then, for example, coin 4 must be equal or greater than coin 3 + (2 x coin 2).

If so, these coins fit:
Coin 1: 1p (there is no means to use your formula here as it has no lower denominations)
Coin 2: 4p (it has only one lower denomination so have had to do = 3x Coin 1 rather than = 1x Coin 1 + 2x 'Coin 0')
Coin 3: 9p (equal or greater to 4p + (2 x 1p) which is 6p)
Coin 4: 20p (equal or greater to 9p + (2 x 4p) which is 17p)

With these denomations, 27p would be made with a 20p, a 4p, and 3x 1p (5 coins) using the 'greedy method' but could be made more efficiently with 3x 9p coins.

I'm beginning to think this whole thing is so circumstantial that any working formula is going to be pretty hectic.

[Paul Howe]

I think Howard's idea always gives a set of coins for which the greedy algorithm is optimal. An x-pence coin will be a multiple of all the coins of lower value, so it's impossible to write a number greater than x as a sum of the lower coin values without a subset of that sum equalling x. Note this wasn't true of the (6,5,1) example where we could make 20 = 5+5+5+5, and no subset of those adds to 6.

Now, suppose we've made change in a non-greedy way, i.e. we've picked the coins in some order and at some point foregone the choice of the largest possible coin, say x-pence. We still need to make up that x-pence from coins of smaller value though, and because of the multiplicative property some of these smaller valued coins will sum to x and we can replace them with a single x-pence coin. This new solution uses fewer coins and hence the non-greedy solution wasn't optimal. You can iterate this until you're left with the greedy solution. Hope that makes sense, couldn't be bothered writing it out more formally. I believe that coins with Fibonacci values might work using roughly the same argument, I'm a bit tentative on that one though.

Of course Charlie asked for a way to test an arbitrary set of coins, not a specific example that just happens to work. I've got a vague feeling this may be equivalent to the knapsack problem (don't take this as gospel!) and hence there isn't a simple formula, rather for any specific set of coins you can do little better than brute force checking of a lot of combinations.

Reading that back I didn't express myself too great, but I cannae be bothered to aim for greater clarity so hopefully you can puzzle it all out.

[Gary Male]

I also have no idea what's going on with the puzzle, but it does remind me of a similar puzzle. There are 2 values of coins in an arbitrary monetary system, one worth 29p and one worth 17p. What's the largest value that cannot be paid exactly using just those coin values? And in the general case what is the largest value that cannot be paid exactly with 2 values of coins sharing those properties?

Maybe that will help shine some light on this puzzle. Or not.

[Paul Howe]

I believe that coins with Fibonacci values might work using roughly the same argument, I'm a bit tentative on that one though.

Actually, scrap that bit, it's turd. The rest I think is OK.

[Jon Corby]

I'm gonna guess that the next coin up has to be equal to or greater than [next lowest coin + two times the next lowest coin after that].
I have no proof/reason whatsoever for this at the moment

There's a distinct possibility you just wanted to come up with some crazy formula to see some numpty try and work it out. If so, I'm your numpty.

Thanks

[Charlie Reams]

I've got a vague feeling this may be equivalent to the knapsack problem (don't take this as gospel!) and hence there isn't a simple formula, rather for any specific set of coins you can do little better than brute force checking of a lot of combinations.

It is similar to the knapsack problem, but different enough that the solution might be completely different (think how much easier the continuous knapsack problem is than the discrete one, even though it's almost identical.)

[Nicky]

I've been reverse engineering this one. In the system we have each new denomination is either twice the previous one, or twice the previous one plus the one before it.

ie,
1 = a
2 = b = 2a
5 = c= 2b +a
10 = d = 2c
20 = e = 2d
50 = f = 2d +c
100=g = 2f

So, I think we have these possible alternative sequences: 1,2,4,8,16,32... and 1,2,5,12,29,70,169...

Now I'm going to go and work out if we could also have d = 2c+b+a and so on.

(If I'm right, do I get a VFSMB?)

[Nicky]

Oh...and what's the knapsack problem?

[Michael Wallace]

Oh...and what's the knapsack problem?

http://tinyurl.com/bdvl53

[Paul Howe]

Oh...and what's the knapsack problem?

http://tinyurl.com/bdvl53

Haha, awesome.

Thinking about this some more, finding the fewest coins to make change for any particular amount is a special instance of the knapsack problem (all the "weights" are 1, and we're subject to an equality constraint rather than an inequality), this additional structure might make it easier to solve than the generalised knapsack, then again it might not.

The problem is there are potentially an infinite number of different amounts you have to check, so you can check the greedy algorithm works up to a billion pounds, but how do you know it won't fail for 3,823,135,125.76? If you could show there was an upper bound such that if non-greedy optimal solutions exist then one must fall below this bound, you'd just have to apply knapsack to all the amounts below the bound (which would hopefully be something not to terrifying like linear or quadratic in the size of the largest coin amount). It seems kind of intuitive that such a bound should exist, but I have no idea whether it actually does or how to go about proving it. That's not especially satisfying, but to me it does have the air of a "hard" problem with no magic bullet solution.

In short, I dunno.

[Nicky]

Sorry, should've tried googling. *facepalm*

EDIT: I've figured out WHY I didn't google - I was thinking of it as 'that knapsack problem we were talking about earlier', rather than 'The Knapsack Problem'. I'd have expected results along the lines of 'need a knapsack? No problem! Come to Knapsacks R Us!' I did actually search this site for 'knapsack' before asking - thinking it might be a puzzle someone had posted here!

(Not that I feel the need to justify myself, or anything... )

[Ian Volante]

I don't think so, but does this help?

http://en.wikipedia.org/wiki/Package-merge_algorithm

[Neil Zussman]

Having made a total idiot of myself in my earlier post, I'll try to regain some credibility now.

I can demonstrate that Jono's suggestion is not correct, by showing a counter example.

Suppose there is a currency containing three coins: 1p, 4p and 9p. This meets the criterion than each is at least double the next smallest.

However, if we try to make up the sum of 34p, the "biggest first" algorithm gives us 3 9p coins, 1 4p coin and 3 1p coins, making 7 coins in total. 34p can be obtained more efficiently by using 2 9p coins and 4 4p coins - 6 coins in total.

But 1,4,9 will ever be the entire system. Otherwise doing the weekly shopping would be a bit of a mission. The next coin may be 19p, in which case the Greedy algorithm works.

In the English number system, we have 3 basic starting values, 1 2 5, and then we multiply these by multiple of 10 (10, 20, 50, 100, 200, 500 etc.). I wonder if doing this would always work? i.e. 1 4 9 becomes 1 4 9 10 40 90 100 400 etc. I suspect not, but will hold out hope until a counterexample is found. It certainly works for 34p...
I would also guess that having the basis values satisfying Jono's hypothesis would be best. Although then again 1 2 3 seems to work...
I don't know. This is not a problem for 10:40pm. Interesting problem at all other times though.

[Gary Male]

In the English number system, we have 3 basic starting values, 1 2 5, and then we multiply these by multiple of 10 (10, 20, 50, 100, 200, 500 etc.). I wonder if doing this would always work? i.e. 1 4 9 becomes 1 4 9 10 40 90 100 400 etc. I suspect not, but will hold out hope until a counterexample is found. It certainly works for 34p...

27p

[Neil Zussman]

In the English number system, we have 3 basic starting values, 1 2 5, and then we multiply these by multiple of 10 (10, 20, 50, 100, 200, 500 etc.). I wonder if doing this would always work? i.e. 1 4 9 becomes 1 4 9 10 40 90 100 400 etc. I suspect not, but will hold out hope until a counterexample is found. It certainly works for 34p...

27p

Bollocks. Scrap that then.
Square numbers? The presence of the 25p ensures that both 27p and 34p work. But I'm sure there's another value that fails. Although again, I'm gonna be lazy and not try to find it.

[Gary Male]

In the English number system, we have 3 basic starting values, 1 2 5, and then we multiply these by multiple of 10 (10, 20, 50, 100, 200, 500 etc.). I wonder if doing this would always work? i.e. 1 4 9 becomes 1 4 9 10 40 90 100 400 etc. I suspect not, but will hold out hope until a counterexample is found. It certainly works for 34p...

27p

Bollocks. Scrap that then.
Square numbers? The presence of the 25p ensures that both 27p and 34p work. But I'm sure there's another value that fails. Although again, I'm gonna be lazy and not try to find it.

12p

Sorry.

[Gavin Chipper]

Does a system count as working if the greedy method ties with another one?

Anyway, looking through all the other posts, it seems that no-one has definitively come up with a system they are happy is correct, so I'll come up with some stuff of my own.

Let's say we're starting a system of coins from the lower end and working up. Systems that can get any integer amount have to have a 1 in them. The next one up from that can be anything at all for fairly obvious reasons.

Actually systems that don't need any integer amount to be possible can start with any number (a) (but it doesn't matter if they have to have every amount because a can just be 1). The next one after that (b) has to be a multiple of it or the next multiple of a higher than b will be less than a more than b and will be impossible to get using b. The greedy system doesn't work here. But any multiple of a will do.

Any system where the next coin up is a multiple of the previous one definitely works.

But for the third coin (c) I think the greedy method can force a tie if it is 2b-a. But I think it will always win if it is 3b-a, 4b-a and so on.

I think that for any coin in the sequence, if it is twice the previous one minus one of the others, then the greedy method will always force a draw. But if it is 3 or more times minus one of the others then it will always win. Also maybe if it is x times the previous minus x-2 of the other coins (probably with repeats allowed).

This is all speculation but I'm too tired to think about it any more.

[Neil Zussman]

Square numbers? The presence of the 25p ensures that both 27p and 34p work. But I'm sure there's another value that fails. Although again, I'm gonna be lazy and not try to find it.

12p

Sorry.

It's my own fault. I noticed earlier when Howard found fault with Jono's original solution that 1 4 9 broke down because Greedy algortihm gives 3x1 + 1x4 + 3x9, whereas optimal is 4x4 + 2x9. These solutions differ only in how the last 12p is made (both use 2x9 + 1x4 = 22, leaving just 12p from the original 34) So I really should've checked that the 12p problem was fixed.

[Simon Myers]

Not sure if (or even if, how) this adds to the discussion, but I think (counterexample in 5, 4, 3...) any coin system using 1 and the first n (for any n>=0) prime numbers should always work in the greedy way (e.g. 1, 2, 3, 5, 7 for n=4).

Even if I'm right, prime numbers could well be a special case anyway.

[Gary Male]

Not sure if (or even if, how) this adds to the discussion, but I think (counterexample in 5, 4, 3...) any coin system using 1 and the first n (for any n>=0) prime numbers should always work in the greedy way (e.g. 1, 2, 3, 5, 7 for n=4).

Even if I'm right, prime numbers could well be a special case anyway.

...2, 1, counterexample.

£21.70. Greedy would use a £21.61, 7p and 2p coin. An optimal method would be a £21.53 and 17p coin.

[Paul Howe]

I mentioned Fibonacci numbers in an earlier post, and dismissed them, but I can't think of a counterexample for any set of Fibonacci coins (e.g. [1,2,3,5,8] is one possible set, [1,2,3,5,8,13,21] is another), so maybe they do work.

Over to you, Gary.

[Gary Male]

I mentioned Fibonacci numbers in an earlier post, and dismissed them, but I can't think of a counterexample for any set of Fibonacci coins (e.g. [1,2,3,5,8] is one possible set, [1,2,3,5,8,13,21] is another), so maybe they do work.

Over to you, Gary.

They probably work because of the nature of Fibonacci numbers, there's no strange boundaries that get crossed where there's no covering numbers like with prime numbers. There's a huge number of ties but that doesn't DQ them under the terms of the stated question.

[Gary Male]

Fibonacci numbers work. Proof to big and complex to write here at this time of night. Will leave to Andrew Wiles to explain.

[Gary Male]

While I'm here, is there an example that counters this theory:

1: There must be a 1p coin.
2: The gap between each coin must be the same or greater then the preceding gaps of lower calue coins.
3: From the 4th coin onwards, you must be able to make change for that coin from any combination of just the previous 2 coins.

And I'm tired (I have genuinely sat through Benjamin Button tonight) so this may have been raised in full earlier and I missed it, or a counter has already been posted, or something.

[Adam Dexter]

I might be lowering the tone, but I nearly jizzed when a customer purchased £1.12 worth of things, and handed over a £20 note... one of those magical times... can anyone see why?

[Ian Volante]

I might be lowering the tone, but I nearly jizzed when a customer purchased £1.12 worth of things, and handed over a £20 note... one of those magical times... can anyone see why?

Yes, £18.88, an amount that can be made with exactly one of each lower denomination. Although if I was that customer, I wouldn't be happy receiving change from someone that's in a state of almost jizzing.

[David Roe]

While I'm here, is there an example that counters this theory:

1: There must be a 1p coin.
2: The gap between each coin must be the same or greater then the preceding gaps of lower calue coins.
3: From the 4th coin onwards, you must be able to make change for that coin from any combination of just the previous 2 coins.

And I'm tired (I have genuinely sat through Benjamin Button tonight) so this may have been raised in full earlier and I missed it, or a counter has already been posted, or something.

On a quick check, looks good to me.

But I thought if you watcched Benjamin Button, you started the film tired but were wide awake at the end of it?

[Chris Corby]

Although if I was that customer, I wouldn't be happy receiving change from someone that's in a state of almost jizzing.

Well, it feels nice to come into the money sometimes

[Naomi Laddiman]

Although if I was that customer, I wouldn't be happy receiving change from someone that's in a state of almost jizzing.

Well, it feels nice to come into the money sometimes

lol!

[Gary Male]

While I'm here, is there an example that counters this theory:

1: There must be a 1p coin.
2: The gap between each coin must be the same or greater then the preceding gaps of lower calue coins.
3: From the 4th coin onwards, you must be able to make change for that coin from any combination of just the previous 2 coins.

And I'm tired (I have genuinely sat through Benjamin Button tonight) so this may have been raised in full earlier and I missed it, or a counter has already been posted, or something.

On a quick check, looks good to me.

But I thought if you watcched Benjamin Button, you started the film tired but were wide awake at the end of it?

Hmm, unless I'm missing something you can add a 35p coin to our currency and screw up part 3 of my theory. More thought required. And fewer films.

[Gavin Chipper]

Does a system count as working if the greedy method ties with another one?

Anyway, looking through all the other posts, it seems that no-one has definitively come up with a system they are happy is correct, so I'll come up with some stuff of my own.

Let's say we're starting a system of coins from the lower end and working up. Systems that can get any integer amount have to have a 1 in them. The next one up from that can be anything at all for fairly obvious reasons.

Actually systems that don't need any integer amount to be possible can start with any number (a) (but it doesn't matter if they have to have every amount because a can just be 1). The next one after that (b) has to be a multiple of it or the next multiple of a higher than b will be less than a more than b and will be impossible to get using b. The greedy system doesn't work here. But any multiple of a will do.

Any system where the next coin up is a multiple of the previous one definitely works.

But for the third coin (c) I think the greedy method can force a tie if it is 2b-a. But I think it will always win if it is 3b-a, 4b-a and so on.

I think that for any coin in the sequence, if it is twice the previous one minus one of the others, then the greedy method will always force a draw. But if it is 3 or more times minus one of the others then it will always win. Also maybe if it is x times the previous minus x-2 of the other coins (probably with repeats allowed).

This is all speculation but I'm too tired to think about it any more.

Right, coming back to this, I think my method doesn't look too bad to me even after a couple of days. A couple of things though - if you're getting the next denemination up by multiplying the previous one by x and taking away some of the other denominations, there are cases where you can take away more than x-2 of them. For example, in our system you multiply 20p by three and take away 10p, which is in fact a perfect example of x-2. But as 10p is a multiple of lower denominations, you can take away more than x-2 of them. But that doesn't really count.

And with Fibonacci numbers (as Paul Howe mentioned) they may work, but not because there's anything particularly special about them, but because they come under the larger system. If you start with 1, 2, 3, 5, 8, 13, then 13, for example, can be made by multiplying 8 by 2 and taking away one of the previous numbers. Fibonacci numbers are only greedy half-frinedly though. 10 can be made by going with the 8 and the 2 but it can be equalled with two 5s, so the greedy method is only joint best in some cases.

Anyway, I think my system works quite well as a method of finding systems that are greedy-friendly, but while it may only turn out greedy systems, it doesn't necessarily turn out all possible greedy systems.

I might start with 1 then pick another arbitrary number for the second coin - 6. But then let's say I pick 10 for the next one. This seems to fail. 12 can be got with two 6s, but using the 10, you need 10, 1, 1. My system would never come up with denoninations that start off failing, even even they can be sorted out with higher denominations.

What I mean is that while 1, 6, 10 fails, a larger system might work with 1, 6 and 10 as the first three. The fourth coin might be 12, which repairs some of the earlier damage. But there are further problems. 18 is a problem. Make that a coin. And so on I'm not sure if the rot can be stopped or if a system that starts badly has to end badly (by going on forever).

My hunch is that once the rot sets in you can't get rid of it, so I'm sticking with my initial answer. To summarise:

To make a coin system, start with a number (1 if that's what is has to be) and then the next denomination up from any one along the line is x times the previous one minus up to x-2 of any of the other denominations with repeats allowed (or x-1 of them for a greedy joint-wining system). It can be more than x-2 of lower denominations that are factors of higher ones, as long you can make it back up from the new denomination to x times the previous denomination using x-2 coins. So 50p is 3*20p minus 10*1p (x is 3 here) but because 1p is a factor of 10p you can still get from 50p to 3*20p (60p) with x-1 (1) coins, by just using the 10p.

[Jon O'Neill]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

[Gary Male]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Fibonacci appears to disprove that. Also an outlandish system where every coin is 1p higher in value than the previous coin right down to 1p disproves that but that's hardly in the spirit of the puzzle.

[Junaid Mubeen]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Wrong...(1p, 2p, 3p) being a counterexample.

[Jon O'Neill]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Fibonacci appears to disprove that. Also an outlandish system where every coin is 1p higher in value than the previous coin right down to 1p disproves that but that's hardly in the spirit of the puzzle.

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Wrong...(1p, 2p, 3p) being a counterexample.

Oh yeah. Hmmm...

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

[Gary Male]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Fibonacci appears to disprove that. Also an outlandish system where every coin is 1p higher in value than the previous coin right down to 1p disproves that but that's hardly in the spirit of the puzzle.

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Wrong...(1p, 2p, 3p) being a counterexample.

Oh yeah. Hmmm...

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

You're 10 days too late.

[Junaid Mubeen]

Haha, admittedly I only read the top and bottom posts and hardly anything in between. Can someone summarise (briefly) where we are up to? Sounds deceptively simple but I suspect there is no uniform solution.

[Gary Male]

Haha, admittedly I only read the top and bottom posts and hardly anything in between. Can someone summarise (briefly) where we are up to? Sounds deceptively simple but I suspect there is no uniform solution.

So far we've established that if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

What?

Oh, lots of maths stuff at a level I can't understand, but a basic premise that if a coin can't be made exactly from the coins directly below there's gonna be some odd boundary crossings which stops greedy from working. Fibonacci almost certainly works for that reason. Adding 1p to every coin is either a special case, or is the key to the whole puzzle. Rucksacks are good for hiking, and is probably related to this puzzle as another special case.

[Gavin Chipper]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Wrong...(1p, 2p, 3p) being a counterexample.

It works in that it fits Charlie's initial definition in a rigid sense - it "guarantees that you will hand over the smallest number of coins possible" but to get 4p you can equal the greedy system (3p + 1p) with another way (2p + 2p). To make the greedy system outperform the others, I think it has to be at least double and I think this is more satisfying.

Double the previous one (and take away up to one of the lower denominations for a draw) or
Triple it and take away up to one of the lower denominations (or two) or
Quadruple it and take away up to three of the lower denominations (or four) etc.

For example, under my more demanding system if you start with 1, 6 then the next one could be 12, 17, 18, 22, 23, 24, 27, 28, 29, 30, 32, 33, 34, 35, 36 and then anything higher than that, so anything from 32 up.

[Gary Male]

I reckon if you put the coins in ascending order, each coin has to be at least double the value of the previous coin.

Right?

Wrong...(1p, 2p, 3p) being a counterexample.

It works in that it fits Charlie's initial definition in a rigid sense - it "guarantees that you will hand over the smallest number of coins possible" but to get 4p you can equal the greedy system (3p + 1p) with another way (2p + 2p). To make the greedy system outperform the others, I think it has to be at least double and I think this is more satisfying.

Double the previous one (and take away up to one of the lower denominations for a draw) or
Triple it and take away up to one of the lower denominations (or two) or
Quadruple it and take away up to three of the lower denominations (or four) etc.

For example, under my more demanding system if you start with 1, 6 then the next one could be 12, 17, 18, 22, 23, 24, 27, 28, 29, 30, 32, 33, 34, 35, 36 and then anything higher than that, so anything from 32 up.

Unless we transport the system to Zimbabwe I think we have to assume that there's going to be a highest value coin. Adding more coin values just to cover gaps is very unsatisfactory. Using just the values quoted 56p would break the system.

How about another approach: If the lowest two values in a 3-coin system are 1p and 10p, what's the highest value after that that would break the system? The lowest value that doesn't break the system? Ditto 4 coins for the highest system-breaking (assume 3rd coin is the next value after the highest system-breaker) and lowest safe (assume lowest safe 3rd coin) 4th coin.

[Gary Male]

Oh, Charlie, what made you think of the original question anyway? Do you work for AQA on the side, this question was texted in and you need the 40p commission? It's the sort of stupid thing I'd text.

[Charlie Reams]

Oh, Charlie, what made you think of the original question anyway? Do you work for AQA on the side, this question was texted in and you need the 40p commission? It's the sort of stupid thing I'd text.

I hate having change and one of my favourite activities is putting weird combinations of coins into vending machines in order to get the minimal number of coins back after I buy something. So I was thinking about how vending machines know what change to give, and it occurred to me that that it's very easy for our particular coinage system (and any real coinage system I've ever encountered), but then I wondered whether it was so easy in general.

[Gavin Chipper]

For example, under my more demanding system if you start with 1, 6 then the next one could be 12, 17, 18, 22, 23, 24, 27, 28, 29, 30, 32, 33, 34, 35, 36 and then anything higher than that, so anything from 32 up.

Unless we transport the system to Zimbabwe I think we have to assume that there's going to be a highest value coin. Adding more coin values just to cover gaps is very unsatisfactory. Using just the values quoted 56p would break the system.

How about another approach: If the lowest two values in a 3-coin system are 1p and 10p, what's the highest value after that that would break the system? The lowest value that doesn't break the system? Ditto 4 coins for the highest system-breaking (assume 3rd coin is the next value after the highest system-breaker) and lowest safe (assume lowest safe 3rd coin) 4th coin.

Actually what I meant was that after 6, each those others were possibilities for the third coin, not having all of them.

If we have 1p and 10p then the lowest value that doesn't break the system would be 19p or 20p depending on whether ties are allowed. I'm going with 20p saying they're not.

Using my more demanding system, I think 91p is the highest value that would break the system. You can get to 100 with ten coins just using the 10p and also ten coins using the 91p and nine 1ps. It's a tie (Or you could say it's 81p - you can get to 90p with nine 10ps, which beats the greedy system which needs ten coins).

If you keep working up like this, the lowest coin for next one is always double the previous one under the demanding system, and double the previous one minus one for the relaxed system.

For the highest system breaker we will call the previous highest coin y. Under the demanding system y^2-y+1 will break the system. Under the relaxed system the highest breaker would be (y-1)^2. I think.

[Charlie Reams]

Ties definitely are allowed.

[Gavin Chipper]

Ties definitely are allowed.

OK, so the lowest value for the next coin up is double the previous value minus one. And the highest system breaker is the (previous one minus one) squared. All assuming there is a 1 in the system. But it's easily fiddled with.