Least amount of change

[thepenguin77]

Now this might be a rather simple problem, but I don't think it is. I'm asking this partially because I'm too lazy to figure it out right now, and also because I feel it will give people an opportunity to think. (This might even end up requiring a program to solve)


So, no one likes to carry around change (coins) and my question is, what coins should you enter a store with so that sum of the number of coins you enter a store and leave a store with is at a minimum?

The general idea here is that you basically want to carry the least amount of change. So, the way this works, is you pick E number of coins to enter with, after buying your items (which have random number of cents) you leave with L number of coins. You want to minimize L + E.

Rules:

• We're using American coins, so the choices are: penny - .01, nickel - .05, dime - .10, quarter - .25 (no half dollars, too rare )
• The number of cents your purchase costs is random (So, a purchase would cost some dollar amount + [0 - 99] cents)
• You receive the minimum number of coins from the cashier ($.90 is not 9 dimes)

Have at it. You'll of course have to provide some sort of justification for your answer.

Spoiler for accepted answer:

Well, it looks like runer had it right from the start. Carrying 0 coins really is the best option.

I believe the solution is to carry no change.

Whatever the cost of your purchase is and whatever coins you have, you can ensure you leave with the minimum amount of change possible by giving the vendor all of your change. Whatever coins properly contribute to the payment, the vendor will keep; the coins that do not will be returned to you. Since the cents amount of the purchase is an equally-distributed random number, subtracting your constant amount of change from this will result in another equally-distributed random number (mod 100). Whatever amount of change you contribute, the vendor will always have to return to you coins that sum to an equally-distributed random amount of cents from 0-99.

You cannot limit the amount of coins you end with, so the optimal solution is simply to limit the amount of coins you begin with.

And with 2 brute force checks to back this, I'm happy. It looks like I've been doing it right all along.

[ruler501]

isnt it 4 pennies one nickel two dimes and 3 quarters since you can make any change out of that combination

for 1-4 cents use the pennies
for 5-9 use one nickel and the neccesary pennies
for 10-19 use 1  dime and the pennies/nickel for the remainder
for 20-24 use two dimes and pennies
for 25-29 use quarter and pennies
for 30-34 use quarter, nickel and pennies
for 35-39 use quarter, dime and pennies
etc.

and i have 3 half dollars if you look for them they are still rare but not too hard to find a few
I also have a dollar coin and thats pretty rare or at least used to be

[thepenguin77]

Yes, that's how you make a number. But the idea here is that there is a purchase in the middle.

Basically, I want to have a certain set of coins in my pocket when entering a store so that when I leave, I will also have a small amount of change.

Let's say the correct answer is a quarter and a dime. I would then have to show that 2 + (all of the possible numbers of coins I could be holding when leaving) is more optimized for my quarter-dime scenario than any other set of entering coins.

[ruler501]

depends is it just when you leave that you count coin or the average of when you left/entered?

[someone]

So, no one likes to carry around change (coins) and my question is, what coins should you enter a store with so that sum of the number of coins you enter a store and leave a store with is at a minimum?

The general idea here is that you basically want to carry the least amount of change. So, the way this works, is you pick E number of coins to enter with, after buying your items (which have random number of cents) you leave with L number of coins. You want to minimize L + E.

Rules:

• We're using American coins, so the choices are: penny - .01, nickel - .05, dime - .10, quarter - .25 (no half dollars, too rare )
• The number of cents your purchase costs is random (So, a purchase would cost some dollar amount + [0 - 99] cents)
• You receive the minimum number of coins from the cashier ($.90 is not 9 dimes)

You enter with no coins & you leave with no coins, and that is the least amount of change you have to bring. If you want to buy something, use a credit card

[ruler501]

So, no one likes to carry around change (coins) and my question is, what coins should you enter a store with so that sum of the number of coins you enter a store and leave a store with is at a minimum?

The general idea here is that you basically want to carry the least amount of change. So, the way this works, is you pick E number of coins to enter with, after buying your items (which have random number of cents) you leave with L number of coins. You want to minimize L + E.

Rules:

• We're using American coins, so the choices are: penny - .01, nickel - .05, dime - .10, quarter - .25 (no half dollars, too rare )
• The number of cents your purchase costs is random (So, a purchase would cost some dollar amount + [0 - 99] cents)
• You receive the minimum number of coins from the cashier ($.90 is not 9 dimes)

You enter with no coins & you leave with no coins, and that is the least amount of change you have to bring. If you want to buy something, use a credit card

cheating

I think we agreed on irc that you enter with none so that the max you will ever have is 10(see my first reply for why)

[Juju]

That's cheating.

Let's break up in denomination of less than $1, 25¢, 10¢ and 5¢, respectively.

So to make anything less than $1, you'll need 3 quarters max.
Less than 25¢: 2 dimes max.
Less than 10¢: 1 nickel max.
Less than 5¢: 4 pennies max.

So 3 quarters, 2 dimes, 1 nickel and 4 pennies will make anything 1-99¢. The amount of coins when you enter will be at minimum and when you go out will also be at minimum since the cashier won't give you any change.

Or else you can carry one $1 coin (we have that in Canada, dunno in US) and the cashier will give minimum change.

[ruler501]

That's cheating.

Let's break up in denomination of less than $1, 25¢, 10¢ and 5¢, respectively.

So to make anything less than $1, you'll need 3 quarters max.
Less than 25¢: 2 dimes max.
Less than 10¢: 1 nickel max.
Less than 5¢: 4 pennies max.

So 3 quarters, 2 dimes, 1 nickel and 4 pennies will make anything 1-99¢. The amount of coins when you enter will be at minimum and when you go out will also be at minimum since the cashier won't give you any change.

Or else you can carry one $1 coin (we have that in Canada, dunno in US) and the cashier will give minimum change.

i say this is the same as my original answer event though i didnt explain all of it or understand the problem

[Runer112]

I believe the solution is to carry no change.

Whatever the cost of your purchase is and whatever coins you have, you can ensure you leave with the minimum amount of change possible by giving the vendor all of your change. Whatever coins properly contribute to the payment, the vendor will keep; the coins that do not will be returned to you. Since the cents amount of the purchase is an equally-distributed random number, subtracting your constant amount of change from this will result in another equally-distributed random number (mod 100). Whatever amount of change you contribute, the vendor will always have to return to you coins that sum to an equally-distributed random amount of cents from 0-99.

You cannot limit the amount of coins you end with, so the optimal solution is simply to limit the amount of coins you begin with.

[Builderboy]

I did the math, and if you carry in no coins at all, you will leave on average with 4.7 coins.  However, if you carry with you 1 penny, you will be able to spend it 4 out of 5 times, reducing your average to 4.11 coins.  This is not a solution, just shows that the solution is not to carry no coins.

[ruler501]

time to brute force it
I could write a program to do that but i think someone should make the proof first of what is best

[nitacku]

The answer is finding the least amount of change that allows you to match most combinations possible.

You'll need 4 pennies so you can fill the gap between nickels.
Adding in 2 nickels and 1 dime lets you cover all values from 1-24.
It follows that adding in 3 quarters would then cover all values from 1-99
So the following combination is the least amount of change you should carry:

4 pennies
2 nickels
1 dime
3 quarters

Since the distribution of purchase costs are random in this scenario, it follows that on average, half of your coins will be used (or at least close to that).

Actually, this would be the solution if you wanted to minimize the amount of change you received. But this isn't the solution to this particular problem. Using the solution presented above coupled with the fact that the cashier will always present the least amount of change, that means you will receive on average 5 coins. Knowing this means that you also know the probability of receiving a particular coin.

pennies: 40%
nickels: 20%
dime: 10%
quarters: 30%

So you want to select 5 coins with the highest probability.
In that case, you would select 4 pennies and 1 quarter.

[Builderboy]

nitacku I already showed that if you carry *no* coins, you will receive 4.7 coins back on average, so if you are going to be carrying in any coins at all, you will have to carry less than 5 at the very least.

EDIT: And i revoke my previous decision that carrying no change was not the best solution, I was doing bad math I know think that it is indeed the best solution.

EDIT2:  I un-revoke my previous decision.  For some reason I was under the impression that you had to spend all of your input change but that is untrue!  There are cases where *not* spending additional coins can actually save you coins.  For example if a product cost 1.00 and you gave them 2.00 instead of 2.01, you would get no coins as change instead of 9 coins.  Now to actually set up code to have the program give the optimal number of change...

[nitacku]

Yes you are indeed correct Builderboy. However, 4.7 coins is not an integer amount. So carrying 5 coins is still the optimal solution.

Here's my thoughts:
You know you will get 4.7 coins back on average, which is 5 coins when viewed as an integer amount.
To minimize your change, you need to predict what 5 coins those will be on average.

[Builderboy]

That logic does not follow.  If one person receives an average of 4.7 coins every transaction, and another person receives an average of 5 coins per transaction, the person with 5 coins will wind up with more coins overall, even though he would have been getting integer amounts of coins each time.

EDIT: plus, even if you pick 5 optimized coins, you will still be getting some coins back on average, and including your starting coins your average will still be far above 4.7