wu :: forums - Print Page


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

        riddles >> easy >> Winning Ball
        
(Message started by: Sir Col on Oct 17^th, 2003, 3:06pm)

Title: Winning Ball
Post by Sir Col on Oct 17^th, 2003, 3:06pm

A box contains one white ball and an unknown number of black balls. Two players take it in turns to remove a ball at random from the box. If a player picks a white ball they win the game. If a black ball is taken it is not replaced.

What can you deduce about the number of black balls in the box if there is an equal chance of either player winning?

Title: Re: Winning Ball
Post by Speaker on Oct 17^th, 2003, 6:47pm

Well, I want to say one black ball. But, maybe then the person who draws second has different odds than the person who draws first. But, then the odds would change everytime a ball is removed so the chances are never equal.

But, both players have the same odds of winning, because they are drawing from the same pool.

The chances of a white ball or a black ball being drawn are not equal, unless there is one of each.

So, you can deduce [hide]nothing. [/hide]

Title: Re: Winning Ball
Post by TimMann on Oct 17^th, 2003, 10:03pm

Speaker is mistaken.

Hint: ::[hide]Imagine that you play the game this way: the two players draw alternately, blindfolded, not replacing any balls, until all balls are taken. The players then remove their blindfolds and the one who has the white ball wins.[/hide]::

Title: Re: Winning Ball
Post by harpanet on Oct 18^th, 2003, 6:17am

Doing a bit of algebra, each term in the probability sequence (player1, player2, player1 etc) :[hide]appears to be the same (1/n+1, where n is the original number of black balls). So as long as there are an even number of balls, the odds for each player will be the same. Deduction - there must be an odd number of black balls[/hide]:

Presumably you could generalise this to encompass 3 or more players.

Title: Re: Winning Ball
Post by Lightboxes on Oct 18^th, 2003, 11:14am

::[hide]I say an infinite number of black balls[/hide]::

Title: Re: Winning Ball
Post by TimMann on Oct 18^th, 2003, 10:16pm

harpanet got it, evidently without looking at my hint. :)

Lightboxes' answer isn't meaningful unless he defines what it will mean to draw randomly from an infinite set of balls. Presumably we're to assume the set is countably infinite, as balls are discrete objects. But the probability distribution that one usually assumes when none other is given -- uniform -- doesn't exist over a countably infinite set. So you'll have to specify a distribution. I think that for any distribution in which there are an infinity of balls that have a nonzero probability of being drawn (including the white one!), the first player has an advantage.

Title: Re: Winning Ball
Post by Sir Col on Oct 19^th, 2003, 11:52am

on 10/18/03 at 22:16:38, TimMann wrote:

harpanet got it, evidently without looking at my hint. :)

I think your hint is an excellent way to prove the result.
::[hide]
Assume that every ball is taken. We know that the product of probabilities will have the following properties: (i) the denominators will decrease from n to 1, (ii) the numerators will contain, (n–1), (n–2), ..., 1 (for the black balls), and an extra 1 (for the white ball). Therefore all of the numerators will cancel with all of the denominators except, n.

For example, for 5 black balls:
P(last ball is white) = (5/6)(4/5)(3/4)(2/3)(1/2)(1/1) = (5*4*3*2*1*1)/(6*5*4*3*2*1) = 1/6
P(3rd ball is white) = (5/6)(4/5)(1/4)(3/3)(2/2)(1/1) = (5*4*3*2*1*1)/(6*5*4*3*2*1) = 1/6

Hence, P(kth ball is white) = ((n–1)/n)((n–2)/(n–1))...(2/3)(1/2)(1/1) = ((n–1)(n–2)...3*2*1*1)/(n(n–1)(n–2)...3*2*1) = 1/n

Player 1 can win on 1st, 3rd, 5th, ...
Player 2 can win on 2nd, 4th, 6th, ...

Hence if there are an even number of balls, P(player 1 wins)=P(player 2 wins).
[/hide]::

It is fairly easy now, as Harpanet suggested, to extend this to m players. However...

What if there were w white balls and b black balls?
(Same rules: white ball is a win, black balls not replaced, and we're trying to make the game fair)

Title: Re: Winning Ball
Post by harpanet on Oct 19^th, 2003, 12:50pm

OK, I'm going to stick my neck out and say: [hide]for w > 1 it is not possible for equal probabilities with the variation.

P(1) = w/(w+b)
P(2) = b/(w+b) * w/(w+b-1)

P(1) = P(2) iff w = 1, and we know that w > 1.
In fact P(2) < P(1) and I suspect (if I could be bothered to continue the algebra to the next term) that P(x) > P(x + 1).

If that last bit is correct then each odd probability (1,3,5,...) is always greater than its corresponding even probability (2,4,6,...). So player 2 can never have the same probability as player 1.[/hide]:

Title: Re: Winning Ball
Post by towr on Oct 19^th, 2003, 1:13pm

I think that as long as the number of balls is a multiple of the number of players, each player has an equal chance of getting any one ball.. And thus equal chances of getting white balls..

Title: Re: Winning Ball
Post by towr on Oct 19^th, 2003, 1:21pm

on 10/19/03 at 12:50:22, harpanet wrote:

P(1) = w/(w+b)
P(2) = b/(w+b) * w/(w+b-1)

P(2) should be something else.
b/(w+b) is one option, but w/(w+b) is also an option for player 1
So we get
P(2) = b/(w+b) * w/(w+b-1) + w/(w+b) * (w-1)/(w+b-1) = w/(b+w)

the last part is zero only if w = 1

Title: Re: Winning Ball
Post by harpanet on Oct 19^th, 2003, 1:49pm

on 10/19/03 at 13:21:41, towr wrote:

P(2) = b/(w+b) * w/(w+b-1) + w/(w+b) * (w-1)/(w+b-1) = w/(b+w)

while that gives the probability of drawing a white ball on the second selection, the added probability doesn't help the second player if the first player has drawn white, as the game is over.

Title: Re: Winning Ball
Post by towr on Oct 19^th, 2003, 1:53pm

Well, yes and no..
If you stop at the first drawn white ball then it doesn't..
But if it's a sort of lottery, and a white ball signifies say a cashprize of 100 dollars, then it does..

It's really a choice between does the first one to draw a white ball win, or everyone who draws a white ball..

Title: Re: Winning Ball
Post by Sir Col on Oct 19^th, 2003, 2:04pm

Towr has solved it, but TimMann's superb suggestion makes this problem quite easy to solve. It also leads to a simple and surprising result: [hide]P(kth ball is white)=w!/[(n(n–1)(n–2)...(n–(w–1))]; for example, with 3 white balls, P(kth ball is white)=3!/[n(n–1)(n–2)]. The number of players vs. number of balls condition follows[/hide].

Title: Re: Winning Ball
Post by Sir Col on Oct 20^th, 2003, 11:08am

Dang! It seems that we've made a serious oversight. :-[

Consider w=2, b=2. If the white ball hasn't appeared by the 2nd ball, player 1 will definitely win (the last ball will never need to be drawn).

Therefore, P(player 2 wins) = P(1st ball black, 2nd ball white) = (1/2)(2/3) = 1/3

Of course, what my (hidden) formula in the last post does, is finds the probability the the kth ball is white, even though a white may come out before and/or after; that is, it finds the probability of one of all possible outcome. What is does do though, is show that each probable outcome is equally likely.

A major rethink on strategy is required...

Title: Re: Winning Ball
Post by towr on Oct 20^th, 2003, 11:17am

I think that basicly comes down to what Harpanet allready said..

But as I said it depends on your winning condition.. I'm not opposed to both players winning when there are two white balls, nor to one player winning twice. But as it is your puzzle, it is your call.

Title: Re: Winning Ball
Post by TimMann on Oct 24^th, 2003, 12:24am

Going back to the original puzzle, the point of my hint was that in the modified game I described, where all the balls are distributed, it's painfully obvious that whichever player ends up with the most balls has the highest probability of having the white one. So the two players have equal probabilities if and only if they end up with an equal number of balls, which happens if and only if the number n of black balls is odd. It should also be obvious that the modified game has the same winner as the original game.

Generalizing to m players and one white ball, again obviously their chances are equal if and only if the total number of balls n+1 is divisible by m. Otherwise the early players, who get one more ball, have a slight advantage. Specifically, an early player has probability ceiling((n+1)/m)/(n+1) and a late player has probability floor((n+1)/m)/(n+1).

I don't see the point of doing any further computation on these problems.

However, I don't have any thoughts about a quick way to solve the generalization to w > 1 white balls. The modified game is no longer equivalent to this one!