Author |
Topic: Colored Balls (Read 7299 times) |
|
Bassem
Guest
|
I got this riddle today over a phone interview for MS. it goes like this: You have a single box full of balls of four different colors. 45 Black, 38 White, 25 Blue and 9 Green balls. What is the maximum number of balls that you need to pull from the box to be able to get two balls of the same color(which can be any color).
|
|
 IP Logged |
|
|
|
Neelesh
Junior Member
Gender: 
Posts: 147
|
 |
Re: Colored Balls
« Reply #1 on: Nov 17th, 2005, 11:04am » |
 Quote  Modify
|
on Nov 17th, 2005, 10:53am, Bassem wrote:| I got this riddle today over a phone interview for MS. it goes like this: You have a single box full of balls of four different colors. 45 Black, 38 White, 25 Blue and 9 Green balls. What is the maximum number of balls that you need to pull from the box to be able to get two balls of the same color(which can be any color). |
|
Maximum number of balls : 45 + 38 + 25 + 9 = 117
(I am so dumb that I am unable to understand that I got the two balls of the same color unless I pull out all of them ....)
 Ooops probably you meant "the number of balls in the worst case" or something like that
So in the worst case, 4 + 1 = 5 balls.
Or may be I have not understood the question properly.
|
|
IP Logged |
|
|
|
Bassem
Guest
|
You understood it correctly Neelesh. 5 is the correct answer.
|
|
IP Logged |
|
|
|
krishnaiah narukulla
Guest
|
(I got this riddle today over a phone interview for MS. it goes like this: You have a single box full of balls of four different colors. 45 Black, 38 White, 25 Blue and 9 Green balls. What is the maximum number of balls that you need to pull from the box to be able to get two balls of the same color(which can be any color).
Total number of balls in worst case is=45+38+25+1=109
Best case: 1+1=2
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Colored Balls
« Reply #4 on: Dec 27th, 2005, 7:32am » |
Quote Modify
|
You might want to rethink that worst-case answer...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Colored Balls
« Reply #5 on: Dec 27th, 2005, 10:49am » |
Quote Modify
|
Can we choose the balls as we take them from the box? 
|
|
IP Logged |
|
|
|
deoBRAT
Newbie
Posts: 2
|
|
Re: Colored Balls
« Reply #6 on: Feb 6th, 2006, 5:17am » |
Quote Modify
|
Hey, the answer is very simple.
Consider this -
You have balls of 4 colors. In the worst case, if you pick up 4 balls, they will all be of different colors. The fifth ball you pick up, has to match with at least one of the balls picked up earlier.
So the answer is - 5 balls.
|
|
IP Logged |
|
|
|
koojealion
Newbie
Posts: 3
|
|
Re: Colored Balls
« Reply #7 on: Mar 27th, 2006, 7:13pm » |
Quote Modify
|
I think the question was lost in translation. The answer 5 is right, but the question should be, "What is the minimum number of balls you must pull out to be sure to get two of a color?"
(not "what is the maximum?")
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Colored Balls
« Reply #8 on: Mar 27th, 2006, 11:48pm » |
Quote Modify
|
No, maximum is right. Because the minimum is when you take two balls of the same color at the start. Once you have two of the same color, you're sure you have them.
But you never need to take more then 5 to be sure there's at least two of the same color. So that's the maximum you need.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Colored Balls
« Reply #9 on: Mar 28th, 2006, 8:27am » |
Quote Modify
|
It all depends whether you can look at the ball you have taken out or not.
If you need to take them out in the dark and you only see later what are the colors, you need to take minimum 5. If you just pull balls until you have a matching pair, it is maximum 5.
|
|
IP Logged |
|
|
|
NumBeast
Newbie
Posts: 6
|
|
Re: Colored Balls
« Reply #10 on: May 12th, 2006, 1:04pm » |
Quote Modify
|
For the porposes of this or similar problems, the number of balls(or other objects) doesn't matter, it is only the number of types of balls(or other objects) that makes any difference.
|
|
IP Logged |
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Colored Balls
« Reply #11 on: Jul 24th, 2006, 6:37am » |
Quote Modify
|
This was asked from me and my friend too Seems lot of ppl at MSFT failed to answer this and hence it became a test bench.
|
| « Last Edit: Jul 24th, 2006, 6:38am by algo_wrencher » |
IP Logged |
|
|
|
TheNumberScott
Full Member
Gender:
Posts: 210
|
|
Re: Colored Balls
« Reply #12 on: Oct 29th, 2006, 5:40pm » |
Quote Modify
|
hmmm, what would it be if you pulled 2 balls at the same time, then discarded them if they were not the same color? I don't know the answer yet, but it seems interesting, and a little harder than the other way.
Also, what color would they be?
|
| « Last Edit: Oct 29th, 2006, 6:04pm by TheNumberScott » |
IP Logged |
There once was a man who hurt his shins. So he went to the doctor to get some help, and they gave him shins of rebar!
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Colored Balls
« Reply #13 on: Oct 29th, 2006, 10:01pm » |
Quote Modify
|
on Oct 29th, 2006, 5:40pm, TheNumberScott wrote:hmmm, what would it be if you pulled 2 balls at the same time, then discarded them if they were not the same color? I don't know the answer yet, but it seems interesting, and a little harder than the other way.
Also, what color would they be? |
|
In the worst case you can pull them all out 2 at a time and never get a pair that are the same color. For example, it's possible that the first 34 times you get black/white, the next 4 times blue/white, then 11 times blue/black, then 9 times blue/green, and finally have just one blue left.
It might be more challenging to ask the following:
1) Suppose you pull out balls 2 at a time and discard them if they aren't the same color? What's the expected (average) number of tries until you either get two of the same color or run out of balls?
2) Suppose instead that you pull out balls 2 at a time, and if they aren't the same color, you drop them back in the box. Then what's the expected number of tries until you get two the same color?
I didn't work these out.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
shrek43
Newbie
Posts: 1
|
|
Re: Colored Balls
« Reply #14 on: Jan 4th, 2007, 4:38pm » |
Quote Modify
|
its 5 because there are only 4 different colors, 5 would gaurantee that u get 2 of the same color.
|
|
IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Colored Balls
« Reply #15 on: Mar 9th, 2007, 12:23am » |
Quote Modify
|
on Oct 29th, 2006, 10:01pm, TimMann wrote:
2) Suppose instead that you pull out balls 2 at a time, and if they aren't the same color, you drop them back in the box. Then what's the expected number of tries until you get two the same color?
|
|
We might end with picking same 2 balls of different color rite ?
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Colored Balls
« Reply #16 on: Mar 10th, 2007, 2:31am » |
Quote Modify
|
2. Is easy:
I count rounds (pulling two, throwing them back if different colour).
The probability that we get two of the same colour in any draw (and so already at the first) is:
P = 45/117*46/116+38/117*37/116+25/117*24/116+9/117*8/116 = cca 30%.
So the expected number of rounds is:
E = P*1 + (1-P) * (E+1), or E = 1/P, cca. 3.34 rounds.
1. Is much more complicated, at the moment I do not see an easy way, other than a brute force calculation.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove