1
$\begingroup$

I am trying to work out the number of scenarios I can cover with a given set of coin combinations so I can decide when I have the optimal amount of change to carry.

For the sake of the example, lets not consider notes €5, €10, etc. Or coin denominations smaller than €0.10 - so €0.05, €0.02, €0.01 etc.

So that leaves us with using the following euro coin denominations: €2, €1, €0.50, €0.20, €0.10. Lets consider this 1 complete set of coins.

Lets say tomorrow I go to the shop and purchase something for €3.40. If I have only 1 set of coins:

I must use 1x€2.00, 1x€1.00, 1x€50, resulting in change of €0.10 returned. Leaving me with 1x€0.20 and 2x€0.10 coins.

However, If I have 2 sets of coins. I could cover a single scenario of much greater quantity than any one set allows. But, more importantly, I could possibly have a larger number of scenarios. If the scenarios are smaller than any 1 set, I could definitely cover 2 scenarios. But I might struggle to cover a third unless it is small.

If I continue like this, now holding 3 sets of coins. Assuming any scenario is less than any 1 set of coins. I can definitely cover 3 scenarios. But it is also likely I could cover a 4th or 5th scenario.

Continuing on with 4 sets of coins. And again with 5 or 6 sets.

What I am asking is, how can I maximise the number of scenarios I can cover, with the minimum number of coins. There is also the possibility of covering amounts larger than any one set alone. So for example with 4 sets of coins. I could easily cover any amounts smaller than all 4 sets of coins, any single set of coins, any double set of coins, and a triple and single set. But if I use them in any one of those scenarios, there is still a possibility I could cover 1 or even more than 1 additional scenario. That is have enough change left if I need it.

I would like to know how to work this out?

What I am trying to do is very practical. Instead of carrying whatever coins I have in one pocket. I want to split my coins up. I want to always know that if I carry X number of coin sets. I will have enough to cover Y number of scenarios. Then I can carry that number of coin sets in 1 pocket, and have random coins in the other. Then at the end of the day, I can reset my coins or know what I must do the next day to ensure I have the right amount of coins to cover a given number of possible scenarios. I want to do this instead of carrying around a random number of random coins, having the check my coinage at every transaction to see if I have enough.

Additional concepts for clarity.

One of the comments so far have suggested I look at Integer Partitions. After a quick look (I am not a mathematician and have not had a lot of time to research this area, so please forgive my ignorance). I would like to point out one important factor. That is, we do NOT have an infinite number of coins. We only have the coins in our set or sets, and whatever change we can receive as a result of using those coins or sets. So we actually do have a very finite number of scenarios. In other words, we cant magically keep pulling €2.00 coins out of the clouds once we have used all our €2.00 coins.

I also used the word "Reasonable" in my comments, I should not have used that word. I left it there to not break the flow.

What would be considered an acceptable answer? A solution that shows some of the possibilities of a finite set or sets of coins and how to calculate the rest for myself. So for example, if you want to use €2.00, €1.00 and €0.50 and ignore others (or any other subset of the coins in the original question). It must also be in line with a practical example. You must think in terms of having these physical sets of coins in your pockets. If you have 4 sets of coins, you have 4 pockets and once a set is broken, you can only use what remains to help other sets if they too get broken. So lets say you have 2 sets. But the first visit to the shop used the lower 2 denomination coins from the first set. But the second visit to the shop used the upper 2 denomination coins from the second set. You can still go back to the shop because you can effectively combine the two broken sets into a complete set and sill even have 1 extra €0.50 cent coin. I hope this is making more sense. The only thing I don't want is that we start considering infinite coins. It has to remain in line with what you could do if you physically had a fixed set or sets of coins. I don't want to be running around robbing grannies at gun point for their coins because my set is broken.

What I am looking for is how to work out mathematically (if possible) the practical problem you see every day of picking change from a set of coins. This way I can say. Oh. I have too many ten cent coins. Let me exchange them, or vice versa, and so my change does not build up very far beyond the number of coins I actually need for most daily scenarios. Or better yet, if I am travelling somewhere, and I want to ensure I have enough coins to give the taxi driver or pizza delivery guy, or waiter, the right amount of change and maybe even a little tip. How many sets of coins should I bring, and more importantly, how many should I ensure I have on my return journey?

I hope this clarifies things better.

$\endgroup$
9
  • $\begingroup$ Clearly, the more coins you carry the more scenarios you can cover. The maximum would be many purchases with the single smallest coin. For a useful answer you need to tell us how likely the different scenarios are. In fact you might be better off with a mix of coins favoring some amounts over others rather than full sets. In any case that's what you will have after you've made a few purchases and gotten change. So in essence I think the real question you are asking involves probabilities, and is difficult to nail down. $\endgroup$
    – Ethan Bolker
    Commented Nov 8, 2017 at 13:55
  • $\begingroup$ Interesting comment. Thanks. Maybe I misunderstood. If something costs €0.10 and you had only 1 set of coins. Are you going pay with the 1 ten cent coin, or will you pay with one of the others. Lets assume, you will pay with the 1 ten cent coin. Then later you find something else of the same value, you would likely use the next smallest denomination. The twenty cent coin. But am I not right in assuming that there is a small finite number of reasonable scenarios for a given number of coin sets? €2 + €1 + €0.5 + €0.2 + €0.1 = €3.80 ... Continued... $\endgroup$
    – Francis Rodgers
    Commented Nov 10, 2017 at 2:38
  • $\begingroup$ With coins summing to $38$ units (tenths of a euro each for you) you can buy $38$ items each of which costs $1$ unit. It doesn't matter which order you use the coins in since you get change. $\endgroup$
    – Ethan Bolker
    Commented Nov 10, 2017 at 2:43
  • $\begingroup$ €3.80 / €0.10 = 38 possible scenarios you could cover if every scenario was €0.10. €3.80 / €0.20 = 19 possible twenty cent scenarios. €3.80 / €0.5 = gives you only 7 scenarios for fifty cents (you cant have .6 of a scenario you either have one or you don't). €3.80 / €1.00 = 3 scenarios with a 1 euro coin. €3.80 / €2.00 = 1 scenario with a two euro coin. Finally, €3.80 / any amount over €2.00 but less than €3.80 also = 1 scenario. However I don't think you can add or multiply all those scenarios, because once you use a coin, it is gone. I just don't know how to do the combination of sets. $\endgroup$
    – Francis Rodgers
    Commented Nov 10, 2017 at 2:47
  • $\begingroup$ With coins summing to $38$ units (tenths of a euro each for you) you can buy $38$ items each of which costs $1$ unit. It doesn't matter which order you use the coins in since you get change. The number of possible transactions is the number of ways to partition $38$. That's a known number = $26,015$, though not obviously easy to compute: wolframalpha.com/input/?i=partitions+of+38&wal=header When you start asking about "reasonable" transactions you're out of mathematical territory. The number is finite, of course. $\endgroup$
    – Ethan Bolker
    Commented Nov 10, 2017 at 2:48

1 Answer 1

Reset to default
1
$\begingroup$

One set of coins plus an extra $0.10$ or an extra $0.20$ will let you pay any amount without having to get change. The only amounts you cannot pay with one set alone are $0.40, 0.90, 1.40, 1.90, 2.40, 2.90$ and either of these coins will cover that. An extra $0.20$ has the advantage that you can pay every amount with the minimum number of coins. If you also carry an extra $2$ you have a minimum coin solution all the way up to $5$ where the notes take over.

$\endgroup$
3
  • $\begingroup$ Thank you ross. I appreciate the concise answer. It is very interesting. But I am much more interested in how you came up with this. It's possible you could get the accepted answer if you can show me how you arrived at it as I am trying to understand the maths behind it. $\endgroup$
    – Francis Rodgers
    Commented Nov 10, 2017 at 3:54
  • 1
    $\begingroup$ The numbers are small enough to just try it. If you had coins in binary you would only need one of each, but $0.1+0.2$ is only $0.3$, leaving a gap before you can use $0.5$. That means you need to fill the gap, and either $0.1$ or $0.2$ will do it. The same thing happens at whole euros because you again have $1,2,5$ which leaves a gap at $4$. Coins are generally layered, as they are in euros. You have the generation of $0.01$s, then the generation of $0.1$s, then the $1$s and so on. The euro comes in $1,2,5$ in each generation, so the gaps repeat each time. $\endgroup$
    – Ross Millikan
    Commented Nov 10, 2017 at 4:00
  • $\begingroup$ Thank you for explaining your method. I am actually sitting down with a set of coins and playing with it. $\endgroup$
    – Francis Rodgers
    Commented Nov 10, 2017 at 4:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .