## Thursday, July 19, 2012

### Predicting the Value of a Bunch of Coins

This is the last part of the 'Coin trilogy'. Here's part-1 and part-2. In this post, we attempt to answer questions on predicting the value for a bunch of coins for which we only know its weight but not the exact internal distribution among coin types.

If somebody gave you the option of choosing either the value of a kilo of coins or 40\$, which will you pick?
Using CPLEX, we determine that the maximum possible value for 1000 grams of pennies, nickels, dimes, and quarters is 44.05\$, so if you took the 40\$, there is a small chance you will incur a loss. If the bag was packed with 400 pennies (weighs exactly a kilo), you'll make a 36\$ profit. If the coins types were uniformly distributed, its value would be about 26\$, and you would make a 14\$ profit.

Say you believe you have 100\$ worth of coins in a jar that you want to cash out at a Coinstar machine. How much would that weigh? A lower bound for that answer is 2.268 Kilos. If the coin types were uniformly distributed in the jar, you would carry about 3.7 Kilos.

What kind of coin ratios does a vending machine carry? This online post author made enough purchases to empty out a vending machine and found this:
Quarters:Dimes:Nickels in the ratio 1:2:1.175

Assuming that the vending machine has to satisfy exact change for any value between 5c and 95c in 5c increments, a minimum weight solution is:
Nickels:1, Dimes:9 (10 coins, weight 25.412g) with zero quarters. However, by adding a secondary objective of also minimizing the number of coins (limited coin capacity?), we obtain the following alternative optimal solution that threw away 5 dimes and picked up 2 quarters:
Nickel:1, Dime:4, Quarter:2 (7 coins, 25.412g)

Quarters and Dimes are now present in the same ratio as that in the vending machine. However, our model doesn't like nickels much (although a melted nickel was once worth more than its value).

I have a digital counting jar that displays the current value of the coins currently in the jar. It currently reads \$20.05, and its weight (excluding the empty jar) is about 700 grams. For this weight, the maximum value is 30.85\$. If my coins were uniformly distributed in the jar, the model predicts a "maximum" value of 18.7\$, which means that I have relatively more dimes and/or quarters in my mix. A dime and a nickel have the exact same bang-to-buck ratio, i.e. value/weight ratio, which is a source of the alternative optimal solutions discussed in part 2.

US Mint Production
Averaged over 2010-2011, the coins are produced in the approximate ratio:
p:n:d:q
12:1.5:3.5:1

Quite different from our preferred ratios calculated in part-1 and part-2. At this rate, my 700 gram jar would contain only about 15\$ and a kilo of coins in this ratio would be worth about 18\$.