Author |
Topic: Winning Ball (Read 553 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Winning Ball
« on: Oct 17th, 2003, 3:06pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: Winning Ball
« Reply #1 on: Oct 17th, 2003, 6:47pm » |
Quote Modify
|
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 nothing.
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Winning Ball
« Reply #2 on: Oct 17th, 2003, 10:03pm » |
Quote Modify
|
Speaker is mistaken.
Hint: ::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.::
|
| « Last Edit: Oct 17th, 2003, 10:05pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: Winning Ball
« Reply #3 on: Oct 18th, 2003, 6:17am » |
Quote Modify
|
Doing a bit of algebra, each term in the probability sequence (player1, player2, player1 etc) :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:
Presumably you could generalise this to encompass 3 or more players.
|
|
IP Logged |
|
|
|
Lightboxes
Full Member
Gender:
Posts: 203
|
|
Re: Winning Ball
« Reply #4 on: Oct 18th, 2003, 11:14am » |
Quote Modify
|
::I say an infinite number of black balls::
|
|
IP Logged |
A job is not worth doing unless it's worth doing well.
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Winning Ball
« Reply #5 on: Oct 18th, 2003, 10:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Winning Ball
« Reply #6 on: Oct 19th, 2003, 11:52am » |
Quote Modify
|
on Oct 18th, 2003, 10:16pm, TimMann wrote:| harpanet got it, evidently without looking at my hint. |
|
I think your hint is an excellent way to prove the result.
::
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).
::
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)
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: Winning Ball
« Reply #7 on: Oct 19th, 2003, 12:50pm » |
Quote Modify
|
OK, I'm going to stick my neck out and say: 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.:
|
| « Last Edit: Oct 19th, 2003, 12:51pm by harpanet » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Ball
« Reply #8 on: Oct 19th, 2003, 1:13pm » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Ball
« Reply #9 on: Oct 19th, 2003, 1:21pm » |
Quote Modify
|
on Oct 19th, 2003, 12:50pm, 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
|
| « Last Edit: Oct 19th, 2003, 1:22pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: Winning Ball
« Reply #10 on: Oct 19th, 2003, 1:49pm » |
Quote Modify
|
on Oct 19th, 2003, 1:21pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Ball
« Reply #11 on: Oct 19th, 2003, 1:53pm » |
Quote Modify
|
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..
|
| « Last Edit: Oct 19th, 2003, 1:53pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Winning Ball
« Reply #12 on: Oct 19th, 2003, 2:04pm » |
Quote Modify
|
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: 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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Winning Ball
« Reply #13 on: Oct 20th, 2003, 11:08am » |
Quote Modify
|
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...
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Ball
« Reply #14 on: Oct 20th, 2003, 11:17am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Winning Ball
« Reply #15 on: Oct 24th, 2003, 12:24am » |
Quote Modify
|
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!
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print