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

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

Quote from: thepenguin77 on June 25, 2012, 11:49:00 pm

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 :P

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)

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

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.

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.

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.