Page 1 of 1

### Where are all the balls?

Posted: Mon Jul 30, 2018 1:02 pm UTC
This is somewhat related to the Ross-Littlewood (balls and jugs) paradox, but I feel it's different enough to merit some discussion.

Suppose I have an infinite number of pots, labelled p1,p2,p3,... initially empty but each capable of holding one of an infinite number of balls, labelled b1,b2,b3,...

I start by placing ball b1 in pot p1, and then perform a series of steps: at each step I move the ball from the first occupied pot to the (even numbered) first pot that has never contained a ball, and add a new ball to the (odd numbered) pot after that one.

So...

Start: Place ball b1 in pot p1
Step 1: Move ball b1 from pot p1 to pot p2, and place ball b2 in pot p3
Step 2: Move ball b1 from pot p2 to pot p4, place ball b3 in pot p5
Step 3: Move ball b2 from pot p3 to pot p6, place ball b4 in pot p7
...
Step n: Move the ball from pot pn to pot p2n, place ball bn+1 in pot p2n+1

Then:
Each pot pn is filled exactly once, at step n/2 (even n) or (n-1)/2 (odd n)
Each pot pn is emptied exactly once, at step n
Each ball bn is placed into a pot at step n-1
After step n, pots p1...pn are all empty, and balls b1...bn+1 are all (somewhere) in pots pn+1...p2n+1

The first few steps look like:

Code: Select all

`1- 1 2- - 2 1 3- - - 1 3 2 4- - - - 3 2 4 1 5- - - - - 2 4 1 5 3 6`

Now let's allow each step n to take time 1/(2n) to complete - and examine what has happened at time t=1 when an infinite number of steps have been performed.

Every ball b1,b2,b3,... has been placed in a pot, and no balls have been discarded. But every pot p1,p2,p3,... has been filled once and subsequently emptied, so all the pots must be empty.

So, the question is... where are all the balls?

Observations:
Spoiler:
Pot pn will at some point contain ball bk where k can be found by removing all trailing zeros in the binary representation of n, then adding 1 and dividing by 2. See sequence https://oeis.org/A003602

Ball bk will at some point be found in all pots p(2k-1)(2n) where n=0,1,2,...

### Re: Where are all the balls?

Posted: Mon Jul 30, 2018 11:06 pm UTC
Someone with better knowledge of the math can probably explain this better, but my understanding is that this kind of problem ill-posed. You can't perform an infinite number of steps because the number of operations you need to perform is unbound. I think the best you can say is that the balls are somewhere farther down the line. You can't reach the end, so every pot you check will be empty.

### Re: Where are all the balls?

Posted: Tue Jul 31, 2018 12:18 am UTC
I'm pretty sure that in this instance, if you followed the super process then all the pots would be empty and there are no balls.

From pot n's perspective, it had a ball in it at some point, but that ball was removed and never replaced. Therefore, lim_(t->inf) of the number of balls in pot n is 0.

From ball n's perspective, it appears at some time, then gets moved across from pot to pot, such that the number of the pot it's in is always increasing over time. So at the end of the superprocess, there is no real number of pot that it could possibly be in.

### Re: Where are all the balls?

Posted: Tue Jul 31, 2018 12:28 am UTC
It's the opposite of Xeno's Paradox.

There, an event that finishes is redefined to never quite end, mathematically. Here, an event that does not end is portrayed as doing so only through mathematical trickery.

As far as the sequences go, I observe that the second half (rounded up) of the current used range of numbers run alternately through the present 'occupied' set, against a 'shuffled' set of the first half (rounded down), the exact manner of shuffling surely having a good description. And this combined sequence is offset away from the (unoccupied) zeroth element by the very last number (both listwise and absolute for that step).

Derive the 'shuffle' method and you can probably solve everything else, per step, or what number must occupy any particular position (later, currently or before any given step) but the infinitieth step is likely to produce values for currentness/top-end positions as undefined as the infinity itself is upon the line. The 'end location' of an infinitely moved ball certainly is. (Ohh, ninjaed on that last point!)

### Re: Where are all the balls?

Posted: Tue Jul 31, 2018 12:55 pm UTC
Other than the obfuscatory shuffling that happens, how is this fundamentally different from a situation where there are infinite jugs and one ball?

Your hand ("jug zero") starts out with the ball in it.
At step 0, the ball is placed into jug 1.
At step k, the ball is removed from jug k and placed into jug k+1.
Now let's allow each step n to take time 1/(2n) to complete - and examine what has happened at time t=1 when an infinite number of steps have been performed.
Where is the ball?

Answer that one, and the answer to the OP should be evident.

Jose

### Re: Where are all the balls?

Posted: Tue Jul 31, 2018 8:46 pm UTC
They're all in pot pω, the one after all of the finitely-labelled pots.

### Re: Where are all the balls?

Posted: Tue Jul 31, 2018 9:58 pm UTC
Ok. So since the pot after pω is pω+1, etc, then in the original question, the balls would be in pots pω thru pω·2.

What order are they in?

Jose
(edit: subscript ω·2 instead of 2ω)

### Re: Where are all the balls?

Posted: Tue Jul 31, 2018 10:03 pm UTC
Soupspoon wrote:As far as the sequences go, I observe that the second half (rounded up) of the current used range of numbers run alternately through the present 'occupied' set, against a 'shuffled' set of the first half (rounded down), the exact manner of shuffling surely having a good description.

(Is p necessarily even? Even with the 2 in there. Things get odd enough around ω…)

### Re: Where are all the balls?

Posted: Wed Aug 01, 2018 1:25 am UTC
It's not that they get odd, it's that getting there is odd. Once you're there, you have another well-ordered sequence. It happens to extend backwards, but not whence you came. That is, you can go from pω to pω-1 to pω-2... and never get to p0 whence you came. You can get there (sort of) but you can never go back.

Jose

### Re: Where are all the balls?

Posted: Wed Aug 01, 2018 9:35 am UTC
This is why I thought it worth discussing - so far we've had three types of resolution:

• The problem is ill-posed, you can't talk about the end-state of a never-ending sequence
• The pots are all empty, therefore all the balls have vanished
• The balls end up in pot pω (and maybe pots thereafter)

I'm inclined to think that if we stick to the regime where the ball and pot numbers are strictly finite (even though there are infinitely many of them) then the problem is indeed ill-posed, it's like asking "what happens when the never-ending thing ends?"

However, introducing transfinite numbers like ω allows for some more interesting discussion, and a way to prevent the balls apparently disappearing simply because we don't know (or can't describe) what numbered pots they are in - all finite-numbered pots end up empty, but that does not necessarily mean that all pots are empty, if we allow for transfinite numbers.

If we say that we end up with ω balls distributed in pots pω,pω+1,pω+2,... then I'm not sure what can be said about their actual locations. I don't think pot pω∙2 would be required, since ball bω does not come into play. But can we really say anything about the location of ball bn other than stating that it's 'definitely somewhere' in a pot pω+k for some non-negative finite k ?

[Given that ω is the first transfinite number which is larger than all finite numbers, I'm not sure that ω-1 is a valid concept, since that would then become ω itself. I believe ω has a successor ω+1 but no predecessor.

Also, strictly speaking I think ω+ω is more correctly written ω∙2 rather than 2ω, because adding ω 2's together simply produces ω whereas adding 2 ω's is the result we want.]

### Re: Where are all the balls?

Posted: Wed Aug 01, 2018 1:54 pm UTC
kryptonaut wrote:Also, strictly speaking I think ω+ω is more correctly written ω∙2 rather than 2ω, because adding ω 2's together simply produces ω whereas adding 2 ω's is the result we want.
Yep, you're right. Infinitely sloppy of me.

I think the issue is akin to nondifferentiability. At t=1, everything happens at once. This destroys any well-ordering that might have existed before. So, that point acts as a barrier in the same sense that the derivative of 1/x2 is "broken" at x=0, or how analytic continuation lets
1 + 2 + 3 + 4 + .... "equal" -1/12.

So, I'd say the question is malformed, but it hints at a well-formed question in a different problem space that has this answer.

EDIT

Here's a variant: There is a pez container with an infinite number of pezs, each labeled with a finite integer starting from 1, with each successive pez being labeled with the next integer (k+1). Is there a pez labeled ω? (no, there isn't - ω is not in the set of finite integers)

Now that that's settled - there are also an infinite number of jugs similarly labeled. On turn #1, pez 1 is placed into jug 1. On turn n, every pez (in jug k) is moved into the second next higher jug (k+2) (starting of course from the highest occupied jug, which should be (2n-1) This leaves n empty jugs in front of the set of full jugs). Jug n is then filled with pez n.

The result is a reversed finite string of pezs that keeps growing and moving further up the line.

Now make turn 1 last 1/2 unit, and each subsequent turn last half as long as the previous turn. The infinite set of turns now lasts one unit (t=1).

Where are the pezs? They are clearly in reversed order; what is the label on the first pez encountered? If you accept transfinite jugs, and say the pezs are in jugs ω thru ω∙2, then pez 1 is of course in jug ω∙2. What is the label on the pez in jug ω?

Jose

### Re: Where are all the balls?

Posted: Mon Aug 13, 2018 10:57 am UTC
In the topic "Infinite Balls and Jugs [solution]" I presented a method for solving supertask puzzles:

To calculate the output of any supertask it is sufficient to break down
the supertask into a set of finite tasks running in parallel. A "finite
task" is a task which completes within a finite number of steps and
then does nothing for the remaining infinite number of steps.

See: http://forums.xkcd.com/viewtopic.php?f=3&t=45522&p=4116961#p4116961

In this case, the function defining the set of balls in pot m at step n is a finite task: the set is empty after step m and remains empty thereafter. So all the pots end up empty.

But the question was not "What is in the pots?" but "Where are the balls?"

The function defining the position of ball m at step n is not a finite task (it changes infinitely often), so this problem is ill-defined.

This is very similar to the Hilbert's hotel problem discussed in my post linked above:
(4) For Hilbert's hotel where a guest is moved infinitely often (say, from room n to some room greater than n on each step): the guest's location never settles down to a fixed value, so the supertask of detemining the guest's final resting place is undefined. However, in a modern hotel the clerk hands the guest a keycard and a piece of paper with their room number written on it. Suppose the clerk computes the supertask first by writing on the paper, instead of repeatedly moving the guest. In this case, we can compute the result which appears on the paper handed to the guest:
At each stage the number on the paper is the set {0, 1, 2, ..., n-1}. The clerk adds n to this set, then n+1 and so on. The finite task for any given element m is that m is eventually added to the set (which is the room number written on the paper) and is never removed. At the end of the supertask, the set is {0, 1, 2, ...} which is precisely the number ω. The guest reads the paper and asks "where is room number ω?" The clerk reads the paper and realises he has made a mistake: there is no "room number ω" in the hotel. So the clerk has to find a different solution to his guest allocation problem.

What if, instead of moving the balls to different jugs, we label each ball with a jug number? If the label is defined as a sequence of decimal digits, then again this set does not settle down and the problem is undefined. Suppose we define the label as an ordinal number (i.e. a set of ordinal numbers), as we did in the hotel problem above, and examine this set. Then for each finite ordinal n, after a finite number of steps, n appears in the label and is never removed. So, in this case, the supertask of computing the label is well-defined and has a solution:

Each ball ends up with the label ω (the ordinal number ω is the set of all finite ordinals).

Note that no label ever gets beyond ω since only finite numbers are added to the label and the number ω is never added to the label. (The supertask which defines whether ω is in the label is finite and trivial).

If we add a jug labelled ω and also add one more step (step number ω) after all the previous steps in which we move each ball to the jug number written on the ball's label, then the answer to the question "where are all the balls?" is "in jug ω"!

### Re: Where are all the balls?

Posted: Mon Aug 13, 2018 3:59 pm UTC
mward wrote:If we add a jug labelled ω...
...then the problem is trivial. At least trivial in the sense that any infinite problem is trivial. The catch is that there is no jug labeled ω, but the ball "is supposed to go there". The question reduces to "where is the place that doesn't exist?"

Jose

### Re: Where are all the balls?

Posted: Wed Aug 15, 2018 3:31 pm UTC
ucim wrote:
mward wrote:If we add a jug labelled ω...
...then the problem is trivial. At least trivial in the sense that any infinite problem is trivial. The catch is that there is no jug labeled ω, but the ball "is supposed to go there". The question reduces to "where is the place that doesn't exist?"

Jose
Just follow the infinite row of pots until you get there; you literally can't miss it.

### Re: Where are all the balls?

Posted: Tue Sep 25, 2018 8:00 am UTC
ucim wrote:The question reduces to "where is the place that doesn't exist?"
Jose
Suppose there are ten jugs, labelled 0 to 9, and a ball starts in jug 0. On each step we move the ball from the jug it is in to the next higher jug. After 10 steps, all the jugs are empty: where did the ball go?

If we add a jug labelled 10...

... then the problem is trivial... The catch is that there is no jug labelled 10, but the ball "is supposed to go there". The question reduces to "where is the place that doesn't exist?"

### Re: Where are all the balls?

Posted: Tue Sep 25, 2018 2:10 pm UTC
That's ignoring the whole point of the thread?
There is no step which you can't complete. There's always a place to put the balls.

It is more like asking which digit will be returned in a function that never ends. Then asking about an infinitely fast processor to be tricky:

Code: Select all

`while (1){  i= (i+1) % 10}return i;`