Author |
Topic: Another Bag of Coloured Balls (Read 10423 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Another Bag of Coloured Balls
« on: Jun 6th, 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 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
Gender:
Posts: 949
|
|
Re: Another Bag of Coloured Balls
« Reply #1 on: Jun 6th, 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 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:
Posts: 4489
|
|
Re: Another Bag of Coloured Balls
« Reply #2 on: Jun 6th, 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 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:
Posts: 459
|
|
Re: Another Bag of Coloured Balls
« Reply #3 on: Jun 6th, 2003, 7:02pm » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Another Bag of Coloured Balls
« Reply #4 on: Jun 9th, 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 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:
Posts: 4489
|
|
Re: Another Bag of Coloured Balls
« Reply #5 on: Jun 9th, 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(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. 
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
Gender:
Posts: 1825
|
|
Re: Another Bag of Coloured Balls
« Reply #6 on: Jun 9th, 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 n-a the number of the other colour.
P(same colour)=a(a–1)/n(n–1)+(n–a)(n–a-1)/n(n–1)=1/3.
This simplifies to n2–(3a+1)n+3a2=0.
Adding k balls of another colour,
P(same colour)=a(a–1)/(n+k)(n+k–1)+(n–a)(n–a-1)/(n+k)(n+k–1)+k(k–1)/(n+k)(n+k–1 )=1/2.
Simplifying to n2–(4a+2k+1)n+k2–k+4a2=0.
My mistake before was here, I had the coefficient of n equal to 4a–2k–1 
Therefore, n2–(4a+2k+1)n+k2–k+4a2=n2–(3a+1)n+3a 2.
Equating the coefficients,
4a+2k+1=3a+1, giving a=-2k.
k2–k+4a2=3a2, giving k2–k+a2=0.
Therefore, k2–k+4k2=0, k(5k–1)=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
Gender:
Posts: 1825
|
|
Re: Another Bag of Coloured Balls
« Reply #7 on: Jun 9th, 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–a-1)/(n+k)(n+k–1)=1/2.
And this simplifies to n2–(2k+4a+1)n+k2–k+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...
|
| « 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:
Posts: 4489
|
|
Re: Another Bag of Coloured Balls
« Reply #8 on: Jun 9th, 2003, 4:56pm » |
Quote 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
Gender:
Posts: 1825
|
|
Re: Another Bag of Coloured Balls
« Reply #9 on: Jun 9th, 2003, 5:13pm » |
Quote 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:
Posts: 4489
|
|
Re: Another Bag of Coloured Balls
« Reply #10 on: Jun 14th, 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(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...
|
| « 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:
Posts: 1948
|
|
Re: Another Bag of Coloured Balls
« Reply #11 on: Jan 4th, 2009, 1:27am » |
Quote Modify
|
on Jun 14th, 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(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 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 12th, 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.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print