Spare Change question

Brussels Sprout

I saw the following as an example telephone interview question for a company:

Let's say I have 50 coins in my hand, that add up to a dollar. One falls out. What is the chance that it is a penny?

The only way I know how to solve this is through brute force. Is there a quick logical trick that I'm missing?

Relevant: American coins are 1, 5, 10, 25 and 50 cents

ray giraffe

Can't use 50 cent coin.

Also number of 1 cent coins used must be multiple of 5.

Try each multiple of 5 in turn for the number of 1 cent coins.

im invisible

Zero chance, it might be a cent though...




(yeah ok, they probably call cents pennys in the US, but still...)

click_here!!!

Someone could hack out a computer simulation!

Maybe there is no right answer: they might be just trying to suss out how you think or if you're good at coping with pressure.

Does anyone know if that problem would be similar to this? I think it is.XKCD NP-Complete Appetizers. If you change the value of appetizers you would like to buy to $1.00, and change the cost of each type of appetizer to 1 cent, 5 cent,etc.

Or maybe there is a way of doing this, and I wouldn't have got the job. :pac:

I'm not an expert on this.

hivizman

This may be one of those things that every American knows (how to make change for a dollar with exactly 50 coins). Ray Giraffe's comment about the number of one-cent coins having to be a multiple of 5 is a good starting point. Clearly you can't have 50 one-cent coins or more, as this won't leave enough for other coins to make up the full dollar. On the other hand, you can't have 35 one-cent coins or less, as you have to make at least 65 cents with nickels, dimes and quarters, but the maximum number of coins you need is going to be less than 50 minus the number of one-cent coins you have already used (65 cents requires at most 13 coins, but adding the 35 one-cent coins uses only 48 coins in total).

Another way of thinking about this is that, for every five one-cent coins you exchange for a nickel, you lose 4 coins in total. If you started with 100 one-cent coins, then you have too many coins until you swap 50 for nickels, but you have to swap more than 50 to be able to make up the full dollar. If you swap 65 coins for nickels, you will have only a maximum of 48 coins for the full dollar.

So you need investigate only combinations of 40 one-cent coins with 10 more coins to make the remaining 60 cents or 45 one-cent coins with 5 coins to make the remaining 55 cents. You should find one combination that works for 40 and one for 45 one-cent coins.

There are mathematical techniques that can be used for these problems, but in this case informed brute force is quicker.

razor425

85% using hivizman's method below. Assuming the chances of getting 40 1c coins is equal to the chances of getting 45 1c coins. Probably not a valid assumption in real life but the most appropiate method for solving this problem IMO.