wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Another Bag of Coloured Balls
        
(Message started by: THUDandBLUNDER on Jun 6^th, 2003, 12:25pm)

Title: Another Bag of Coloured Balls
Post by THUDandBLUNDER on Jun 6^th, 2003, 12:25pm

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?

Title: Re: Another Bag of Coloured Balls
Post by James Fingas on Jun 6^th, 2003, 1:26pm

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%.

Title: Re: Another Bag of Coloured Balls
Post by THUDandBLUNDER on Jun 6^th, 2003, 1:37pm

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.)

Title: Re: Another Bag of Coloured Balls
Post by Leonid Broukhis on Jun 6^th, 2003, 7:02pm

on 06/06/03 at 13:26:56, 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.

Title: Re: Another Bag of Coloured Balls
Post by Sir Col on Jun 9^th, 2003, 8:58am

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²+7k+4=0.

[e]Thanks for pointing out the typo, T&B[/e]

Title: Re: Another Bag of Coloured Balls
Post by THUDandBLUNDER on Jun 9^th, 2003, 3:28pm

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 a² + b² = 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

k² - 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

k² - 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!

Title: Re: Another Bag of Coloured Balls
Post by Sir Col on Jun 9^th, 2003, 3:52pm

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 n²–(3a+1)n+3a²=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 n²–(4a+2k+1)n+k²–k+4a²=0.
My mistake before was here, I had the coefficient of n equal to 4a–2k–1 :-[
Therefore, n²–(4a+2k+1)n+k²–k+4a²=n²–(3a+1)n+3a².

Equating the coefficients,
4a+2k+1=3a+1, giving a=-2k.

k²–k+4a²=3a², giving k²–k+a²=0.

Therefore, k²–k+4k²=0, k(5k–1)=0. That is, k=0 or k=1/5.

Title: Re: Another Bag of Coloured Balls
Post by Sir Col on Jun 9^th, 2003, 4:36pm

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 n²–(2k+4a+1)n+k²–k+4a²+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... ;)

Title: Re: Another Bag of Coloured Balls
Post by THUDandBLUNDER on Jun 9^th, 2003, 4:56pm

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.

Title: Re: Another Bag of Coloured Balls
Post by Sir Col on Jun 9^th, 2003, 5:13pm

on 06/09/03 at 16:56:02, 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!

Title: Re: Another Bag of Coloured Balls
Post by THUDandBLUNDER on Jun 14^th, 2003, 9:33pm

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)² = 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
= (u²+1) +/- [3u²+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²+1 is a perfect square.

And there are infinitely many solutions to 3u²+1 = x²

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...

;)

Title: Re: Another Bag of Coloured Balls
Post by Eigenray on Jan 4^th, 2009, 1:27am

on 06/14/03 at 21:33:16, THUDandBLUNDER wrote:

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

:D
Look at the brute forced solutions: 6,10, 105, 120,....

Let a = n(n-1)/2, b = n(n+1)/2. If c' = 1+2n², the second probability is 1/2. For the first probability to be 1/3, we need 1+3n² 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}
...

Title: Re: Another Bag of Coloured Balls
Post by osheen on Jan 6^th, 2009, 5:05am

intially there are 6 ball later 2 more balls of same colour are added to make the probability 1/2

Title: Re: Another Bag of Coloured Balls
Post by ThudanBlunder on Jan 12^th, 2009, 5:19pm

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 (http://www.qbyte.org/puzzles/p064s.html).