Infinite balls

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Goemon
Posts: 442
Joined: Mon Nov 19, 2007 4:57 am UTC

Infinite balls

Postby Goemon » Thu Feb 04, 2016 4:07 am UTC

What's this puzzle/conundrum/paradox called?

Procedure: for each iteration k, Alice throws balls numbered 2k and 2k+1 into a room. Bob then removes ball k. i.e,

Step 0: Alice Adds balls 0, 1; Bob removes ball 0; room contains ball 1
Step 1: Alice adds 2, 3; Bob removes 1; room contains 2, 3
Step 2: Alice adds 4, 5; Bob removes 2; room contains 3, 4, 5
Step 3: Alice adds 6, 7; Bob removes 3; room contains 4, 5, 6, 7
...


After an infinite number of repetitions, how many balls are there in the room?

Answer A: at the completion of the kth step, there are k balls in the room; as k increases to infinity, the number of balls in the room increases to infinity
Answer B: each ball numbered k is removed from the room on the kth iteration. Every ball is removed from the room. None remain after infinite repetition
Life is mostly plan "B"

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

Re: Infinite balls

Postby ConMan » Thu Feb 04, 2016 4:55 am UTC

It's apparently the Ross-Littlewood paradox, although technically that paradox adds the idea of a supertask, i.e. a process that allows an infinite number of steps to be carried out in finite time.

It relates to the fact that frequently the behaviour of a process in the limit can be completely at odds with each individual step in that process. You have a sequence of sets A_1, A_2, A_3, ... which are the lists of balls in the room after each step. You can define one function to be s(k) = |A_k| = number of balls in the room at time k, which grows without bounds as k increases. You can define a whole class of functions b_n(k) = 1 if ball n is in the room after step k and 0 otherwise, and for all n you can clearly show that for each n the function b_n(k) is eventually a constant 0, meaning that for all sets past some k ball n is guaranteed to not be in the set, so if you tried to define some kind of "final step" set based on the values of the b_n then you'd say that there are no balls in the room after that many steps. So ... eh. Once you've dealt with limits a few times you quickly discover that it's perfectly fine for things to not have a well-defined limit, or for the limit to not behave like all the things leading to it.
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.

Cauchy
Posts: 600
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Infinite balls

Postby Cauchy » Thu Feb 04, 2016 8:44 am UTC

This kind of thing shows up in analysis all the time, and the question in the opening is just a discrete version of that. In analysis, the only sensible candidate for a limit of functions is the pointwise limit, that is if f is the limit of f_1, f_2, etc., then it must be the case that f(x) is the limit of f_1(x), f_2(x), etc. for each x. But if this limit is not "close" to the sequence of functions in a stronger sense, then there's no reason to expect that the limit has similar properties to the original functions. A couple different definitions of closeness get tossed around (in technical terms, we look at different metrics on the space of functions), but the most common one, called the L^2 distance, calculates the distance between f and g as int_{-infinty}^{infinity} (f(x)-g(x))^2 dx. If the sequence of functions converges to the pointwise limit using this sense of distance, then the limit will inherit a lot of nice properties that the individual functions might all share, and many calculations about the limit function can be evaluated in terms of the limit of the calculations on the original sequence of functions.

In this discrete version, we might look at B_k(n), the collection of functions that tell you whether ball n is in the room after step k. Each function B_k describes the state of the room after step k (by storing B_k(1), B_k(2), etc.), so it's natural to say that the state of the room "after an infinite number of repetitions" is the limit of the B_k's. The pointwise limit B of the B_k's is the constant zero function, since each ball is eventually out of the room forever after some point in time. But the distance between B and B_k, which, modeling based on the integral earlier, ought to be sum_{n=0}^{infinity} (B(n) - B_k(n))^2, is increasing without bound. So there's no reason to believe that, say, the "integral" of B (that is, \sum_{n=0}^{infinity} B(n)) is the limit of the integrals of the B_k's, which is to say that there's no reason to believe that the limit of the number of balls after k steps should be the number of balls after "infinity many" steps.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Infinite balls

Postby Cradarc » Fri Feb 05, 2016 10:26 am UTC

I don't think it's a paradox.
Fact 1: The number of balls in the room grows without bound with successive steps.
Fact 2: Every ball placed in the room during any given step will be taken out in another future step.

These two facts do not contradict because the number of steps are NOT finite. If you're filling a bucket with a small hole in it, as long as you are sending water in at a rate faster than the leak, the bucket will fill with water. If you stop putting water in, all the water will eventually leak out. If you don't stop, the water in the bucket grows over time. You can't ask "what happens after I continue sending water into the leaky bucket?". It doesn't make sense. There is no "after" if you are continually doing the task.

*Okay, the bucket is a bad example because water pressure builds with more water, but you get the idea.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1412
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Infinite balls

Postby Xenomortis » Fri Feb 05, 2016 11:23 am UTC

Cradarc wrote:I don't think it's a paradox.
Fact 1: The number of balls in the room grows without bound with successive steps.
Fact 2: Every ball placed in the room during any given step will be taken out in another future step.

These two facts do not contradict because the number of steps are NOT finite...

It isn't strictly paradoxical, but it is unintuitive to the lay person.
Hence the name "paradox".
Image

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

Re: Infinite balls

Postby jestingrabbit » Fri Feb 05, 2016 8:42 pm UTC

I think its unintuitive to the lay person because it asks us questions about what is essentially impossible from a physical perspective. And sure, you can resolve the issue, using the sorts of reasoning that Cauchy brings up, and go further and suggest that Cauchy's resolution is the only sensible resolution. But equally, a solid logical position to take is that such things are impossible and even talking about the end state of the room is nonsensical.

There's been a lot of logic puzzle threads that ask these questions in more precise, interrogative ways. Look at this one, for instance.

viewtopic.php?f=3&t=45360

For instance, the "just consider the fate of individual balls" approach is relying on the partial supertask axiom. But it won't help you work out the state of a lamp at time 1 which is toggled at times 1 - 2^(-n). There are genuinely deep things going on here.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Infinite balls

Postby PeteP » Fri Feb 05, 2016 9:19 pm UTC

ConMan wrote:It's apparently the Ross-Littlewood paradox, although technically that paradox adds the idea of a supertask, i.e. a process that allows an infinite number of steps to be carried out in finite time.

Question under the given solution if we follow the reasoning for the empty answer is there any reason the same wouldn't apply to the following: We increase a counter (which conveniently can display infinitely big numbers) by one an infinite number of times, what is the number at the end.=> That is basically directly related to the problem because the number of the lowest ball increases by one at each step (and in the variant in this thread it also equals the number of balls in the urn). So can I say it is zero because there is no finite number it hasn't passed?


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests