[Guest]

After reading unreality's problems dealing with infinite numbers, I decided to post my own. To be honest, it's not "my own," since I read it in a book a few years ago (I don't remember which book, but it was really good. You should all read it).

Suppose you have 2 bins, labeled 'A', and 'B'. To start, bin A has an infinite number of ping pong balls, and they are numbered sequentially from 1 to infinity. Each ball has a unique number printed on it. Bins B is empty to start.

You begin an experiment that will last 1 minute, but will include an infinite number of iterations. Each iteration will take exactly half of the time remaining - ie, the first iteration will be completed after 30 seconds, the second after 45, the third after 52.5, etc. At each iteration, you do two things: 1st, take the two lowest numbered balls out of bin A and put them in bin B; 2nd, take the one lowest numbered ball out of bin B, and throw it away.

So, in the first 30 seconds, you take balls 1 and 2 out of A and put them in B, then take ball 1 and throw it away. In the next 15 seconds, you take balls 3 and 4 out of A, put them in B, then throw away ball 2. As you can see, the number of balls in bin A will decrease by 2 with every iteration, and the number of balls in bin B will increase by 1.

The question is this: after the entire minute has elapsed, how many balls will be in bins A and B?

[Guest]

The question is this: after the entire minute has elapsed, how many balls will be in bins A and B?

both be empty.

[Guest]

I believe, since there are an infinate number of balls, that bin "b" will always have half the number of ping pong balls that 'a" has.

[Guest]

won't there be infinite amount in both beacuse if the iterations keep taking half the time, the minute won't properly finish if you get what i'm talking about

Edited July 29, 2008 by lemonymelon

[Guest]

won't there be infinite amount in both beacuse if the iterations keep taking half the time, the minute won't properly finish if you get what i'm talking about

The one-minute / half-time thing is the way around that problem. You could also set it up as doing it once a minute for an infinite amount of time, but that raises the added difficulty of understanding how you can ever be at the end of infinite time. This way, the minute is over after one minute, no problem there. You just have to imagine that you are moving faster and faster as the time gets closer and closer to one minute.

The main thrust of the question is, what happens after you have done an infinite number of iterations?

[Guest]

INFINITY HAPPENS!!!!!

AAAARGH!

[Guest]

What color are the balls?

[Guest]

What color are the balls?

White with black numbers written on them.

[Guest]

infinite in both?

Good one, I'm not so sure myself.

[Guest]

So long as BOTH items must happen in order for an iteration occurs, then A should be empty and B should contain 1/2 of infinity...

Right? ...Sounded better in my head... LOL...

[Guest]

The one-minute / half-time thing is the way around that problem. You could also set it up as doing it once a minute for an infinite amount of time, but that raises the added difficulty of understanding how you can ever be at the end of infinite time. This way, the minute is over after one minute, no problem there. You just have to imagine that you are moving faster and faster as the time gets closer and closer to one minute.

The main thrust of the question is, what happens after you have done an infinite number of iterations?

I think the way to look at it is this:

At every iteration, you toss the lowest numbered ball, as well as doing a bunch of other unimportant stuff. So if you repeat this process an infinite number of times, you will have thrown away an infinite number of balls - i.e. all of them - and can therefore not have any left. Another way of looking at it is that every number eventually gets discarded, so when you complete your task, you have discarded everything, and can have nothing left.

How this is physically accomplished, however, is decidedly less clear.

[Guest]

At each iteration, you do two things: 1st, take the two lowest numbered balls out of bin A and put them in bin B; 2nd, take the one lowest numbered ball out of bin B, and throw it away.

So, in the first 30 seconds, you take balls 1 and 2 out of A and put them in B, then take ball 1 and throw it away. In the next 15 seconds, you take balls 3 and 4 out of A, put them in B, then throw away ball 2. As you can see, the number of balls in bin A will decrease by 2 with every iteration, and the number of balls in bin B will increase by 1.

The question is this: after the entire minute has elapsed, how many balls will be in bins A and B?

Now, d3k3 makes a good point, however, at each iteration, is there a check to see if there are sufficient balls to complete the entire iteration? (Ie: we only have 2 balls in A and 0 in B. We take the two from A and put them in B. We trash the low one from B. What if we only had 1 in A ? do we stop or do we still get it and throw it in B, then trash it?). I think that is the biggest question that needs to be agreed upon before this puzzle can be solved.

[unreality]

since A has an infinite number of balls, it never loses balls, it just keeps putting them in B. They end with an infinity of balls in both bins after infinity of iterations

[Guest]

since A has an infinite number of balls, it never loses balls, it just keeps putting them in B. They end with an infinity of balls in both bins after infinity of iterations

In that case I pose this question - since every ball has a number assigned to it, give me the number of some of the balls in each bin.

[bonanova]

In that case I pose this question - since every ball has a number assigned to it, give me the number of some of the balls in each bin.

... forcing us, right in the middle of thinking about infinity, to think in finite terms. Not nice!

But Ok, I guess that's fair. Let's see what we have.

By the OP, after a full minute has passed, there have been an infinity of operations on the bins.

Those operations result in an infinity of integers [or balls, but let's think of integers because

we've been asked about specific numbers] moving from bin A to bin B, and the lower half

of these integers leaving bin B.

We're all kind of thinking that the bins, even after the full minute, still have balls in them.

Now we're being asked: if bin A and bin B are NOT EMPTY, name some of the the integers they contain.

Seems impossible, but ... maybe not. Read on.

What integers will have been left in bin A?

[1] The answer is: bin A will have all the integers it initially had, minus the infinity of integers that were taken from it.

What integers will remain in bin B?

[2] The answer is: bin B will contain the upper half of the infinity of integers that were taken from bin A.

What specific integers are in the A and B sets?

[3] The answer is: none that you can specify.

If you specify an integer, 13 is as good as any, it will eventually leave bin A, and later it will leave bin B.

So let's take these three statements, which seem all to be unavoidably true, and see where they leave us.

And since I've forgotten how to write the symbol, let me use 8 to represent infinity:

1. Bin A has 8-8 balls remaining.
   
2. Bin B has 8/2 balls remaining.
   
3. Bins A and B contain no identifiable integers.
   

We can wriggle out of [1] by saying 8-8 is undetermined, and therefore could be taken to be 8.

We can wriggle out of [2] by saying that 8/2 is still 8.

Okay so far.

Now [3] seems like a proof [by induction - it's true for 1, and if it's true for n, it's also true for n+1] that the bins are empty.

But [3] can be restated in the same terms as [1] and [2].

Let 8_a be the count of the integers originally in bin A.

Let 8_b be the count of operations performed during the full minute described in the OP.

Then, the above 3 points can be stated this way:

Initially,

1. bin A contains 8_a integers [or balls]
   
2. bin B contains 0 integers
   
3. All the integers - 13, for example - are in bin A; no integers are in bin B.
   

After the full minute,

1. bin A contains 8_a - 8_b integers
   
2. bin B contains the upper half of the first 8_b integers
   
3. bin A contains all of the integers that lie between 8_b and 8_a; bin B contains all the integers between 8_b/2 and 8_b.
   

Now we see that all the answers contain 8-8 in some form, and you can Google "infinity minus infinity" to proceed further.

Anyway, you may now resume the part of your life that is not indeterminate, assuming it exists.

[Guest]

Now, d3k3 makes a good point, however, at each iteration, is there a check to see if there are sufficient balls to complete the entire iteration? (Ie: we only have 2 balls in A and 0 in B. We take the two from A and put them in B. We trash the low one from B. What if we only had 1 in A ? do we stop or do we still get it and throw it in B, then trash it?). I think that is the biggest question that needs to be agreed upon before this puzzle can be solved.

There is always a sufficient number of balls, since they are infinite.

[Guest]

There is always a sufficient number of balls, since they are infinite.

You guys are forgetting that you cant ahve a "infinity" count of objects.. Therefore the number of balls in A must be a logical number, which means after many iterations there will be no balls left in bin A to complete the requirements of putting balls in B

[Guest]

cant ahve a "infinity" count of objects..

Why not? It is well established that the set of natural numbers is infinite. The balls themselves simply a convenient placeholder for them.

I say that because they are infinite, there are always enough balls to complete the next "iteration". However, because there is no such thing as the infinitieth iteration, I am also able to argue that if you were to repeat the process infinitely, you would end up with both bins empty. That may sound irrational or contradictory to some, but I think it's perfectly logical. How the process actually ends is not relevant, we only need to know that it has a conclusion (as specified by the OP).

[Guest]

In physical terms, both bins will *always* contain more balls.

For any ball you can imagine being removed from bin B, I can give you one which will still be in bin B (eg. x+1) and one which will still be in Bin B (eg. 2x+1). The problem with considering 'infinity' is that it is not a physical concept (as others have pointed out). In your original problem, you can never *physically* get to one minute, as there's always another step before you get there.

The only answer I think you can give is, at any point in time *up to* your "one minute" moment,

there are an infinite number of balls in Bin A,

a finite and well defined number of balls in Bin B,

a finite and well defined number of balls have been thrown away.

As we tend towards one minute,

Bin A still has an infinite number of balls,

Bin B tends towards an infinite number of balls (ie. for an arbitrarily large numbered ball, I can tell you when it gets put into Bin B)

the number of thrown away balls tends to infinity (ie. for an arbitrarily large numbered ball, I can tell you when it has been thrown away).

There's nothing wrong with (3 x infinity) = infinity. It's true! So the answer is: none of us really understand infinity, and we certainly can't do 'normal' maths like (infinity - infinity)=0! (actually infinity - infinity = anything, depending on how you define 'infinity'!)

[Guest]

... forcing us, right in the middle of thinking about infinity, to think in finite terms. Not nice!

But Ok, I guess that's fair. Let's see what we have.

By the OP, after a full minute has passed, there have been an infinity of operations on the bins.

Those operations result in an infinity of integers [or balls, but let's think of integers because

we've been asked about specific numbers] moving from bin A to bin B, and the lower half

of these integers leaving bin B.

We're all kind of thinking that the bins, even after the full minute, still have balls in them.

Now we're being asked: if bin A and bin B are NOT EMPTY, name some of the the integers they contain.

Seems impossible, but ... maybe not. Read on.

What integers will have been left in bin A?

[1] The answer is: bin A will have all the integers it initially had, minus the infinity of integers that were taken from it.

What integers will remain in bin B?

[2] The answer is: bin B will contain the upper half of the infinity of integers that were taken from bin A.

What specific integers are in the A and B sets?

[3] The answer is: none that you can specify.

If you specify an integer, 13 is as good as any, it will eventually leave bin A, and later it will leave bin B.

So let's take these three statements, which seem all to be unavoidably true, and see where they leave us.

And since I've forgotten how to write the symbol, let me use 8 to represent infinity:

1. Bin A has 8-8 balls remaining.
   
2. Bin B has 8/2 balls remaining.
   
3. Bins A and B contain no identifiable integers.
   

We can wriggle out of [1] by saying 8-8 is undetermined, and therefore could be taken to be 8.

We can wriggle out of [2] by saying that 8/2 is still 8.

Okay so far.

Now [3] seems like a proof [by induction - it's true for 1, and if it's true for n, it's also true for n=1] that the bins are empty.

But [3] can be restated in the same terms as [1] and [2].

Let 8_a be the count of the integers originally in bin A.

Let 8_b be the count of operations performed during the full minute described in the OP.

Then, the above 3 points can be stated this way:

Initially,

1. bin A contains 8_a integers [or balls]
   
2. bin B contains 0 integers
   
3. All the integers - 13, for example - are in bin A; no integers are in bin B.
   

After the full minute,

1. bin A contains 8_a - 8_b integers
   
2. bin B contains the upper half of the first 8_b integers
   
3. bin A contains all of the integers that lie between 8_b and 8_a; bin B contains all the integers between 8_b/2 and 8_b.
   

Now we see that all the answers contain 8-8 in some form, and you can Google "infinity minus infinity" to proceed further.

Anyway, you may now resume the part of your life that is not indeterminate, assuming it exists.

Ok...I think my brain just imploded x_X

[Guest]

The answer, which was written by people who know a lot more about this than I do, is that there will be zero balls in each bin.

The logic is this: every ball has a number. For every number, I can tell you when that ball was removed from bin A, and when it was removed from bin B. As counterintuitive as it seems, there can't be any balls in either bin, because they have all been removed.

The book I read this in presented this problem as an introduction to the idea of cardinality, but I thought it was a very good thought experiment / paradox. There are still some objections to the solution that I can't respond to, such as - the number of balls in bin B increases monotonically with time. At any point in time, I can tell you (a), how many balls are in bin B, and (b), that the number of balls has never been higher. This intuitively contradicts the solution, almost as much as the logic for the solution seems inarguable.

[bonanova]

The answer, which was written by people who know a lot more about this than I do, is that there will be zero balls in each bin.

The logic is this: every ball has a number. For every number, I can tell you when that ball was removed from bin A, and when it was removed from bin B. As counterintuitive as it seems, there can't be any balls in either bin, because they have all been removed.

The book I read this in presented this problem as an introduction to the idea of cardinality, but I thought it was a very good thought experiment / paradox. There are still some objections to the solution that I can't respond to, such as - the number of balls in bin B increases monotonically with time. At any point in time, I can tell you (a), how many balls are in bin B, and (b), that the number of balls has never been higher. This intuitively contradicts the solution, almost as much as the logic for the solution seems inarguable.

My first post shows the answers depend on the difference of two infinities.

Nevertheless the answers are']

1. An infinite number of balls are thrown out.
   
2. An infinite number are in bin B.
   
3. An infinite number are in bin A.
   

Let's talk about cardinality of infinite sets.

Suppose set A, B and C contains all the integers, all the even integers and all the odd integers from 1 to 100, respectively.

A = {1, 2, 3, ... 100}

B = {2, 4, 6, ... 100}

C = {1, 3, 5, ... 99}

The cardinality of the three sets are 100, 50, and 50 respectively.

A is twice as large as B and C.

But replace 100 with infinity and you get something very different.

Now we have

A = {1, 2, 3, ... }

B = {2, 4, 6, ... }

C = {1, 3, 5, ... }

These three sets have the same cardinality.

It's called Aleph-null, the cardinality of any countably infinite set.

Any set whose members have a 1-1 correspondence with the natural numbers has this cardinality.

What's counter-intuitive about this is that set A has members that set B does not - namely the members of set C.

Nevertheless they have the same cardinality: the members b_i of B correspond 1-1 with the members a_i of A:

b_i = 2a_i for all i.

Any two countably infinite sets have the same cardinality, even if one has countably infinite more elements than the other.

For example, the set of all integers and the set of even integers have the same cardinality.

Let's introduce bin C which catches all the balls discarded from bin B. Let 8 stand for infinity.

Initially,

1. bin A contains the integers [balls] from 1 to 8
   
2. bin B contains 0 integers
   
3. bin C contians 0 integers
   

After N operations,

1. bin A contains the integers from (2N+1) to 8: a countably infinite number of integers
   
2. bin B contains the integers from (N+1) to 2N: N integers
   
3. bin C contains the integers from 1 to N: N integers
   

That is, the cardinality of bin A is Aleph-null, of B is N, and of C is N.

Note that the elements of bin A have a 1-1 correspondence with the integers. Just add (2N).

The elements of bin B have a 1-1 correspondence with the integers 1-N. Just add N.

The elements of bin C have a 1-1 correspondence with the integers 1-N. They are the integers.

What happens as N -> 8?

1. bin A's integers still have a 1-1 correspondence with the natural numbers. Just add (28). [1]
   
2. bin B's integers now have a 1-1 correspondence with the natural numbers. Just add 8. [1]
   
3. bin C's integers now have a 1-1 correspondence with the natural numbers. They are the natural numbers.
   

So all three bins have a countably infinite number of integers.

[1] How can we add 8 to 8 and maintain cardinality?

Because adding cardinalities works only for finite sets.

The set of even integers and of odd integers both have cardinality Aleph-null. And so does their union.

Even and odd numbers have a 1-1 correspondence. Just add 1 to a member of odds to get the corresponding member of evens.

But suppose we placed the set of even numbers after the set of odd numbers, instead of interleaving them.

The correspondence still exists: Just add 8 to the member of odds to get the corresponding member of the evens.

Or, in the case of bin A, add 28.

Change the problem slightly, but in a way that will not change the answer.

As before, move the two lowest numbered balls from bin A to bin B.

But now, move the highest numbered ball from bin B to bin C.

After each operation the bins contain the same number of balls as if we

had moved the lowest numbered ball from bin B to bin C.

The number of balls in each bin is not changed.

In the 1st move, balls 1 and 2 go from A to B, and ball 2 moves to C.

In the 2nd move, balls 3 and 4 to from A to B, and ball 4 moves to C.

And so forth.

After the full minute,

bin B contains the odd integers [an infinite number of integers]

bin C contains the even integers [also an infinite number of integers].

What about bin A? It has an infinite number of integers as well.

Visualize it this way.

Take a line segment and mark it with 1, 3, 5, 7, 9, ... N at each unit of length, [N is odd]

Put an 2nd line segment, marked with 2, 4, 6, 8, ... N+1 at each unit of length, after it.

Put a 3rd line segment, similarly marked with N+2, N+3, N+4 ... 2N, after the 2nd segment.

Let N go to infinity.

The numbers on the first line are the numbers in bin B.

The numbers on the second line are the numbers in bin C.

The numbers on the third line are the numbers in bin A.

All three bins contain a countably infinite number of balls.

[Guest]

This is a canonical paradox, used to show young mathematicians that you can't just let things go to infinity willy-nilly: you need to first define limiting behavior clearly. Since it's been shown by several people that each bin must contain an infinite number of balls, let me present a

Suppose bin B contains some ball. That ball is labeled with a natural number, say N. But at step N (which occured after 60*(1-2^N) seconds), this ball was removed from bin B; so bin B cannot contain any ball.

Please note that this is not an informal argument. Any proof that bin B contains an infinite number of balls contradicts this, which is why it is a paradox: bin B must simultaneously be empty and contain infinitely many balls.

The place that the paradox lies here is in the implicit assumption that we can have a "box" which contains one ball for each integer. We have a mixture of physical objects (balls with numbers painted on them) and purely platonic abstracts (infinity).

Challenge: describe the algorithm given in the problem as a mathematical object. If we do this, the answer will be come clear.

would be as a function from the natural numbers to the set of ordered pairs of sets of integers. (Note that the codomain in this case has cardinality 2^|N|, which if we accept CH is the cardinality of the reals. That's okay, we just know we won't use all of them.)

So, our function takes the integer n to the ordered triple whose elements are:

{2n+1,2n+2,...} the set of integers greater than 2n; these are the balls that are in bin A after the move.

{n+1,n+2,...,2n}, the set of balls that are in B after the move.

How do we take the limit at infinity here? The limit is defined precisely when the limsup and liminf exist and are equal. For bin A, they do exist, and they are equal--both are the empty set. For bin B, they are likewise both the empty set, and so bin B is also empty. This is a counterintuitive result, given the monotonicity of the number of balls in B, but makes sense from a rigorous mathematical standpoint.

It's perfectly acceptable, in mathematics, to have an undefined limit. It is a meaningful fact.

Taking the limsup and liminf for a family of sets (for those of us that aren't set theorists):

Suppose we have a family of sets A1,A2,...,An,... (countably many of them).

The limsup of this family is:

Intersection (n=1,...,infty) [union (k=n,...,infty) Ak]

So, we take the union of all sets beyond a certain point, and take the intersection of all these. In the bin A example above, the sets are nested, so the union is just An; the intersection of all the An is empty. In bin B, the union is the set {n,n+1,...}; the intersection of all these sets is also empty.

The liminf of the family is:

Union (n=1,...,infty) [intersection (k=n,...,infty) Ak]

So, we intersect all the sets beyond a certain point, and take the union of all such intersections. In the bin A example above, each intersection is empty, and so the limsup, the union of all such intersections, is also empty. In bin B, the intersection is empty after finitely many steps (Intersection (k=n,...,2(n-1)+1) Bn is empty), and so the whole intersection is empty; again we have the union of empty sets.

It may be possible to define the algorithm rigorously in a way that makes both bins full at the end of time... though I doubt it, since each can be proved to contain no particular integer.

Interestingly, the above definition gives different results for the modified algorithm, wherein the highest-numbered ball from bin B is discarded. With the modified algorithm, the rigorous definition gives B containing all odd numbers, just as we'd expect. Yes, even though at each finite step B contains the same number of balls.

The counter-intuitive aspects of limits at infinity is what makes analysis any fun at all, so we should all be grateful.

[bonanova]

The "proof" that bin B is empty is fallacious.

Re-order the natural numbers so that the even numbers follow the odd ones.

Although you can't specify their place in the sequence by a finite number, the even numbers still exist.

[Guest]

My first post shows the answers depend on the difference of two infinities.

[etc...]

Nevertheless the answers are']

1. An infinite number of balls are thrown out.
   
2. An infinite number are in bin B.
   
3. An infinite number are in bin A.
   

There is a flaw in your logic: you are looking at the state after some finite number of operations/iterations, and from there trying to count to infinity.

Let us simplify the problem by first considering only bin A. Bin A doesn't care what happens to the balls once they are removed from it, only that they are no longer contained in A. Removing the lowest, or two lowest, numbers consecutively from bin A is equivalent to counting the natural numbers. Therefore, when I have accomplished my task of removing balls from bin A, I have removed the set of natural numbers from it. But this is precisely what bin A contained initially (and nothing more), so it must now be empty.

Now consider bin B. Everything removed from A is placed directly into B. Therefore, every natural number is contained in B, although not simultaneously. As before, when I discard the lowest numbered ball from B at each iteration, I am counting the natural numbers. Therefore, if I perform this task ad infinitum, I discard the set of natural numbers from B. B must therefore also be empty.

Another way of looking at it is this: because we started only with the natural numbers, any remaining balls in A or B must be subsets of N. There is no subset that satisfies the condition of always removing the lowest numbered ball from B, because this is the same as counting the members of N.

However, you are correct in saying that if you remove the highest numbered ball from B instead of the lowest, you will end up with the odd numbers in it.

[edit: clarification]

Edited July 30, 2008 by d3k3

[unreality]

this infinity-stuff is intense ;D