Sunday, August 5, 2012

Cents on the Dollar, Some Attempts

How much of a dollar bill can you cover up using change for a dollar? The coins must not overlap one another.

(See previous post and the one before that.)

I made a few attempts at this, see pictures below.

Version 1, wide-open. Here I covered the dollar bill with 45 pennies, going for a hexagonal lattice. I'm guessing this covered a percentage of the dollar in the mid- to high-80's. (One easily shows that an infinite hexagonal lattice covers a fraction Pi*Sqrt[3]/6, or a little less than 91%, so I'm assuming the below is pushing up against that limit.)

Version 2, intermediate. I nudged the configuration above in order to make room for the additional coins to touch the dollar bill - that seemed to force a decision to remove five of the pennies and replace the nickel with a dime.

I did some quickie image analysis on the above awful picture to give me some inputs for a Monte Carlo calculation of the covered area:

The result was just under 85% coverage. I didn't do a sensitivity analysis. I'm guessing this configuration is low- to mid-80's.

Version 3, tight. Here, my attempt uses 8 dimes, 15 pennies and a nickel. According to the spreadsheet, this configuration covers just over 64% of the dollar.

It would be nice to be able to replace that nickel with 5 pennies - according to the spreadsheet, that would bump the area up to 74.6%. But I wasn't seeing quite enough room to do that, and truth be told I have put a lot more time into blogging this puzzle than I've spent trying to solve it. Feel free to blow these attempts out of the water!


I thought of this puzzle after daydreaming the following exchange between a bank teller and an eccentric customer:

"May I help you?"
"I'd like change for a dollar."
"Here you go!" (Hands the customer four quarters.)
"Why, you cheat! I had 16 square inches' worth of currency and you gave me back only 3 square inches' worth!"
"I'm sorry, sir. Here are 7 dimes and 30 pennies instead."
"OK, close enough...."

I thought it was amusing, this image of a person valuing an exchange along a totally irrelevant dimension. As if one were to share a long kiss with somebody, and then become upset because the other person took a different number of breaths than you did.


The above puzzle takes the form, "How many X can you cover with Y?" I'm sure there a lot of problems and solutions of this nature to be found in the literature on circle-packing. I don't know that literature, but a quick search just now turned up some neat pictures here.

Thursday, August 2, 2012

Cents on the Dollar, Ctd

How much of a dollar bill can you cover up using change for a dollar? The coins must not overlap one another.

Yesterday I played the game three times, under three different conditions:
Version 1: Wide-open. In this version, you don't have to use all the coins. Equivalently, we might characterize things by saying that while you do have to place all of the coins adding to $1.00 on the table, not all of the coins on the table have to touch the dollar bill. Also, those coins that do touch the bill are allowed to protrude beyond its edges.
Version 2: Intermediate. All of the coins adding to $1.00 have to touch the bill. Coins are allowed to protrude beyond the edges.
Version 3: Tight. All of the coins adding to $1.00 have to lie within the boundary of the bill. 
(The spreadsheet is appropriate for scoring attempts that meet the constraint in Version 3.)

On Monday I'll post a picture of my attempt at each version.