Author 
Topic: Another Bag of Coloured Balls (Read 9001 times) 

ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Another Bag of Coloured Balls
« on: Jun 6^{th}, 2003, 12:25pm » 
Quote 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 6^{th}, 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
Gender:
Posts: 949


Re: Another Bag of Coloured Balls
« Reply #1 on: Jun 6^{th}, 2003, 1:26pm » 
Quote Modify

This is a very cool question. The fact that there's only one solution is quite incredible. I haven't proven it thoughjust bruteforced 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:
Posts: 4489


Re: Another Bag of Coloured Balls
« Reply #2 on: Jun 6^{th}, 2003, 1:37pm » 
Quote 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 10^{th}, 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:
Posts: 459


Re: Another Bag of Coloured Balls
« Reply #3 on: Jun 6^{th}, 2003, 7:02pm » 
Quote Modify

on Jun 6^{th}, 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 thoughjust bruteforced it. You must add 21 balls to increase the odds to 50%. 
 Your bruteforcing 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 6^{th}, 2003, 7:36pm by Leo Broukhis » 
IP Logged 



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Another Bag of Coloured Balls
« Reply #4 on: Jun 9^{th}, 2003, 8:58am » 
Quote 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 5k^{2}+7k+4=0. [e]Thanks for pointing out the typo, T&B[/e]

« Last Edit: Jun 9^{th}, 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:
Posts: 4489


Re: Another Bag of Coloured Balls
« Reply #5 on: Jun 9^{th}, 2003, 3:28pm » 
Quote 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(a1) + b(b1) =  = 1/3 (a+b)(a+b1) This gives a^{2} + b^{2} = ab + a + b If we now add k balls of a different colour, we get a(a1) + b(b1) + k(k1)  = 1/2 (a+b+k)(a+b+k1) Substituting a = b = 2, we get k^{2}  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+k1) + b(b1)  = 1/2 (a+b+k)(a+b+k1) Substituting a = b = 2, we get k^{2}  k  4 = 0, which also has no integer solutions. 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 6^{th}, 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
Gender:
Posts: 1825


Re: Another Bag of Coloured Balls
« Reply #6 on: Jun 9^{th}, 2003, 3:52pm » 
Quote 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. 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 na the number of the other colour. P(same colour)=a(a–1)/n(n–1)+(n–a)(n–a1)/n(n–1)=1/3. This simplifies to n^{2}–(3a+1)n+3a^{2}=0. Adding k balls of another colour, P(same colour)=a(a–1)/(n+k)(n+k–1)+(n–a)(n–a1)/(n+k)(n+k–1)+k(k–1)/(n+k)(n+k–1 )=1/2. Simplifying to n^{2}–(4a+2k+1)n+k^{2}–k+4a^{2}=0. My mistake before was here, I had the coefficient of n equal to 4a–2k–1 Therefore, n^{2}–(4a+2k+1)n+k^{2}–k+4a^{2}=n^{2}–(3a+1)n+3a^{ 2}. Equating the coefficients, 4a+2k+1=3a+1, giving a=2k. k^{2}–k+4a^{2}=3a^{2}, giving k^{2}–k+a^{2}=0. Therefore, k^{2}–k+4k^{2}=0, k(5k–1)=0. That is, k=0 or k=1/5.

« Last Edit: Jun 9^{th}, 2003, 4:03pm by Sir Col » 
IP Logged 
mathschallenge.net / projecteuler.net



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Another Bag of Coloured Balls
« Reply #7 on: Jun 9^{th}, 2003, 4:36pm » 
Quote 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+k–1)/(n+k)(n+k–1)+(n–a)(n–a1)/(n+k)(n+k–1)=1/2. And this simplifies to n^{2}–(2k+4a+1)n+k^{2}–k+4a^{2}+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...

« Last Edit: Jun 9^{th}, 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:
Posts: 4489


Re: Another Bag of Coloured Balls
« Reply #8 on: Jun 9^{th}, 2003, 4:56pm » 
Quote Modify

Which of Leonid's results are you referring to? He produced numbers for the 3colour version, but we are doing the 2colour version. The 3colour 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 6^{th}, 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
Gender:
Posts: 1825


Re: Another Bag of Coloured Balls
« Reply #9 on: Jun 9^{th}, 2003, 5:13pm » 
Quote Modify

on Jun 9^{th}, 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 rereading 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:
Posts: 4489


Re: Another Bag of Coloured Balls
« Reply #10 on: Jun 14^{th}, 2003, 9:33pm » 
Quote 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(a1) + b(b1) =  = 1/2 (a+b)(a+b1) This gives (ab)^{2} = a+b Let a = u(u+1)/2 b = u(u1)/2 u = 2,3,4,5... Now, adding k balls of a different colour, probability of choosing two balls of the same colour a(a1) + b(b1) + k(k1) =  = 1/3 (a+b+k)(a+b+k1) 3[a(a1) + b(b1) + k(k1)] = (a+b+k)(a+b+k1) Solving for k gives 2k = (a+b+1) +/ [3(a+b)+1)]^{1/2} = (u^{2}+1) +/ [3u^{2}+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 3u^{2}+1 is a perfect square. And there are infinitely many solutions to 3u^{2}+1 = x^{2} 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(a1) + b(b1) + c(c1)  = 1/3 (a+b+c)(a+b+c1) a(a1) + b(b1) + c'(c'1)  = 1/2 (where c' > c) (a+b+c')(a+b+c'1) to be continued...

« Last Edit: Jun 16^{th}, 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:
Posts: 1948


Re: Another Bag of Coloured Balls
« Reply #11 on: Jan 4^{th}, 2009, 1:27am » 
Quote Modify

on Jun 14^{th}, 2003, 9:33pm, THUDandBLUNDER wrote: What is the relationship between this problem and the original problem? 
 Look at the brute forced solutions: 6,10, 105, 120,.... Let a = n(n1)/2, b = n(n+1)/2. If c' = 1+2n^{2}, the second probability is 1/2. For the first probability to be 1/3, we need 1+3n^{2} 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 4^{th}, 2009, 1:29am by Eigenray » 
IP Logged 



osheen
Newbie
Posts: 2


Re: Another Bag of Coloured Balls
« Reply #12 on: Jan 6^{th}, 2009, 5:05am » 
Quote 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:
Posts: 4489


Re: Another Bag of Coloured Balls
« Reply #13 on: Jan 12^{th}, 2009, 5:19pm » 
Quote 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.



