## Infinite Balls and Jugs [solution]

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

### Re: Infinite Balls and Jugs [solution]

Alright, let's back up a minute.

I understand the argument that the urn is empty at midnight, because every number that is added is removed in a later step.

But how does this school of thought reconcile the argument that the urn begins with zero balls, and in every step of the process, more balls are added than removed?

To the empty-urn people, if I were to play devil's advocate I would ask: In what step are more balls removed than added? If there is no such step, how does the urn go from having 9 balls after step 1 to having zero balls at the end?
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

If we interpret the initial wording as to only permit balls with finite numbers, then it's empty because we ran out. If we have 50 balls, it's empty after we've removed 50 balls because we have no more to add.

The paradox then lies in ambiguity of the question.

I now feel I satisfactorily understand the conditions for emptiness. It is empty at step X if we have no balls labeled X or larger. Any room for debate thus flows from ambiguity in the phrasing of the initial question about the number of steps taken, and about whether natural or ordinal numbers are applicable, there are sets of both which satisfy the description of "starting 1,2,.." and "infinitely large".

Note that this does not explicitly require that it not be empty other certain other circumstances, I have not yet proven that. It is simply an intuitive reason to show it's emptiness in at least some cases.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:Oh well. I wasn't putting it forth as an argument that it was full, just that there still appeared to be high level debate. If not, that's fine.

In the mean time, I think I isolated the root of why I believe it is not empty.

Say we have the simplest case, a counter that switches on and displays 0 with the first tick, and increases to the next smallest number at every subsequent tick that has gone past in the singularity event.

By which you mean, I assume, the counter counts the number of steps? You could just say that, instead of using phrases like "singularity event" which don't mean anything.
To interpret which tick we are past, we construct a set from every number that has appeared on the counter after it has ticked.

When we have {0} we know 1 interval has gone by.
When we have {0,1} we know 2 intervals have gone by.

This seems needlessly complicated, but OK. Basically what you're doing is interpreting the number n as the set {0, 1, 2, ... , n-1}.
In general, when we have [0,X) we know X intervals have gone by.

Sloppy notation - best to write {0, 1, ... , X-1}. Intervals with open and closed brackets are more usually associated with sets of real numbers, not naturals.
So is it, or is it not, correct to say [0,ω) after midnight? All of the finite numbers have gone by, so we cannot say [0,n) for any natural n. Is everything I know based on a lie and there is something between these two concepts?

Well, yes, it's kind of correct, but it doesn't mean as much as you think it means. The set N, the natural numbers, is indeed the set of ordinals which are strictly less than ω, and this is indeed the set of steps that have passed once we've reaced midnight. HOWEVER, that doesn't mean we're on step ω. There's no such thing as step ω. You've extended the problem into the ordinals, but there's no justification for doing so in the problem. Just because we have a valid, defined step for each finite ordinal (that is, each natural number), doesn't mean we suddenly get a step for any infinite ordinals. You can't just extrapolate like that.
If I am not a complete idiot, then why can there is a ball labeled n at each interval [0,n), and not a ball labeled ω at [0,ω)? Is there something in the problems wording I am missing that precludes its existence?

There's at least three misconceptions here that I can see. First, as I've said, there is no step corresponding to [0,ω). If you like, [0,ω) represents the state AFTER all the steps. It's not a step itself. Second, just because something is true for each finite ordinal, that doesn't make it true for every ordinal. As a trivial example, every finite ordinal is finite, but not every ordinal is finite. Even leaving aside the non-definedness of an "ωth step", we wouldn't be able to say anything about it based solely on facts about individual previous steps - we need to consider every set together. So just because there's a ball labeled 'n' at the nth step, doesn't mean there's suddenly a ball labelled ω at the "ωth step" (whatever that is). And third, no, there is nothing precluding the existence of a ball labelled ω. There is also nothing that says that after midnight, the jug isn't full of flying chimpanzees. We have to assume that the universe of the problem contains only those things explicitly brought into existence by the statement of the problem. If we don't, there's no way of saying anything meaningful about it.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:If we interpret the initial wording as to only permit balls with finite numbers, then it's empty because we ran out. If we have 50 balls, it's empty after we've removed 50 balls because we have no more to add..

After which finite number do we run out?

@Puck - short answer, I deny that the number of balls in the urn is a continuous function of time. The reason being that in order to count things, I need a bijection between them and some set of objects representing a natural number, and I can't do this in a reasonable way because no ball is ever "settled", so while I can happily add the numbers discretely, when I try to do it continuously I fall on my face.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

By which you mean, I assume, the counter counts the number of steps? You could just say that, instead of using phrases like "singularity event" which don't mean anything.
I mean to say that after K steps, it has displayed every number less than K.
Sloppy notation - best to write {0, 1, ... , X-1}. Intervals with open and closed brackets are more usually associated with sets of real numbers, not naturals.
Then some would claim I am violating the ordinal operations as ω-1 does not exist outside more exotic systems. We can however say [0,ω) without such contradictions.
There's at least three misconceptions here that I can see. First, as I've said, there is no step corresponding to [0,ω). If you like, [0,ω) represents the state AFTER all the steps. It's not a step itself. Second, just because something is true for each finite ordinal, that doesn't make it true for every ordinal. As a trivial example, every finite ordinal is finite, but not every ordinal is finite. Even leaving aside the non-definedness of an "ωth step", we wouldn't be able to say anything about it based solely on facts about individual previous steps - we need to consider every set together. And third, no, there is nothing precluding the existence of a ball labelled ω. There is also nothing that says that after midnight, the jug isn't full of flying chimpanzees. We have to assume that the universe of the problem contains only those things explicitly brought into existence by the statement of the problem. If we don't, there's no way of saying anything meaningful about it.
But we have an "[0,ω)th state". If we have a label denoting the state, would it not have ω on it?

In another vein, if there was an ωth step and there was an ωth ball in with the finite numbers, do you say the ω-ball ever enters the vase?

After which finite number do we run out?
If we permit ordinal states, states ω and up deny all finite numbers. Without ordinal labels, there was nothing to put in. No finite step is required to have an empty vase.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:Now, if we were to explicitly declare that only balls with natural numbers are included under any circumstances, then it is of course empty, as we cannot add balls with ordinals even if it were appropriate. If we had, without question, ω+3 steps, but were only allowed to add each natural number once, then we are defining it to be empty regardless of it's circumstances at anything but finite steps. We can run out of balls, but still want to add some given the other rules of the process. If we only had balls labeled up to 50, it would also be empty at steps 51 plus, despite the rules telling us we should have put enough in such that it would not be empty at step 51.
Unlike everyone else (it seems), I quite like this interpretation. However, I believe that you're being inconsistent with it. We run out of finite numbered balls, so we want ω-numbered balls. If we don't have any then the problem is trivial, so we'll pretend we do. We start adding balls {ω, ω+1...}, however (here's where I think you've gone wrong) we also start taking out ω-numbered balls. You can't extend the rules for adding balls without also extending the rules for taking out balls. And if you do take out the ω-numbered balls then we're back where we started: every ball is put in and taken out at some point.
Indigo is a lie.
Which idiot decided that websites can't go within 4cm of the edge of the screen?
There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:
After which finite number do we run out?
If we permit ordinal states, states ω and up deny all finite numbers. Without ordinal labels, there was nothing to put in. No finite step is required to have an empty vase.

No, I'm asking in response to your earlier statement, which I quoted before:

WarDaft wrote:If we interpret the initial wording as to only permit balls with finite numbers, then it's empty because we ran out. If we have 50 balls, it's empty after we've removed 50 balls because we have no more to add..

If I only allow balls with finite numbers, at what point are there no more numbers to add?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

At state ω. I don't see how we can describe the state after midnight with anything less than ω; even if we deny ordinal steps we have to admit ordinal (or at least infinite) states to remove all the finite numbers, under any interpretation. If there are finite states, it's not empty.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Infinite Balls and Jugs [solution]

Why describe it as anything at all? It's not a step, and we don't DO anything to the jar after midnight. It's just confusing the issue.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

Macbi wrote:
WarDaft wrote:Now, if we were to explicitly declare that only balls with natural numbers are included under any circumstances, then it is of course empty, as we cannot add balls with ordinals even if it were appropriate. If we had, without question, ω+3 steps, but were only allowed to add each natural number once, then we are defining it to be empty regardless of it's circumstances at anything but finite steps. We can run out of balls, but still want to add some given the other rules of the process. If we only had balls labeled up to 50, it would also be empty at steps 51 plus, despite the rules telling us we should have put enough in such that it would not be empty at step 51.
Unlike everyone else (it seems), I quite like this interpretation. However, I believe that you're being inconsistent with it. We run out of finite numbered balls, so we want ω-numbered balls. If we don't have any then the problem is trivial, so we'll pretend we do. We start adding balls {ω, ω+1...}, however (here's where I think you've gone wrong) we also start taking out ω-numbered balls. You can't extend the rules for adding balls without also extending the rules for taking out balls. And if you do take out the ω-numbered balls then we're back where we started: every ball is put in and taken out at some point.
That is where it depends on our situation. We're taking out ordinal labeled balls, but we may have put in more >ω labeled balls than we have removed, but we may also not have. If states divisible by 2 follow steps which added balls, states divisible by 3 follow states that removed the least ball, it is empty at ω, and ω+1, and ω+2, and ω+3, because none of these are multiples of two, and we removed every finite labeled ball at some finite state. At state ω2 we add a ball, which we remove at ω3.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

Token wrote:Why describe it as anything at all? It's not a step, and we don't DO anything to the jar after midnight. It's just confusing the issue.
You just described it as after midnight, I just described it as state ω, unless "state ω" implies something incorrect, or does not imply something correct, it is no less valid than describing it as "after midnight".

I phrased it explicitly that way such that if my interpretation is wrong, you can tell me exactly what saying state ω implies that is wrong, or does not imply that is right. If I am wrong in this interpretation, I want to know exactly where the boundary between my interpretation and the correct one is.
Last edited by WarDaft on Tue Nov 10, 2009 9:25 pm UTC, edited 1 time in total.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

At 1 minute to midnight, I add ball 1. At 1/2 minute to midnight, I add ball 2. And so on. I never take any balls out, I just always add the next one.

Now I hope we can all agree there are infinitely many balls in the urn at midnight, right?

Is there a ball labeled infinity/omega?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

That is, essentially, what I was asking.

But we can simplify it more actually.

If at time 1 we add ball 1, and at time 2 we add ball 2, and at time 3 we add ball 3, and so on...

What time is the phrase 'at/after' midnight equivalent to?

As I understand it, the time is countably infinite, which means we can describe it with ω or aleph null. If we describe it with aleph null we cannot of course, describe an additional equivalent time after a step arbitrarily 37 seconds after midnight and the equivalent time between 0 and 37 seconds after midnight simultaneously.

If at time 1 we add ball 0, and at time 2 we add ball 1, ω is not in the jar at time ω, as every ball in the jar at time T is less than T. If at time 1 we add ball 1, at time 2 we add ball 2, then what I know says we describe time ω as containing ω in the jar. Furthermore, if each ball is added exactly once, is not in the jar before it's appropriate time, and we have ball labels starting from 0, then in the former the jar is necessarily empty at time 0 and in the latter it is not necessarily empty at time 0.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Muffins3141
Posts: 2
Joined: Tue Nov 10, 2009 10:30 pm UTC

### Re: Infinite Balls and Jugs [solution]

On the original problem, I think it is similar to the http://en.wikipedia.org/wiki/Cauchy_principal_value. The idea is that an integral from negative infinity to positive infinity is only finite if the end-behavior of both sides is zero, or rather if the limit as x approaches infinity=the limit as x approaches negative infinity=0. In this case what matters is the size of the infinities involved. At time t there have been 10t balls added and 1t balls removed. The as t goes to infinity the one is larger than the other. The number of balls in the box can thus be described as $\int_{-a}^{a} -t \forall t<0, 9t \forall t>0$ as a goes to infinity. As the end-behavior does not resolve to zero in both limits the number of balls must resolve to a non-finite value, leaving either infinity or negative infinity. As the rate of ball adding is positive (on the whole), the number of balls is thus infinity. It does not matter that every ball that is added must be removed; this argument only works with finite numbers. An infinite number of time steps and a finite number of balls and a finite ball-removal probability guarantees zero in the end, but the number of balls waiting to be added is always infinite, so the answer cannot resolve to zero.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

Muffins3141 wrote:On the original problem, I think it is similar to the http://en.wikipedia.org/wiki/Cauchy_principal_value. The idea is that an integral from negative infinity to positive infinity is only finite if the end-behavior of both sides is zero, or rather if the limit as x approaches infinity=the limit as x approaches negative infinity=0. In this case what matters is the size of the infinities involved. At time t there have been 10t balls added and 1t balls removed. The as t goes to infinity the one is larger than the other. The number of balls in the box can thus be described as $\int_{-a}^{a} -t \forall t<0, 9t \forall t>0$ as a goes to infinity. As the end-behavior does not resolve to zero in both limits the number of balls must resolve to a non-finite value, leaving either infinity or negative infinity. As the rate of ball adding is positive (on the whole), the number of balls is thus infinity. It does not matter that every ball that is added must be removed; this argument only works with finite numbers. An infinite number of time steps and a finite number of balls and a finite ball-removal probability guarantees zero in the end, but the number of balls waiting to be added is always infinite, so the answer cannot resolve to zero.

Firstly, you're getting things mixed up, the Cauchy principal value (shouldn't it be principle?) has to do with when you start with an integral from -infinity to +infinity, you can't necessarily let the bounds grow at the same speed. Secondly, your integral should be over -1, +10, not -t, 9t, but none of this really matters.

Nobody here will deny (at least I hope), that (10-1) + (10-1) + (10-1) +... is infinite. The problem is, this does not describe our situation, because when we take a ball out, we're not taking out one of the balls we just put in, so the -1 doesn't belong to the 10 in the same step.. it belongs to the 10 which represents the set of balls being put in that are now being removed, so in fact, we have:

Step 1:
10 - 1
Step 2:
10 - 1 - 1 + 10
Step 3:
10 - 1 - 1 - 1 + 10 + 10
And as time goes on, we get:
10 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 +10 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 ....+10+10...+10.

After infinitely many steps, those trailing 10s don't exist anymore (kind of like looking at the difference between the partial sums of .99999... and 1), so, any partial sum adds up to a number between 0 and 10. This alone leaves the sum undefined, but it's certainly not infinite. If you want to say that the state of the jug is undefined, I guess I'm fine with that, but really that just means our approach didn't yield an answer. But in this situation, we can evaluate what's in the jug point-wise (or rather, ball-wise), each ball n goes in at time ceiling(n/10), and comes out at time n, so it's not in the jug.

@WarDraft, this is where your argument gets really absurd. You just said the state of the jug is different at the end if you started at time 1 or time 0. (namely, one had omega, one didn't). In both cases, after infinitely many steps, the jug has all natural numbered balls. The reason we used times 1/2^n before midnight was because changing it to times 1, 2,3.., midnight has no analogue. We'd have to take a limit as n goes to infinity in the very statement of the question, there is no omega time.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

### Re: Infinite Balls and Jugs [solution]

So basically what you are arguing is that what numbers are written on the balls you remove affects how many of them are in the jar at midnight - the jar is empty at midnight if we always remove the lowest-numbered ball, but not if we always remove a ball from the set we just put in. In both cases, we are adding and removing the same number of balls at every step, yet at the end, we have a different number of balls left over, depending on which ones we removed.

I'm not sure I understand how there are people that don't have a problem with this.
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

Puck wrote:So basically what you are arguing is that what numbers are written on the balls you remove affects how many of them are in the jar at midnight - the jar is empty at midnight if we always remove the lowest-numbered ball, but not if we always remove a ball from the set we just put in. In both cases, we are adding and removing the same number of balls at every step, yet at the end, we have a different number of balls left over, depending on which ones we removed.

I'm not sure I understand how there are people that don't have a problem with this.

Absolutely, welcome back to page 1

Let's simplify things a little bit. I'm just going to do all the adding right away. All balls 1, 2.. are in the jug to start.

At time 0, I take out ball 1. At time 1/2, I take out ball 2. In general, at time 1-1/2^n, I take out ball n+1. At each time I take out 1 ball, and the jug ends up empty at time 1.

Now, start over, but this time, at time 1-1/2^n, take out ball 10(n+1). Now at each time I take out 1 ball, but the jug has lots left at time 1.

Do you have a problem with the statement: There are as many multiples of 10 as there are integers? This is just the same thing.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

### Re: Infinite Balls and Jugs [solution]

Again, I understand the argument being made. You're not answering my real question, which is: Where, exactly, is the flaw in the opposing argument?

If there is no step in which the urn loses balls, how does the urn lose balls? (Note that after step 1, there are clearly 9 balls in the urn; after time 1 you claim there are 0.)
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

If the balls can only have finite numbers, then by necessity it must be empty when only infinitely large numbers could be in the jug. The question then becomes a case of when is it appropriate for there to be infinitely large numbers in the jug, and when it is simply empty.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

Puck wrote:Again, I understand the argument being made. You're not answering my real question, which is: Where, exactly, is the flaw in the opposing argument?

If there is no step in which the urn loses balls, how does the urn lose balls? (Note that after step 1, there are clearly 9 balls in the urn; after time 1 you claim there are 0.)

It never 'loses' balls. There are lots and lots and lots of balls in the jug up until midnight.

Let's go back to this guy:

All balls 1, 2.. are in the jug to start.

At time 0, I take out ball 1. At time 1/2, I take out ball 2. In general, at time 1-1/2^n, I take out ball n+1.

When are the number of balls in the jug finite? Whatever time you pick for that, that's the time I pick for the answer to your question.

@WarDraft: Given the orginal question, where did the infinite balls come from? There weren't any, so the jug is empty.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

We're told there are infinitely many. The question does not say that they only have finite numbers on them. When I read it, I do not get the impression that the numbers on the balls are meant to be the limiting factor on what is or is not in the jug, or it would explicitly state that they are finitely numbered, or whatever conditions that the numbers must satisfy to be on a ball.

The question then becomes a matter of exactly which balls are in the jug relative to the state for all states.

Thus, one of my earlier questions, if we permitted jug states of ω, ω+1, ω+2, and ω+3, exactly which balls would be in the jug? If at ω+3 we only have balls less than ω+3, then we can show that like at time 0, it is empty at state ω. If we can show that ball δ is only ever present before state δ, then it is again empty at 0 and empty at ω. There are many (infinitely I imagine) other variations, with many different results for state ω.

We also then ask if there is a difference between the statement after midnight and the statement state ω. After midnight implies that the jug is in a state which is following countably infinitely many finitely indexed states. Is that not exactly what state ω also implies?

Also...
At time 0, I take out ball 1. At time 1/2, I take out ball 2. In general, at time 1-1/2^n, I take out ball n+1.
This is fundamentally different from other sequences. It is fairly common knowledge at this point that which ball you remove changes the answer, so it should not be unreasonable to consider when it is removed to be important as well. Interesting that you chose this sequence... if we let ball ω be in the jug at the start, when exactly do you propose it was removed? There is no time T such that T+1 = ω.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

### Re: Infinite Balls and Jugs [solution]

So the urn has 9 balls at some point in time, and 0 balls at some later point in time, but the number of balls in the urn never decreases between those two times?

Ooookay....
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:We're told there are infinitely many. The question does not say that they only have finite numbers on them. When I read it, I do not get the impression that the numbers on the balls are meant to be the limiting factor on what is or is not in the jug, or it would explicitly state that they are finitely numbered, or whatever conditions that the numbers must satisfy to be on a ball.

The question then becomes a matter of exactly which balls are in the jug relative to the state for all states.

Thus, one of my earlier questions, if we permitted jug states of ω, ω+1, ω+2, and ω+3, exactly which balls would be in the jug? If at ω+3 we only have balls less than ω+3, then we can show that like at time 0, it is empty at state ω. If we can show that ball δ is only ever present before state δ, then it is again empty at 0 and empty at ω. There are many (infinitely I imagine) other variations, with many different results for state ω.

We also then ask if there is a difference between the statement after midnight and the statement state ω. After midnight implies that the jug is in a state which is following countably infinitely many finitely indexed states. Is that not exactly what state ω also implies?

Also...
At time 0, I take out ball 1. At time 1/2, I take out ball 2. In general, at time 1-1/2^n, I take out ball n+1.
This is fundamentally different from other sequences. It is fairly common knowledge at this point that which ball you remove changes the answer, so it should not be unreasonable to consider when it is removed to be important as well. Interesting that you chose this sequence... if we let ball ω be in the jug at the start, when exactly do you propose it was removed? There is no time T such that T+1 = ω.

Perhaps I'm taking for granted that by 1,2,... I mean the natural numbers. Here's the original posting:

Suppose I have infinitely many balls, numbered 1,2,.. and so on.

At 10 minutes to midnight, I put balls 1-10 in the jug, and remove a ball. At 5 minutes to midnight I put balls 11-20 in the jug and remove a ball. At 2.5 minutes to midnight, etc (halving the time between insertions ad infinitum, putting the next 10 balls numerically in the jug each time).

How many balls are in the jug at midnight if:

a) I always remove the lowest numbered ball
b) I always remove the highest numbered ball
c) I remove balls uniformly at random.

While you may interpret 1,2... as meaning the set of all ordinals, I assure you that that puts you very much in the minority. The ordinals are a perfectly valid thing to talk about, but if I didn't bring them up, I'm not working in them. [imath]\omega[/imath] is not a time on our usual model of time, nor is it a step in a normal sequence giving by [imath]a_n[/imath], unless specifically stated.

I said what happens at time 20/2^n minutes before midnight. I said nothing about doing anything at all at midnight, why do you assume from this omission that something should be done then?

And, what do you propose the action at midnight is, you obviously want to put in some balls with labels involving omega, what ball do you take out in that "omega" step?

Also, you seem to be attaching quite a bit of value (unwarrantedly) to the labeling of the times before midnight, so I will make the removals EXACTLY the same as in the original question: Starting with a jug containing balls 1,2... (And here, as before, I mean the natural numbers), at time 20/2^n before midnight, remove ball n. How many balls are in the jug at midnight?

Puck wrote:So the urn has 9 balls at some point in time, and 0 balls at some later point in time, but the number of balls in the urn never decreases between those two times?

Ooookay....

Perhaps I misspoke in saying it never loses balls. What I mean is in no step does the number of balls decrease. Nonetheless, after infinitely many steps, the number of balls in the jug is 0, and this is because the 'number of balls in the jug' function is not continuous at midnight. This is because when I say there are 9 balls in the jug, it means I can set up a 1-1 match between the set {*,*,*,*,*,*,*,*,*} (or some other representation of 9) and the balls in the jug, and when I perform a step, I say, ok, there are 9 more balls, so there are now 9+9 =18. But neither of those 9's is the 9 that used to be in the jug, since one of those balls is gone now. When I'm mixing and matching my counting like this, there's no reason to think that what works after a finite number of steps influences what happens after an infinite number of steps in anyway.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

Perhaps I'm taking for granted that by 1,2,... I mean the natural numbers. Here's the original posting:

While you may interpret 1,2... as meaning the set of all ordinals, I assure you that that puts you very much in the minority. The ordinals are a perfectly valid thing to talk about, but if I didn't bring them up, I'm not working in them. [imath]\omega[/imath] is not a time on our usual model of time, nor is it a step in a normal sequence giving by [imath]a_n[/imath], unless specifically stated.
By the questions wording, does not every state less than ω occur before midnight, leaving only states ω and greater to describe after it? Do we not mean after every finite state when we say after midnight? I assume the balls have ordinal numbers only if it is reasonable for there to be ordinal states, which to me seems reasonable from the previous sentences. When it is said "infinitely many balls, numbered 1,2,..." the question does not, to me, sound like one where availability of balls is meant to be the constraining factor. If we define the availability of balls to be an explicit constraining factor, it is assuredly empty after midnight.

I said what happens at time 20/2^n minutes before midnight. I said nothing about doing anything at all at midnight, why do you assume from this omission that something should be done then?
I am simply trying to describe the state of the jug after midnight numerically. If we pair up times:
1,1/2,1/4,1/8,...
1 , 2 , 3 , 4 , ...
... Then what do you consider the equivalent description for the second line as the statement "less than 0" in the first? Must not everything implied by that equivalent description also be implied by "after midnight" in our scenario? If not, then how is it the equivalent description?

Now, if there was no time after midnight, or even at midnight, then it would be impossible for an infinite labeled ball to be in the jar, unless added at a finite step. But we have stated after midnight.
And, what do you propose the action at midnight is, you obviously want to put in some balls with labels involving omega, what ball do you take out in that "omega" step?
That depends on our phrasing. If the conclusion of each step is to remove the least labeled ball in the jar, whatever it may be, we remove ball ω. Whether there is a ω+1 depends on the setup. If for any step δ there are never balls equal to or greater than δ, then it is empty (assuming we set up the question to have removed all finite balls by this point.)

Also, you seem to be attaching quite a bit of value (unwarrantedly) to the labeling of the times before midnight, so I will make the removals EXACTLY the same as in the original question: Starting with a jug containing balls 1,2... (And here, as before, I mean the natural numbers), at time 20/2^n before midnight, remove ball n. How many balls are in the jug at midnight?
By specifying the natural numbers, none, I've already said that.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:By the questions wording, does not every state less than ω occur before midnight, leaving only states ω and greater to describe after it? Do we not mean after every finite state when we say after midnight? I assume the balls have ordinal numbers only if it is reasonable for there to be ordinal states, which to me seems reasonable from the previous sentences. When it is said "infinitely many balls, numbered 1,2,..." the question does not, to me, sound like one where availability of balls is meant to be the constraining factor. If we define the availability of balls to be an explicit constraining factor, it is assuredly empty after midnight.

I find your terminology strange, but if I say, do nothing in the [imath]\omega[/imath] step, then in your [imath]\omega[/imath] state, how many balls are in the urn?

I am simply trying to describe the state of the jug after midnight numerically. If we pair up times:
1,1/2,1/4,1/8,...
1 , 2 , 3 , 4 , ...
... Then what do you consider the equivalent description for the second line as the statement "less than 0" in the first? Must not everything implied by that equivalent description also be implied by "after midnight" in our scenario? If not, then how is it the equivalent description?

I don't see any equivalent description for less than 0. Just because you've paired up a few numbers doesn't mean it's going to make sense for every number.

And, what do you propose the action at midnight is, you obviously want to put in some balls with labels involving omega, what ball do you take out in that "omega" step?
That depends on our phrasing. If the conclusion of each step is to remove the least labeled ball in the jar, whatever it may be, we remove ball ω. Whether there is a ω+1 depends on the setup. If for any step δ there are never balls equal to or greater than δ, then it is empty (assuming we set up the question to have removed all finite balls by this point.)

I don't follow this fully, but are you suggesting that if in the first step I do nothing, then treat the second step as the first, the third as the second, and so on, that I get a different result? If so, you don't understand infinity.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

phlip
Restorer of Worlds
Posts: 7554
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Infinite Balls and Jugs [solution]

Let N be the set of natural numbers, and E be the set of even natural numbers. E ⊊ N.

Let [imath]N_n = \{ i : i \in N, i \le n \} = \{ 0, 1, 2, \dots, n \}[/imath]. Similarly, [imath]E_n = \{ i : i \in E, i \le n \} = \{ 0, 2, 4, \dots, 2 \left \lfloor \frac n2 \right \rfloor \}[/imath].

Now, consider |Nn| and |En|, for some n. They are different, and their difference is a strictly non-decreasing function, [imath]\left \lfloor \frac {n+1}2 \right \rfloor[/imath]. That is, the subset of N is strictly larger than the subset of E, and this discrepancy gets bigger as the sets grow.

However, "at infinity" (to abuse the terminology), Nω = N, Eω = E, and these sets are the same size. Even though the difference between the sets was positive and growing.

In short: There exist calculations that are positive and non-decreasing at every finite point, which are still zero "at infinity". Because infinity is special. This particular example isn't very analogous the puzzle at hand, but just as a counterexample to one of the assumptions behind the "the number of balls is always growing, how can it be 0 at the end" argument.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

I find your terminology strange, but if I say, do nothing in the [imath]\omega[/imath] step, then in your [imath]\omega[/imath] state, how many balls are in the urn?
It's empty.

I don't see any equivalent description for less than 0. Just because you've paired up a few numbers doesn't mean it's going to make sense for every number.
Doesn't the jar have to be in some definable state to ask what's in it? If it is, why can we not match it to an ordinal?

I don't follow this fully, but are you suggesting that if in the first step I do nothing, then treat the second step as the first, the third as the second, and so on, that I get a different result? If so, you don't understand infinity.
Not quite. As I understand it, transfinite induction let's us prove that anything which is true for δ if we assume it is already true for all β < δ, to be true for all δ.

If our instruction is to add ball δ-1 and remove ball δ-2 for state δ, I'm not aware of a way to show any ball to be in the jar at state ω.

If our instructions are to add the least 3 balls which have never been in the jar and remove the least ball in the jar, then can we not prove at least ω+1 is in the jar at state ω?

Assume that for each state β < δ, ball β+1 has been present
As each number of the form β+1 for all β < δ has been in the jar, every 0 < γ < δ has surely already been in the jar.
But as per our instructions, the least ball in the jar is removed for each state, thus for β+1 to be present, some γ < β+1 must have been present before the removal, thus every γ < δ has surely already been in the jar by state δ.
Thus, at state δ, the least balls which could possibly be added are δ, δ+1, and δ+2, if they have not been added, they will be for state δ as per our instructions.
To be in the jar at state δ, a ball λ must not yet have been removed.
Let us assume that δ < λ and λ has been removed.
For λ to be removed, it must be the least value in some state β < δ. But we have that β+1 is present for each state λ, thus, λ < β+1 for some β.
But we assumed δ < λ, thus δ < λ < β+1, and β < δ < λ < β+1, a contradiction.
Thus for δ < λ, λ has not been removed.
Thus, for state δ, we have that if δ, δ+1, and δ+2 are not present, they are added for state δ, and if δ < λ, λ has not been removed by state delta, thus, δ+1 is present for every state δ.

That's the latter, I'm not aware of any way to guarantee any balls being present for the former. If you can find something wrong with it, do not hesitate to say so. If not, that leaves us with what might end up being an agreement to disagree that we are in state ω after midnight.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:If our instructions are to add the least 3 balls which have never been in the jar and remove the least ball in the jar, then can we not prove at least ω+1 is in the jar at state ω?

That would be true, if we had such an instruction. However, in the problem as written, balls are only added and removed at times which are 1/2n minutes before midnight, for some n, so no balls are removed and none are added exactly at midnight. There is no "state ω"; there is only midnight, when no actions are taken.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Infinite Balls and Jugs [solution]

Well the ruler analogy finally did it for me.

Let a pencil and an eraser both start at the 1-inch mark on a ruler. Let them both start moving toward the 0 mark. Let the eraser move at a constant speed, so it will reach the 0 mark in exactly 10 minutes. Let the pencil move in such a manner that when the eraser reaches the [imath]\large\frac{1}{2}[/imath]-inch mark, the pencil has reached the [imath]\large\frac{1}{1024}[/imath]-inch mark, and in general when the eraser reaches the [imath]2^{-n}[/imath]-inch mark the pencil has reached the [imath]2^{-10n}[/imath]-inch mark. When the pencil reaches the 0 mark it lifts up and stops drawing on the ruler, in a manner so that the pencil does not actually draw on the 0 mark itself.

Clearly the pencil is always ahead of the eraser. So the pencil is bounded between the 0 mark and the eraser. But the eraser moves at constant speed, so it reaches the 0 mark in exactly 10 minutes. It is easy to see that the pencil will reach the 0 mark in exactly 10 minutes as well. Furthermore, as the eraser moves, it erases the pencil marks.

So at any time before 10 minutes, say when the eraser is at the [imath]2^{-k}[/imath] mark, there are [imath]9k[/imath] of the binary fraction marks that have a pencil line on them. As the eraser approaches the 0 mark, that number grows asymptotically. But it is obvious that when 10 minutes have gone by the eraser will have erased the entire pencil line, and precisely zero of those marks will still have pencil lines on them.
wee free kings

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

### Re: Infinite Balls and Jugs [solution]

Wow, that's pretty good.
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

Qaanol wrote:Well the ruler analogy finally did it for me.

Let a pencil and an eraser both start at the 1-inch mark on a ruler. Let them both start moving toward the 0 mark. Let the eraser move at a constant speed, so it will reach the 0 mark in exactly 10 minutes. Let the pencil move in such a manner that when the eraser reaches the [imath]\large\frac{1}{2}[/imath]-inch mark, the pencil has reached the [imath]\large\frac{1}{1024}[/imath]-inch mark, and in general when the eraser reaches the [imath]2^{-n}[/imath]-inch mark the pencil has reached the [imath]2^{-10n}[/imath]-inch mark. When the pencil reaches the 0 mark it lifts up and stops drawing on the ruler, in a manner so that the pencil does not actually draw on the 0 mark itself.

Clearly the pencil is always ahead of the eraser. So the pencil is bounded between the 0 mark and the eraser. But the eraser moves at constant speed, so it reaches the 0 mark in exactly 10 minutes. It is easy to see that the pencil will reach the 0 mark in exactly 10 minutes as well. Furthermore, as the eraser moves, it erases the pencil marks.

So at any time before 10 minutes, say when the eraser is at the [imath]2^{-k}[/imath] mark, there are [imath]9k[/imath] of the binary fraction marks that have a pencil line on them. As the eraser approaches the 0 mark, that number grows asymptotically. But it is obvious that when 10 minutes have gone by the eraser will have erased the entire pencil line, and precisely zero of those marks will still have pencil lines on them.

That's cheating! You went and made things intuitive!

In seriousness though, nice!
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Puck
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

### Re: Infinite Balls and Jugs [solution]

It still seems crazy, because it's plain that in step one of the process, more marks are drawn than erased, and there are no steps where more marks are erased than drawn, and yet every drawn mark is erased at the end of the process. I guess that shouldn't surprise me as much as it does; after all it's really just saying that 10*∞ = ∞, and I don't have a problem with that in the least.
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

### Re: Infinite Balls and Jugs [solution]

I love the ruler example. So, what happens if we apply that same logic to the case where instead of removing a ball, we relabel it?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

lordatog wrote:I love the ruler example. So, what happens if we apply that same logic to the case where instead of removing a ball, we relabel it?

That's harder... something with a chisle that's curling the sawed off wood forward and up... at the end the entire ruler is just smeared infinitely upwards?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

That's a tricky one. After all, we can't say that any finite ball that is added is removed... it's true that every ball is relabeled and thus there still cannot be any finite labeled balls, but there is something, and it cannot have a finite number of digits.

I think that means they're uncountable?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:That's a tricky one. After all, we can't say that any finite ball that is added is removed... it's true that every ball is relabeled and thus there still cannot be any finite labeled balls, but there is something, and it cannot have a finite number of digits.

I think that means they're uncountable?

This has already been answered, depending on the method of relabeling, you might have balls with an infinite string of digits on them, or what's written on them may be undefined.

There is no way you're getting anything uncountable. The countable union of countable sets is countable.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Infinite Balls and Jugs [solution]

Aren't numbers with infinitely many digits equally as valid for diagonal proof of uncountability as the real numbers? That's not to say we have uncountably many of them.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs [solution]

WarDaft wrote:Aren't numbers with infinitely many digits equally as valid for diagonal proof of uncountability as the real numbers? That's not to say we have uncountably many of them.

You're right that the set of all infinite strings of digits is uncountable.

I was not very specific in my last post, but you'll never have all infinite strings, just particular ones. For example, if your relabeling consists of adding a 1 at the end of the ball, then you'll have all finite strings of digits followed by infinitely many 1's.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

dedalus
Posts: 1169
Joined: Fri Apr 24, 2009 12:16 pm UTC
Location: Dark Side of the Moon.

### Re: Infinite Balls and Jugs [solution]

Here's a question:

Suppose there was a machine in the urn that relabels each ball such that every step, after the ball with the lowest number had been removed, the balls were in a sequence starting from 1 and going up. I.e. it removed 1 from the number on each ball, and then n-1 from the balls that had just been added in the nth step. You're still removing the lowest numbered ball in the urn, and you're still removing the same ball each step that you would've without the machine. However, now when you ask the question 'what is the lowest numbered ball after the final step', then I can say 1. And I'm going to change my balls to lcd displays, so instead of erasing the old number, you just overwrite the infinite-sized memory banks as appropriate. So by rights this would end up with an infinite number of balls inside the urn. How does this differ from the original situation?

Regarding the ruler; when the pencil reaches the 0 mark, there are an infinite number of marks separating it from the rubber, right? And this happens at exactly the same time. So then at exactly the same time we have an infinite number of marks and no marks on the ruler. But that's ok, because the marks that still existed between the time when the pencil reached the end of the ruler and the rubber reached the end of the ruler get rubbed out in an infinitely small period of time. Which makes sense, because clearly the pencil reaches the 0 mark before the rubber does, but only an infinitely small amount of time before. Coincidentally the exact same amount of time that it requires for the rubber to remove the remaining marks.
doogly wrote:Oh yea, obviously they wouldn't know Griffiths from Sakurai if I were throwing them at them.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Infinite Balls and Jugs [solution]

dedalus wrote:Here's a question:

Suppose there was a machine in the urn that relabels each ball such that every step, after the ball with the lowest number had been removed, the balls were in a sequence starting from 1 and going up. I.e. it removed 1 from the number on each ball, and then n-1 from the balls that had just been added in the nth step. You're still removing the lowest numbered ball in the urn, and you're still removing the same ball each step that you would've without the machine. However, now when you ask the question 'what is the lowest numbered ball after the final step', then I can say 1. And I'm going to change my balls to lcd displays, so instead of erasing the old number, you just overwrite the infinite-sized memory banks as appropriate. So by rights this would end up with an infinite number of balls inside the urn. How does this differ from the original situation?

No, I would say the urn ends empty. Consider that every ball enters the urn and leaves the urn, and afterwards is untouched. The fact that the labeling is messing around changes nothing, except the numbers on the balls removed. You end up with an empty urn and huge pile of balls labeled 1.

dedalus wrote:Regarding the ruler; when the pencil reaches the 0 mark, there are an infinite number of marks separating it from the rubber, right? And this happens at exactly the same time. So then at exactly the same time we have an infinite number of marks and no marks on the ruler. But that's ok, because the marks that still existed between the time when the pencil reached the end of the ruler and the rubber reached the end of the ruler get rubbed out in an infinitely small period of time. Which makes sense, because clearly the pencil reaches the 0 mark before the rubber does, but only an infinitely small amount of time before. Coincidentally the exact same amount of time that it requires for the rubber to remove the remaining marks.

The pencil and the rubber arrive at exactly the same time.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.