wu :: forums
wu :: forums - Another Bag of Coloured Balls

Welcome, Guest. Please Login or Register.
Jul 30th, 2014, 2:04am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: william wu, Eigenray, Grimbal, SMQ, towr, Icarus, ThudnBlunder)
   Another Bag of Coloured Balls
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Another Bag of Coloured Balls  (Read 7683 times)
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Another Bag of Coloured Balls  
« on: Jun 6th, 2003, 12:25pm »
Quote Quote Modify Modify

A bag contains three different colours of balls. Initially, pulling two balls from the bag without replacement, there is a 1/3 chance that the balls will be the same colour. More balls are added, all of one of the existing colours, and the chance of pulling out a pair of the same colour has now increased to 1/2.
 
How many balls are now in the bag?

« Last Edit: Jan 6th, 2009, 3:07am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Another Bag of Coloured Balls  
« Reply #1 on: Jun 6th, 2003, 1:26pm »
Quote Quote Modify Modify

This is a very cool question. The fact that there's only one solution is quite incredible. I haven't proven it though--just brute-forced it. You must add 21 balls to increase the odds to 50%.
IP Logged

Doc, I'm addicted to advice! What should I do?
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Another Bag of Coloured Balls  
« Reply #2 on: Jun 6th, 2003, 1:37pm »
Quote Quote Modify Modify

I agree that it's a rather coool question. And that one needs brute force (or a good knowledge of what's possible with quadratic Diophantine equations). However, I don't agree that there is a unique solution. (But my intuition tells me that there would be, had there been only two different colours.)
 
« Last Edit: Jun 10th, 2003, 10:21am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Leo Broukhis
Senior Riddler
****





   


Gender: male
Posts: 459
Re: Another Bag of Coloured Balls  
« Reply #3 on: Jun 6th, 2003, 7:02pm »
Quote Quote Modify Modify

on Jun 6th, 2003, 1:26pm, James Fingas wrote:
This is a very cool question. The fact that there's only one solution is quite incredible. I haven't proven it though--just brute-forced it. You must add 21 balls to increase the odds to 50%.

 
Your brute-forcing is not brute enough:
 
Found third: 5 6 10  half: 6 10 33  
Found third: 6 10 12  half: 6 10 33  
Found third: 100 105 120  half: 105 120 451  
Found third: 105 120 126  half: 105 120 451  
 
C++ rules!
 
And I do not think there is a solution for two colors, because the only possibility for 1/3 is 2 balls of each color: the solution for x^2 + y^2 = xy + x + y.
« Last Edit: Jun 6th, 2003, 7:36pm by Leo Broukhis » IP Logged
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Another Bag of Coloured Balls  
« Reply #4 on: Jun 9th, 2003, 8:58am »
Quote Quote Modify Modify

There isn't a solution for 2 colours. If the probability of getting the same colour is 1/3 when there are 2 colours and the probability increases to 1/2 when k extra balls, of a different colour, are added, the conditions of the problem reduce to finding the solution of the quadratic 5k2+7k+4=0.
 
[e]Thanks for pointing out the typo, T&B[/e]
« Last Edit: Jun 9th, 2003, 4:01pm by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Another Bag of Coloured Balls  
« Reply #5 on: Jun 9th, 2003, 3:28pm »
Quote Quote Modify Modify

Sir Col, I think there's a typo in your first line.
 
I come to the same conclusion as you, but get a different quadratic.
 
With 2 colours, probability of choosing 2 balls the same colour
 
  a(a-1) + b(b-1)
=---------------- = 1/3
  (a+b)(a+b-1)
 
This gives a2 + b2 = ab + a + b
 
If we now add k balls of a different colour, we get
 
  a(a-1) + b(b-1) + k(k-1)
 ------------------------- = 1/2
  (a+b+k)(a+b+k-1)
 
Substituting a = b = 2, we get
 
k2 - 9k - 4 = 0, which has no integer solutions.
 
And if we add k balls of one of the original colours, we get
 
  (a+k)(a+k-1) + b(b-1)
 ------------------------ = 1/2
  (a+b+k)(a+b+k-1)
 
Substituting a = b = 2, we get
 
k2 - k - 4 = 0, which also has no integer solutions. Sad
 
In fact, if we use p instead of 1/2 (when balls are added), there is no p that gives an integer value  
for k in either scenario!
 
« Last Edit: Jan 6th, 2009, 3:59am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Another Bag of Coloured Balls  
« Reply #6 on: Jun 9th, 2003, 3:52pm »
Quote Quote Modify Modify

I've just checked again and you're right, I did make a mistake, but not where you're suggesting. Thanks for pointing out my typo though. Wink
 
Actually, I didn't build on Leonid's brute force solution for 2 colours. Instead I worked up from assuming that a solution exists for 2 colours, but did not attempt to solve it:
 
Starting with 2 colours, let n be the number of balls in total, a be the number of one colour and n-a the number of the other colour.
 
P(same colour)=a(a1)/n(n1)+(na)(na-1)/n(n1)=1/3.
 
This simplifies to n2(3a+1)n+3a2=0.
 
Adding k balls of another colour,
 
P(same colour)=a(a1)/(n+k)(n+k1)+(na)(na-1)/(n+k)(n+k1)+k(k1)/(n+k)(n+k1 )=1/2.
 
Simplifying to n2(4a+2k+1)n+k2k+4a2=0.
My mistake before was here, I had the coefficient of n equal to 4a2k1 Embarassed
 
Therefore, n2(4a+2k+1)n+k2k+4a2=n2(3a+1)n+3a 2.
 
Equating the coefficients,
4a+2k+1=3a+1, giving a=-2k.
 
k2k+4a2=3a2, giving k2k+a2=0.
 
Therefore, k2k+4k2=0, k(5k1)=0. That is, k=0 or k=1/5.
« Last Edit: Jun 9th, 2003, 4:03pm by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Another Bag of Coloured Balls  
« Reply #7 on: Jun 9th, 2003, 4:36pm »
Quote Quote Modify Modify

Argh! I've just written a programme to do the check and when my answers did not agree with Leonid's I realised that I had misinterpreted the problem. I assumed that the balls added are a new colour!
 
In which case, we get P(same colour)=(a+k)(a+k1)/(n+k)(n+k1)+(na)(na-1)/(n+k)(n+k1)=1/2.
 
And this simplifies to n2(2k+4a+1)n+k2k+4a2+4ak=0.
 
Equating n coefficients leads to the same result as before, 2k+4a+1=3a+1; that is, a=-k. Which means that there is no solution, as this would require k to be negative; in other words, removing balls! In fact, equating the constants and solving this leads to k=0 or k=1, which would have a=-1.
 
Obviously my brute force solutions agree with Leonid's.
 
An interesting twist is to invert the problem:
 
A bag contains two different colours of balls. Initially, pulling two balls from the bag without replacement, there is a 1/2 chance that the balls will be the same colour. More balls of a different colour are added and the chance of pulling out a pair of the same colour has now decreased to 1/3.  
 
How many balls are now in the bag?
 
 
Of course, there is an subtle connection with all of the above... Wink
« Last Edit: Jun 9th, 2003, 4:54pm by Sir Col » IP Logged

mathschallenge.net / projecteuler.net
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Another Bag of Coloured Balls  
« Reply #8 on: Jun 9th, 2003, 4:56pm »
Quote Quote Modify Modify

Which of Leonid's results are you referring to? He produced numbers for the 3-colour version, but we are doing the 2-colour version. The 3-colour version, although rather messy, also works out quite nicely and if I have time I will try to rework my previous results from way back.
 
« Last Edit: Jan 6th, 2009, 4:00am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Sir Col
Uberpuzzler
*****




impudens simia et macrologus profundus fabulae

   
WWW

Gender: male
Posts: 1825
Re: Another Bag of Coloured Balls  
« Reply #9 on: Jun 9th, 2003, 5:13pm »
Quote Quote Modify Modify

on Jun 9th, 2003, 4:56pm, THUDandBLUNDER wrote:
(Which of Leonid's results are you referring to?

Both. If you look at my expression for the probability after the balls were added, you will see that previously I added k balls of a new colour. When I ran my programme and, obviously got no solution for the 2 balls, tried the 3 balls. However, I did not get a solution then either. Upon re-reading the problem I realised that you said k new balls were added, although all the same colour, they were also the same colour as one of the original colours. I was effectively introducing a fourth colour!
IP Logged

mathschallenge.net / projecteuler.net
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Another Bag of Coloured Balls  
« Reply #10 on: Jun 14th, 2003, 9:33pm »
Quote Quote Modify Modify

Quote:
A bag contains two different colours of balls. Initially, pulling two balls from the bag without replacement, there is a 1/2 chance that the balls will be the same colour. More balls of a different colour are added and the chance of pulling out a pair of the same colour has now decreased to 1/3.
How many balls are now in the bag?

With a balls of one colour and b balls of another colour, probability of choosing two balls of the same colour  
 
  a(a-1) + b(b-1)  
= ---------------- = 1/2  
  (a+b)(a+b-1)  
 
This gives (a-b)2 = a+b  
 
Let  
a = u(u+1)/2  
b = u(u-1)/2  
u = 2,3,4,5...  
 
Now, adding k balls of a different colour, probability of choosing two balls of the same colour  
 
  a(a-1) + b(b-1) + k(k-1)  
= ------------------------- = 1/3  
  (a+b+k)(a+b+k-1)  
 
3[a(a-1) + b(b-1) + k(k-1)] = (a+b+k)(a+b+k-1)  
 
Solving for k gives  
 
2k = (a+b+1) +/- [3(a+b)+1)]1/2  
  = (u2+1) +/- [3u2+1]1/2
 
Substituting u = 4 gives a = 10, b = 6, and k = 5 or 12
Substituting u = 15 gives a = 120, b = 105, and k = 100 or 126
etc.
 
In contrast to the previous puzzle, here there are always TWO solutions for k for every solution for a and b.
 
In fact, there are integer solutions whenever 3u2+1 is a perfect square.
 
And there are infinitely many solutions to 3u2+1 = x2
 
This is an example of Pell's equation - remember Archimedes' cattle problem?
 
What is the relationship between this problem and the original problem?  
 
For the original problem we can write
 
 a(a-1) + b(b-1) + c(c-1)
------------------------ = 1/3  
  (a+b+c)(a+b+c-1)
 
 a(a-1) + b(b-1) + c'(c'-1)
-------------------------- = 1/2 (where c' > c)
  (a+b+c')(a+b+c'-1)
 
to be continued...  
 
Wink
 
« Last Edit: Jun 16th, 2003, 1:58pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Another Bag of Coloured Balls  
« Reply #11 on: Jan 4th, 2009, 1:27am »
Quote Quote Modify Modify

on Jun 14th, 2003, 9:33pm, THUDandBLUNDER wrote:

What is the relationship between this problem and the original problem?

 Cheesy
Look at the brute forced solutions: 6,10, 105, 120,....
 
Let a = n(n-1)/2, b = n(n+1)/2.  If c' = 1+2n2, the second probability is 1/2.  For the first probability to be 1/3, we need 1+3n2 to be a perfect square!  But are these all solutions?
 
6, 10, {{5, 12}, 33}
105, 120, {{100, 126}, 451}
1540, 1596, {{1520, 1617}, 6273}
21736, 21945, {{21660, 22022}, 87363}
303810, 304590, {{303525, 304876}, 1216801}
4235505, 4238416, {{4234440, 4239482}, 16947843}
59007816, 59018680, {{59003840, 59022657}, 236052993}
821928240, 821968785, {{821913400, 821983626}, 3287794051}
11448190270, 11448341586, {{11448134885, 11448396972}, 45793063713}
...
« Last Edit: Jan 4th, 2009, 1:29am by Eigenray » IP Logged
osheen
Newbie
*





   


Posts: 2
Re: Another Bag of Coloured Balls  
« Reply #12 on: Jan 6th, 2009, 5:05am »
Quote Quote Modify Modify

intially there are 6 ball later 2 more balls of same colour are added to make the probability 1/2
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Another Bag of Coloured Balls  
« Reply #13 on: Jan 12th, 2009, 5:19pm »
Quote Quote Modify Modify

I have just noticed that this thread has received thousands of hits. Must be because there is a link to it on Nick Hobson's site.
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board