Interview Question: Coins

Sample Question #238 (brainteaser)
 
[This is a classic]
 
There are five bags containing the same number of coins. Four of the bags contain gold coins while the last bag contains silver coins coated with gold, and you are told that each gold coin weighs 10 oz. and each silver coin weighs 2 oz. less. You have a weighting scale (minimum=8 oz., maximum=large enough so you can weigh all five bags of coins) and you can take coins out of the bags. What’s the minimum number of weighings you need to do in order to tell which bag has the silver coins?
 
[I was asked this question at a State Street on-site a few years ago]
Advertisements
This entry was posted in Sample Qs. Bookmark the permalink.

6 Responses to Interview Question: Coins

  1. Brett says:

    ANSWER
     
    Like most brainteasers, once you know the answer, it just seems so damned obvious!
     
    The answer is "one."
     
    Take 1 coin from the first bag, 2 from the second bag, 3 from the third bag, 4 from the fourth bag, and 5 from the last bag. You weigh these 15 coins. If all were gold, you’d get 150 oz. in total weight. But since some of the 15 coins are fake, you get x oz. where x<150. Then, (150-x)/2 gives you the number of fake coins in this sample, which allows you to know which bag is the one full of silver coins.
     
    So you only need to do one weighting in order to tell which bag has the silver coins.
     

  2. Monad says:

    Shouldn’t the number of fake coins be (150-x)/8 in this case?Anyway, I think you have a great blog which introduces what being a quant is like without all the BS like most other websites. Your blog entries about a life as a quant offers a more realistic point of view, which is useful especially to people like me who is currently contemplating work or a post-doc after I finish my PhD in comp sci.

  3. Brett says:

    Hi, Monad! The divisor should be 2. Here’s an example.
     
    Suppose among the 15 sample coins, 2 are silver, which means the total weight will be 4 oz. (2oz. x 2) less than the "ideal" total of 150 oz. In other words, the actual total weight for the sample will be 1(10)+2(8)+3(10)+4(10)+5(10) = 146 oz., which is 4 oz. less than 150 oz.
     
    Divide this shortfall of 4 oz. into 2 gives you 2 silver/fake coins.
     
    -brett

  4. Monad says:

    You are right. I made a silly mistake and thought that the silver coins weight 2oz so that’s why I made the divisor 8oz.

  5. Handong says:

    You can actually achieve by taking coins from first 4 bags.Take i coins from i-th bag for i=1,2,3,4.Assuming the total weight is x. Then do y=mod(x,10)/2.  If y=0, then y=5.y is now the bag that contains the silver coins.

  6. Brett says:

    ahbuchen: would that work? Let’s say the first bag holds the silver coins. Then the total weight in your answer, x, is 98. Mod(98,10)=8, and 8/2=4, which is your y.
     
    But you’re right in saying we only need to take coins from 4 bags. Then since the total weight of the 1,2,3,4 gold coins is 100, then if x is 100, we know the 5th bag holds the silver. If x<100, then (100-x)/2 gives you the number of fake coins in the sample.
     
    Thanks for your contribution!
    -brett

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s