Author |
Topic: Infinite Balls Urn (Read 3471 times) |
|
kiochi
Newbie
Posts: 42
|
 |
Infinite Balls Urn
« on: Jan 4th, 2007, 1:15pm » |
 Quote  Modify
|
A friend told me this one. Maybe it's too easy or uninteresting to be a good riddle, but here goes anyway.
So suppose Mindy has an infinite number of (numbered) balls and an urn that can fit as many balls as necessary. We also assume that Mindy has the ability to do things "really fast."
At 1 minute until midnight, Mindy puts balls 1-10 into the urn, then immediately takes out ball 1 (i.e. at 1 minute till midnight, balls 2-10 are in the urn).
Next, at 1/2 minute till midnight, Mindy puts balls 11-20 into the urn and takes out ball 11. At 1/3 minute till midnight, Mindy puts in balls 21-30 and takes out ball 21.
The process continues, with the nth iteration occuring at 1/n minutes till midnight. How many balls are in the urn at midnight?
The next day, Mindy decides to mix it up. She starts out again with an empty urn and a bunch of balls. At 1 minute till midnight, Mindy puts in balls 1-10, and takes out ball 1. At 1/2 minute till midnight she puts in balls 11-20 and takes out ball 2. At 1/3 minute till midnight she puts in balls 21-30 and takes out ball 3, and so on.
How many balls left at midnight?
Hint: Mindy got a different answer this second time.
Mindy, confused by the new answer wanted to try a third experiment.
She bought completely new balls with no numbers or identifying characteristics. At 1 minute till midnight she puts in ten of these balls and takes out 1 of them at random. At 1/2 minute till midnight, she puts in 10 more balls and takes out another one at random, and so on. How many did she end up with this last time, or can you say? Will she get the same number each time?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Infinite Balls Urn
« Reply #1 on: Jan 4th, 2007, 1:52pm » |
Quote Modify
|
A great riddle to teach someone the perils of infinity..
(Although unfortunately, in other places, many people never seem to get it, and just cop out saying it isn't physically possible.)
|
| « Last Edit: Jan 4th, 2007, 1:52pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: Infinite Balls Urn
« Reply #3 on: Jan 4th, 2007, 3:18pm » |
Quote Modify
|
I don't understand the difference between the three scenarios. 
Each time she effectively puts in nine balls. Why wouldn't the number of balls in the bin always be 9n ?
**Edit -- For each of your questions, how many balls would you say she removed from the urn?
|
| « Last Edit: Jan 4th, 2007, 3:26pm by honkyboy » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite Balls Urn
« Reply #4 on: Jan 4th, 2007, 3:29pm » |
Quote Modify
|
on Jan 4th, 2007, 3:18pm, honkyboy wrote:| I don't understand the difference between the three scenarios. |
|
A hint Identify which (numbered) balls are left in the bucket.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: Infinite Balls Urn
« Reply #5 on: Jan 4th, 2007, 4:08pm » |
Quote Modify
|
Ok. Here's how I'm looking at it.
1st scenario:Removed from the urn are all number which end in 1. Therefore remaining in the urn are all numbers except for those that end in 1.
2nd scenario: Removed from the urn are the bottom tenth of all numbers, or all numbers < infinity/10. Remaining in the urn is all numbers > infinity/10.
3rd scenario: Well she adds an infinite number of balls and randomly take away %10 of them.
It seems to me that she will always have an infinite number of balls inside and out of the urn when she is done. What am I missing here?
One thing for sure is that Mindy has got alot of balls!
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Infinite Balls Urn
« Reply #6 on: Jan 4th, 2007, 4:29pm » |
Quote Modify
|
But infinity/10 = infinity
Infinite numbers do not obey the same algebraic laws as finite numbers.
|
| « Last Edit: Jan 4th, 2007, 4:30pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: Infinite Balls Urn
« Reply #7 on: Jan 4th, 2007, 5:06pm » |
Quote Modify
|
on Jan 4th, 2007, 4:29pm, THUDandBLUNDER wrote:But infinity/10 = infinity
Infinite numbers do not obey the same algebraic laws as finite numbers. |
|
I see. I wrote down what number infinity/10 is on a bar napkin, I just can't find it right now. 
A graph the number of balls in the urn as a function fo time is a steep curve along the asymptote of t=midnight. With no numbers on the balls this curve intersects the asymptote at n=infinity.
Where does Mindy's progress deviate from this curve using numbered balls?
|
| « Last Edit: Jan 4th, 2007, 5:07pm by honkyboy » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Infinite Balls Urn
« Reply #8 on: Jan 4th, 2007, 5:27pm » |
Quote Modify
|
on Jan 4th, 2007, 5:06pm, honkyboy wrote:| Where does Mindy's progress deviate from this curve using numbered balls? |
|
At infinity. 
There is a discontinuity.
LIMITf(x) = b does NOT imply f(a) = b
x -> a
|
| « Last Edit: Jan 4th, 2007, 7:27pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: Infinite Balls Urn
« Reply #9 on: Jan 4th, 2007, 5:42pm » |
Quote Modify
|
Thank you.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Infinite Balls Urn
« Reply #10 on: Jan 4th, 2007, 5:56pm » |
Quote Modify
|
You are welcome.
There is also a long discussion here.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite Balls Urn
« Reply #11 on: Jan 5th, 2007, 12:33am » |
Quote Modify
|
In scenario two, it's important to see that a ball with number n is removed 1/n minutes before midnight. And since all balls are numbered, there can't be any left.
Any identifiable ball is removed, and all balls were identifiable. (In contrast to the first scenario were you can identify an infinite number of balls that must still be in the bucket; and the third scenario were balls aren't identifiable at all.).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Infinite Balls Urn
« Reply #12 on: Jan 5th, 2007, 6:52am » |
Quote Modify
|
In every case, the number of balls is
infinity - infinity = undefined.
|
|
IP Logged |
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: Infinite Balls Urn
« Reply #13 on: Jan 5th, 2007, 11:09am » |
Quote Modify
|
on Jan 5th, 2007, 6:52am, Grimbal wrote:In every case, the number of balls is
infinity - infinity = undefined.
|
|
I think that it's only "undefined" in the third case. As towr has pointed out, in the first two scenarios we can identify exactly which balls remain and which are removed.
In the third case I guess it's reasonable to say that it's "undefined," but, following the reasoning from the first two, I think it makes sense to say that there could be any number of balls from 0 to infinity left in the urn.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite Balls Urn
« Reply #14 on: Jan 5th, 2007, 6:50pm » |
Quote Modify
|
on Jan 5th, 2007, 6:52am, Grimbal wrote:In every case, the number of balls is
infinity - infinity = undefined.
|
|
 - is not undefined because you can't ever get a value. It is undefined because the value that you get differs from situation to situation. You have to determine the result by a logical examination of the situation, rather than relying on a simple subtraction to get your answer.
The logical examinations reveal that in the first case, the number of balls remaining is . In the second case, it is 0. And in the third case, it really is indeterminate from the information given.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Infinite Balls Urn
« Reply #15 on: Jan 6th, 2007, 8:55am » |
Quote Modify
|
Now that you say it, I think "undeterminate" is better than "undefined".
What I mean is that from the fact that you add an infinity of balls and you remove an infinity, you cannot tell anything. That is why I say "infinity - infinity = undeterminate". And that is what the 3 cases have in common. But by numbering the balls, you can sometimes determine which ball (and therefore how many) remain in the urn.
This explains the paradox that by doing essentially the same thing, you get different results.
You also can do something worse.
You add balls #0-9, 10-19, 20-29, etc. and remove balls #0, 1, 2, etc. Move 1 is "add #0-9, remove #0". Move 2 is "add #10-19, remove #2", etc. Let's call that the base sequence of moves.
Then you interleave multiple copies of this sequence. Every 100 moves, at move n·100. you add in move n from the base sequence. After every 10000 moves, at move n·10000 you add in move n·100 but also move n. And in general, every move n·100k, you add in move n·10i for i=k-1,...,0.
That means that every ball gets added and removed an infinite number of times. In that case, even if all moves a precisely identified, it is impossible to tell whether a particular ball is in the urn after an infinite number of moves.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite Balls Urn
« Reply #16 on: Jan 7th, 2007, 7:11am » |
Quote Modify
|
You can arrive at that problem a lot easier:
At odd n add ball 1, at even n remove ball 1.
How many are left after an infinite number of moves?
What I was wondering about case three, is if you did number the balls, but randomly selected one of the numbered balls for removal. Could you say anything about the probability that the bucket ends up empty or not?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Infinite Balls Urn
« Reply #17 on: Jan 7th, 2007, 2:31pm » |
Quote Modify
|
on Jan 7th, 2007, 7:11am, towr wrote:| What I was wondering about case three, is if you did number the balls, but randomly selected one of the numbered balls for removal. Could you say anything about the probability that the bucket ends up empty or not? |
|
It would be empty with probability 1. But if you were to add something like n2 or 2n balls on the n-th step, it gets more complicated.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite Balls Urn
« Reply #18 on: Jan 7th, 2007, 2:49pm » |
Quote Modify
|
I'm quite curious about the reasoning behind that.
And also, does the result transfer to case three as originally stated?
(Obviously to remove the first or last ball we have to be able to identify them; but to uniformly randomly remove a ball, we don't really need that, do we? Yet these problems are counterintuitive enough to make me doubt.)
|
| « Last Edit: Jan 7th, 2007, 2:50pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Infinite Balls Urn
« Reply #19 on: Jan 7th, 2007, 4:56pm » |
Quote Modify
|
on Jan 7th, 2007, 2:31pm, Eigenray wrote:
It would be empty with probability 1. |
|
So it's not certain then?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite Balls Urn
« Reply #20 on: Jan 7th, 2007, 8:56pm » |
Quote Modify
|
on Jan 7th, 2007, 4:56pm, THUDandBLUNDER wrote:
So it's not certain then?
|
|
Nope. After all, if you pick a real number between 0 and 1 at random with uniform probability, the probability of getting an irrational number is also 1.
|
| « Last Edit: Jan 7th, 2007, 8:58pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Infinite Balls Urn
« Reply #21 on: Jan 8th, 2007, 7:16am » |
Quote Modify
|
on Jan 7th, 2007, 8:56pm, Icarus wrote:
Nope. After all, if you pick a real number between 0 and 1 at random with uniform probability, the probability of getting an irrational number is also 1. |
|
Thanks; just as I expected.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
kiochi
Newbie
Posts: 42
|
|
Re: Infinite Balls Urn
« Reply #22 on: Jan 8th, 2007, 11:58am » |
Quote Modify
|
on Jan 7th, 2007, 2:49pm, towr wrote:I'm quite curious about the reasoning behind that.
And also, does the result transfer to case three as originally stated?
(Obviously to remove the first or last ball we have to be able to identify them; but to uniformly randomly remove a ball, we don't really need that, do we? Yet these problems are counterintuitive enough to make me doubt.) |
|
I'm also very curious about the reasoning.
My intuition is that choosing numbered balls at random is equivalent to having blank balls. E.g. number the balls with magic ink that only an observer (we) can see, while Mindy thinks she has blank balls.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Infinite Balls Urn
« Reply #23 on: Jan 8th, 2007, 5:16pm » |
Quote Modify
|
on Jan 8th, 2007, 7:16am, THUDandBLUNDER wrote:
Thanks; just as I expected.
|
|
I figured you were being facetious, but I wanted to make sure other readers who are less familiar with probability understood the difference between probability = 1 and certainty.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Infinite Balls Urn
« Reply #24 on: Jan 9th, 2007, 3:02pm » |
Quote Modify
|
on Jan 7th, 2007, 2:49pm, towr wrote:| I'm quite curious about the reasoning behind that. |
|
Consider ball b, which gets added at stage k=ceiling(b/10). What is the probabilitiy that this ball is never removed?
During stage k, there are 9k+1 balls to choose from, so the probabilitiy that ball b is not removed is 1 - 1/(9k+1). And given that ball b is still there after stage s-1, the probability that it is not removed during stage s is 1 - 1/(9s+1). So the probability that ball b is never removed is
p = [1 - 1/(9k+1)]*[1 - 1/(9k+10)]*[1 - 1/(9k+19)]*... = 0.
(It's a standard result that if {an} is a sequence of positive numbers such that [sum] an diverges, but [sum] an2 converges, then [prod](1 - an) = 0, and this applies to an = 1/[9n + 9k-8].)
Thus each ball gets removed with probability 1, and a countable intersection of probability 1 events also has probability 1. So the urn is almost surely empty.
Of course what I'm sweeping under the rug here is that this actually is a well-defined probability space. This can be seen as follows. Define probability measures pn on Nn by pn(b1,...,bn) = 1/[10*19*...*(9n+1)] if b1,...,bn are distinct and each bk < 10k; otherwise set pn(b) = 0. This is the probability that we pick ball bk during stage k, for 1<k<n.
These measures are consistent in that if E is a subset of Nn, then pn+1(E x N) = pn(E). Thus by the Kolmogorov extension theorem, there is a unique probability measure P on NN such that for any b1,...,bn in N,
P((b1,...,bn)xNN) = pn(b1,...,bn).
The domain of P is the sigma-algebra generated by subsets of NN with a given finite prefix, and these are all basic open sets for the product topology on NN. Fix a ball b, and let A be the event that b is never removed. Let As be the event that ball b is not removed during the first s stages. Then for s > k = ceiling(b/10),
P(As) = [1 - 1/(9k+1)]*...*[1 - 1/(9s+1)],
since As is the disjoint union of [10*19*...*(9(k-1)+1)]*[(9k)...(9s)] basic open sets, each of the form (b1,...,bs)xNN.
Now, A is the intersection of all the As, hence measurable, and since P(As) -> 0, we have P(A)=0, and the conclusion follows as before.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print