Where are all the balls?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
kryptonaut
Posts: 79
Joined: Mon Nov 07, 2016 4:06 pm UTC

Where are all the balls?

Postby kryptonaut » 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,...

User avatar
LaserGuy
Posts: 4513
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: Where are all the balls?

Postby LaserGuy » 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.

User avatar
ConMan
Shepherd's Pie?
Posts: 1660
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Where are all the balls?

Postby ConMan » 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.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3364
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Where are all the balls?

Postby Soupspoon » 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!)

User avatar
ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Where are all the balls?

Postby ucim » 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
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
Sizik
Posts: 1205
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Where are all the balls?

Postby Sizik » Tue Jul 31, 2018 8:46 pm UTC

They're all in pot pω, the one after all of the finitely-labelled pots.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Where are all the balls?

Postby ucim » 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ω)
Last edited by ucim on Wed Aug 01, 2018 1:56 pm UTC, edited 1 time in total.
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3364
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Where are all the balls?

Postby Soupspoon » 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 ω…)

User avatar
ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Where are all the balls?

Postby ucim » 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
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
kryptonaut
Posts: 79
Joined: Mon Nov 07, 2016 4:06 pm UTC

Re: Where are all the balls?

Postby kryptonaut » 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.]

User avatar
ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Where are all the balls?

Postby ucim » 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
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

mward
Posts: 120
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: Where are all the balls?

Postby mward » 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 ω"!

User avatar
ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Where are all the balls?

Postby ucim » 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
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests