   Answer to brain tease question
  I have gotten this question for the third time on a test for a programming position and I can't seem to remember how to do this kind of problem. Anyhow the question is simple and I have an idea about how to do it but I can't quite figure it out.Question:Quote:You have a bucket of jelly beans. 32 are red, 48 are blue, and 16 are green. How many do you need to grab to make sure you have two of the same color?I am thinking at minimum you need to pick up 16 balls but beyond that my mind is a blank. Thanks for any help!   
  4 (will guarantee you have at least two of one of the colors)82 (will guarantee you have at least two of each of the colors)   ;Quote:Original post by toogreat4uI have gotten this question for the third time on a test for a programming position and I can't seem to remember how to do this kind of problem. Anyhow the question is simple and I have an idea about how to do it but I can't quite figure it out.Question:Quote:You have a bucket of jelly beans. 32 are red, 48 are blue, and 16 are green. How many do you need to grab to make sure you have two of the same color?I am thinking at minimum you need to pick up 16 balls but beyond that my mind is a blank. Thanks for any help!generally speaking, reading comprehension is an important skill in word problems.   ;  If I give you that bucket of jelly beans and ask you to pick out two reds or two blues or two greens (i.e. two of the same colour) then what are you going to do? You can't pick out less than two jelly beans otherwise you don't satisfy my request, rather you're going to pick out a first one and then hunt around for a second one of the same colour, at this point that makes two jelly beans of the same colour so you can stop there. The answer being two.If we try again but this time I blindfold you then that technique won't work, instead you could pick out three jelly beans and mentally examine the cases for what you might have:1) X, Y, Z  (Three jelly beans, one of each colour)2) X, Y, Y  (One jelly bean of one colour, two of another)3) X, X, X  (All three jelly beans the same colour)Cases 2 and 3 already satisfy the request of picking out two of the same colour, it's only case 1 that doesn't. Fortunately case 1 has the property that you're holding one of each of the colours, so if you just pick up one more jelly bean then it doesn't matter what colour it is you know you'll be holding two of one colour.So the answer is 4.   ;  I think this is the relevant principle:Pigeonhole;Quote:You have a bucket of jelly beans. 32 are red, 48 are blue, and 16 are green. How many do you need to grab to make sure you have two of the same color?The quick literal answer, as pointed out above, is 4.  You are not determining WHAT color you have two of but you will have two of one of them.Perhaps the question is testing you to see if you over think the problem and 'assume' that you must know the color you need two of?  The number of beans comes off as a red herring and is meant to make you over complicate it.   ;Quote:Original post by capn_midnightQuote:Original post by toogreat4uI have gotten this question for the third time on a test for a programming position and I can't seem to remember how to do this kind of problem. Anyhow the question is simple and I have an idea about how to do it but I can't quite figure it out.Question:Quote:You have a bucket of jelly beans. 32 are red, 48 are blue, and 16 are green. How many do you need to grab to make sure you have two of the same color?I am thinking at minimum you need to pick up 16 balls but beyond that my mind is a blank. Thanks for any help!generally speaking, reading comprehension is an important skill in word problems.I dont believe the problem is effected by choosing to think of it as picking balls(the item of choice in most probablity textbooks), or jelly beans.   ;Quote:Original post by toogreat4uQuestion:Quote:You have a bucket of jelly beans. 32 are red, 48 are blue, and 16 are green. How many do you need to grab to make sure you have two of the same color?Let's try probability theory[smile]Probabilities to grab red is Pr=32/96 ,Pb =48/96 etc.For red jelly,for example will be:probability do not grab  is  1-Prprobability do not grab for n attempts is (1-Pr)nprobability to grab after n attempts 1.0-(1-Pr)nprobability to grab 2 beans after n attempts is (1.0-(1-Pr)n)2total probability to grab any color twice is (1.0-(1-Pr)n)2+(1.0-(1-Pg)n)2+(1.0-(1-Pd)n)2 ,for some n this sum will be more than 1.0 -i.e.full confidence.This formula work only if you return jelly in bucket,otherwise you must correct probabilities,because  the amount of each color and the total amount change,so probabilityes change too.But this seems me too scientific.The most long case when  all colors were grabbed for 3 attempts,and you need 4th to grab another one,the color  don't care.[Edited by - Krokhin on June 20, 2009 7:49:27 AM];  In my opinion, all the answers presented here are way over-complicated. The problem is not about mathematics at all, but insight.   ;Quote:Original post by AndreTheGiantI think this is the relevant principle:PigeonholeYes, indeed. [smile]16 balls is far too many. There are three possible colors. The pigeonhole principle implies that if you have four balls, two must be of the same color. Four is the smallest number for which this is true, so the problem is solved.The pigeonhole principle is one of the greatest tools in problem solving. Here's a more interesting application of the same idea. Consider the finite arithmetic progression 1, 4, 7, ..., 100. Find the minimum integer n such that any collection of n distinct members of this sequence will have two distinct elements whose sum is 104. The most difficult part of solving this is the recognition that the pigeonhole principle can be applied; thus the hardest part is already done.   