# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
bonanova
Daedalian Member

 Posted: Sat Nov 06, 2010 1:33 am    Post subject: 1 I read this Zeno-like paradox [some call them super tasks] some years ago. I was first convinced of answer [1] until someone argued convincingly for answer [2]. Then I changed the conditions innocuously [I think] to destroy answer [2]. Now I'm wondering if the paradox can even be stated, meaningfully. One can distinguish between super tasks like the man who moves half the remaining distance in half the remaining time, which is understandable and possible, and those like Thompson's Lamp that switches on and off in a convergent, geometrically decreasing time sequence. Is it on or off, finally? The latter question requires a nonexistent highest integer to provide an answer. But the following task doesn't seem to be of that type. I'll describe it, then ask: 1. Is answer [2] correct? 2. Does the question itself require an impossible assumption? Bin A contains Aleph-null ping-pong balls painted with the counting numbers. Bin B is empty Bin C is empty. After 1 tick, two balls, those numbered 1 and 2, are moved from Bin A to Bin B, then the lowest numbered ball in Bin B is moved to Bin C. Then, After 1/2 tick, two balls, numbered 3 and 4 are moved from A to B, then the lowest numbered ball in B is moved to C. Then. After 1/4 tick, 5 and 6 move from A to B and B's lowest ball goes to C. Then, After 1/8 tick ... rinse and repeat. After 2 ticks, describe the contents of Bin B. [If we object that ping-pong balls might at some point have to break the speed of light limit, the balls can be regarded as mass-less integers, and the bins can be thought of as sets.] Answer [1] B contains an infinite number of balls. Proof: Each step adds two balls and subtracts one ball. Answer [2] B is empty. Proof: Every ball enters and leaves the bin. What convinced me that [2] must be right was the question: If B contains even one ball, what is its number? Any number you give has a well-defined tick value at which it transferred to Bin C. But let's make an innocuous change. Instead of moving the lowest numbered ball from B to C, move the highest numbered ball from B to C. Now I can say B is not empty. Proof: ball # 1 entered B and stayed there. Can the answer depend on the shape of paint marks?_________________ Vidi, vici, veni. Last edited by bonanova on Sat Nov 06, 2010 2:41 am; edited 2 times in total
bonanova
Daedalian Member

 Posted: Sat Nov 06, 2010 2:03 am    Post subject: 2 Not to answer my own puzzles, but it seems that all of the integers enter set B and "half of them" leave. Since the even integers have the same cardinality as the integers, it's somewhat undetermined whether you remove them all. If you make the 1-1 correspondence between the integers and the integers, [moving the lowest integer from B to C aleph-null times] then you've moved them all. If you make the 1-1 correspondence between the integers and the evens [moving the highest integer from B to C aleph-null times] then you've left all the odd ones behind in B. OK, I'm cool with that, logically and mathematically. But I'm an engineer, and want the question to have an answer - I still want the difference in procedure to be physically innocuous. Do I have to give that up? Does physics have to stay finite? Are Banach and Tarski lurking in the room somewhere? Uhh nah, they messed around with aleph-one._________________ Vidi, vici, veni.
L'lanmal
Daedalian Member

 Posted: Sat Nov 06, 2010 3:30 am    Post subject: 3 Alice the Friendly Chowder Server and Bob the Chowder Nazi both have difficulties dealing with the lunch crowd. Every minute, 2 people arrive, and each Alice and Bob can only serve one. Alice tFCS solves this problem by having her customers form a line, first-come, first-served. Bob tCN instead picks one of the two to serve, and refuses to serve the other. Does Alice tFCS deny chowder to anyone who waits long enough in line? No. But each may have to wait a long time, and the later you come, the longer you will have to wait. Does Bob tCN deny chowder to anyone who waits long enough in line? Yes. Some of them. The difference here depends not on the people's clothing, skin color, or markings (unless Bob is a bigot as well as a, erm, "nazi"), merely on the algorithms they have chosen for chowder distribution. I hope the mappings are clear. n minutes from the start of lunch maps to 2-1/(2^n) ticks. Bin A contains all people outside who will enter the store. Bin B contains people who entered the store, but have not yet received chowder. Bin C contains people who received chowder. Alice is the queueing (lowest number) method. Bob is the higher number method. Ball number is order in line for Alice. Ball number is the preference function for Bob (where he serves the higher, not it is arbitrary which is 1 and which is 2, etc.). So I agree with [2]. Some of the intuitive confusion comes from the implication from ending at time "2" that the process is finite, and the length of the "line" converges to 0, or even converges at all. It does not. The "line" only gets longer as more people come, but each person who comes can still get served in finite time. In this case, time "2' is a label essentially meaning "eventually", and has little mechanical metric meaning. You would have great physical difficulty designing a machine that could move two balls (or even, say, electrons) in an arbitrarily short time (such as 1/(2^n) for arbitrarily large n).
Antrax
ESL Student

 Posted: Sat Nov 06, 2010 6:22 am    Post subject: 4 What L'l said I think. Assume to the contrary there's a ball left in B. But by its index you know exactly when it moved to C and it's in the interval [1, 2). So B has to be empty._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
bgg1996
BeeGees are awesome!

 Posted: Sat Nov 06, 2010 6:36 am    Post subject: 5 The question is, indeed, impossible. The ticks would never reach two. Using the same logic as answer two, name the fraction that would eventually make it to exactly two. You can't, because there isn't one. The argument against this is that the ticks could be a seperate occurence, and just a way of measuring the events that are taking place. The problem is, that means that the balls in the bins are moving at an infinite speed. P.S. Wasn't there already a GL puzzle on this exact subject. Something about an imp shoving marbles under rugs.
Antrax
ESL Student

 Posted: Sat Nov 06, 2010 7:22 am    Post subject: 6 Urns of Infinity is similar: http://www.greylabyrinth.com/puzzle/puzzle091_________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
JohnP
Icarian Member

 Posted: Sat Nov 06, 2010 4:01 pm    Post subject: 7 Answer [3] The question is nonsense. "I protest against the use of infinite magnitude as something completed" - C. F. Gauss
bonanova
Daedalian Member

Posted: Sat Nov 06, 2010 6:02 pm    Post subject: 8

 L'lanmal wrote: In this case, time "2' is a label essentially meaning "eventually", and has little mechanical metric meaning. You would have great physical difficulty designing a machine that could move two balls (or even, say, electrons) in an arbitrarily short time (such as 1/(2^n) for arbitrarily large n).

Second point first - we can get around that if balls are integers and bins are sets. This objection seems a red herring that would dismiss an infinity [perhaps] of standard paradoxes. Now to the first point.

move lowest ball:
After i steps, C contains 1 -> i; B contains i+1 -> 2i At completion [I'm not saying how, but 1 + 1/2 + ... has infinite terms and is <= 2] C contains 1 -> inf; B contains inf+1 -> 2inf. That is, infinity has been disjoined into its lower and upper halves. I CONCEDE THIS MEANS B IS EMPTY. The contents of C are all the integers [I mean, of course, all the counting numbers.] There is no inf+1 [inf is not a counting number] and "eventually" carries the day.

move highest ball:
After i steps, C contains the first i even integers; B contains the first i odd ones. Complete the process. C contains ALL the even integers; B contains ALL the odd integers. Now we've disjoined infinity in a proper manner. I is the union of E and O. All three with cardinality aleph-null. For every ball in C there is a named ball in B. In particular, ball #1 is in B, and "eventually" does not change its destiny to C. In this case I do NOT concede B is empty.

My issue is that the choice between moving lowest and highest seems innocuous but it's obviously not.

Simplify:
Forget bin B.

Case 1. On step i, move ball i from A to C. Let the process complete. Describe the contents of A. It's empty. Every ball was moved.

Case 2. On step i, move ball 2i from A to C. Let the process complete. Describe the contents of A. It contains all the odd integers.

----- edit to cloud the issue and test the "pat" answers -----

After the lowest two balls are taken from bin A, someone wipes off the numbers and re-writes them using invisible ink [any ball can be read later by applying heat] and places them in B.

Now another person moves one of the balls from B to C; of course s/he don't know which one it is. Complete the process. Apply heat. Describe the contents of B.

Seems inescapable that B contains on average half the odd numbers and half the even numbers, and C contains the other half
_________________
Vidi, vici, veni.
L'lanmal
Daedalian Member

Posted: Sat Nov 06, 2010 11:28 pm    Post subject: 9

bonanova wrote:
 L'lanmal wrote: In this case, time "2' is a label essentially meaning "eventually", and has little mechanical metric meaning. You would have great physical difficulty designing a machine that could move two balls (or even, say, electrons) in an arbitrarily short time (such as 1/(2^n) for arbitrarily large n).

Second point first - we can get around that if balls are integers and bins are sets. This objection seems a red herring that would dismiss an infinity [perhaps] of standard paradoxes. Now to the first point.

But I thought your objection was that integers were not intrinsic properties of physical balls, and the set theory result did not make physical intuitive sense to you...? As soon as you concede to frame it in terms of sets and integers to avoid physical impossibilities, you cannot then object to it on violating physical intuition...

 Quote: My issue is that the choice between moving lowest and highest seems innocuous but it's obviously not.

Agreed on both accounts: it seems innocuous when phrased in the ball example, but it is actually very different. I tried to explain this with the chowder example.

<snip>
 Quote: After the lowest two balls are taken from bin A, someone wipes off the numbers and re-writes them using invisible ink [any ball can be read later by applying heat] and places them in B. Now another person moves one of the balls from B to C; of course s/he don't know which one it is.

1) You limit the 2nd person's choice to the last two put in. This seems to be what you are thinking of, but this is clearly different than the "take the lowest" algorithm, which would require you to violate this on the second pull.

2) The 2nd person chooses randomly amongst all balls in B. For each ball, examine the probability that it remains in B at the "end" of the process. Your spoilered text should not seem quite so inescapable. (Although be careful drawing too many conclusions from this, because just because events have 0 probability does not mean they cannot happen.)
bgg1996
BeeGees are awesome!

 Posted: Sun Nov 07, 2010 5:50 am    Post subject: 10 The question is what balls would be in B when the machine is finished finished, right? It would never finish, as it has an infinite amount of work to do. The question is impossible, even when you replace the machine with integers, because it's the same problem, with the same answer. Since none of the variables that changed the eventual answer, then the answer is the same.
Thok*
Guest

Posted: Sun Nov 07, 2010 9:20 am    Post subject: 11

 bgg1996 wrote: The question is what balls would be in B when the machine is finished finished, right? It would never finish, as it has an infinite amount of work to do.

Define work in a mathematically rigorous way that's relevant to this problem.

There's a legitimate question here that given be defined as follows; given a sequence of sets A_n, how does one define a limit set lim n->oo A_n? This can be done by defining some notion of distance between pairs of sets, so that a limit exists only if the distance(A_n, A) goes to 0 as n gets large.

The naive notion of distance is just distance(A_n, A)=the number of elements in exxactly one of A_n, A. I believe this works (there are a useful set of axioms for distance that I won't describe but will provide a wiki link to if necessary), but then dist(A_n, A) is often infinite and particularly the sets that show up in ball of urns don't converge to anything.

An alternative notion is distance(A_n, A)=sum (1/2^i), where the sum is taken over all i that belong to exactly one of A_n, A. [Here I'm abusing the fact that A_N and A are subsets of the integers.] Again I believe this follows the standard set of rules for a distance (it's related to an L_P space), but now the distance is defined for every pair of sets, and it's easy to see that the sets of balls in urns converge to the empty set and nothing else.
bgg1996
BeeGees are awesome!

 Posted: Sun Nov 07, 2010 11:39 am    Post subject: 12 There is no answer to the sequence described, because the sequence will never finish. The eventual outcome of the sequence will not be evident until it is complete. Since the sequence never runs its full course, an answer can never be found. Consider the similiar sequence: 1-1+1-1+1-1+1-1+1-1+1-1+1-1+1-1+1-1+1-1......... What is the final sum? One answer is 0, [1-1]+[1-1]=0 Another answer is 1, [1-1]+[1-1]+1=1 Because the sequence continues indefinitely (never ends), there will never be a true answer.
Thok*
Guest

Posted: Sun Nov 07, 2010 12:09 pm    Post subject: 13

 bgg1996 wrote: Consider the similiar sequence: 1-1+1-1+1-1+1-1+1-1+1-1+1-1+1-1+1-1+1-1......... What is the final sum?

Undefined, since the limit doesn't exist. But that's not because there are infinitely many steps, but because under the standard metric the partial sums alternate 0 and 1, and thus there's no one point that the partial sums approach.

(If you must make that sum converge to something, 1/2 is probably the correct answer: it's consistent with the rule 1/(1-x)=1+x+x^2+x^3+.... when plugging in x=-1. But that would involve a different metric on infinite series and the real numbers.)
bgg1996
BeeGees are awesome!

 Posted: Sun Nov 07, 2010 12:41 pm    Post subject: 14 If the values did not fluctuate (0-0+0-0+...), then a logical assumption could be made about the eventual answer, yes. The only way a logical assumption about an answer can be made with an infinite series, however, is if the change either never occurs (0-0+0-0+...), or if the change eventually becomes zero, or extremely close to zero (1+1/2+1/4+1/8+...). That is why we can assume that the eventual end of the ball movement is two. This problem, however, is more like: a + b - a + c + d - b + e + f - c + g + h - d... There is always a change in the value, so an answer cannot be deduced.
Thok*
Guest

 Posted: Sun Nov 07, 2010 12:55 pm    Post subject: 15 [quote="bgg1996"This problem, however, is more like: a + b - a + c + d - b + e + f - c + g + h - d... There is always a change in the value, so an answer cannot be deduced.[/quote] Again, when you start talking about change in value, you are really talking about a metric structure and measuring distances between sets. And if you use the second metric structure I provided (because a priori, there isn't a default notion of distance between sets), you get a well defined notion of convergence of the sets. The situation you would be talking about is more like "Take two sets A and B". At tick whatever, switch all the balls from A to B or from B back to A. And in that situation, there's no set that anything converges to. The difference between the two situations can be made a bit more obvious if you assume that ball i requires work 1/2^i (the balls are getting progressively smaller or something as the numbers go up). Then in the original problem, only finite work is done and only a finite amount of work is done to any individual ball; the amount of work done to a given ball goes down as the number increases. In the switch back and forth problem, infinite work is being done to every single ball because every ball is moved infinitely many times.
bonanova
Daedalian Member

Posted: Sun Nov 07, 2010 8:07 pm    Post subject: 16

 L'lanmal wrote: I thought your objection was that integers were not intrinsic properties of physical balls, and the set theory result did not make physical intuitive sense to you...? As soon as you concede to frame it in terms of sets and integers to avoid physical impossibilities, you cannot then object to it on violating physical intuition...

I guess it shifts then to violating mathematical intuition. And, in my case at least, that matters much less. Point taken.

L'lanmal wrote:

 bonanova wrote: My issue is that the choice between moving lowest and highest seems innocuous but it's obviously not.

Agreed on both accounts: it seems innocuous when phrased in the ball example, but it is actually very different.

Which is why I then tried to force a paradox by posing this:

L'lanmal wrote:

 bonanova wrote: After the lowest two balls are taken from bin A, someone wipes off the numbers and re-writes them using invisible ink [any ball can be read later by applying heat] and places them in B. Now another person moves one of the balls from B to C; of course s/he don't know which one it is.

1) You limit the 2nd person's choice to the last two put in. This seems to be what you are thinking of, but this is clearly different than the "take the lowest" algorithm, which would require you to violate this on the second pull.

2) The 2nd person chooses randomly amongst all balls in B. For each ball, examine the probability that it remains in B at the "end" of the process. Your spoilered text should not seem quite so inescapable. (Although be careful drawing too many conclusions from this, because just because events have 0 probability does not mean they cannot happen.)

And here I actually did mean 2) - to keep everything else the same - making a third case for the B to C process:

1. move the lowest ball in bin B [or counting number in set B] to C
2. move the highest ball in bin B ... to C
3. move a randomly chosen [but identifiable] ball from bin B ... to C

And your answer to the random case is beautiful. I see it. Thank you.

I don't think I can force the paradox I had in mind, to follow an endless series of steps that add 1 to the count of something which when completed leaves the count at 0. I can only recall the words of that immortal 20th century mathematician Yogi Berra, who perhaps said it best: Nobody goes to that restaurant any more; it's too crowded.

But we're all agreed, are we not, that moving the highest of B to C leaves ball 1 in B and in fact leaves all the odd counting numbers in B and puts all the evens in C, producing two non-empty sets?
_________________
Vidi, vici, veni.
bgg1996
BeeGees are awesome!

Posted: Mon Nov 08, 2010 3:31 am    Post subject: 17

Thok* wrote:
 bgg1996 wrote: This problem, however, is more like: a + b - a + c + d - b + e + f - c + g + h - d... There is always a change in the value, so an answer cannot be deduced.

Again, when you start talking about change in value, you are really talking about a metric structure and measuring distances between sets. And if you use the second metric structure I provided (because a priori, there isn't a default notion of distance between sets), you get a well defined notion of convergence of the sets.

The situation you would be talking about is more like "Take two sets A and B". At tick whatever, switch all the balls from A to B or from B back to A. And in that situation, there's no set that anything converges to.

The difference between the two situations can be made a bit more obvious if you assume that ball i requires work 1/2^i (the balls are getting progressively smaller or something as the numbers go up). Then in the original problem, only finite work is done and only a finite amount of work is done to any individual ball; the amount of work done to a given ball goes down as the number increases. In the switch back and forth problem, infinite work is being done to every single ball because every ball is moved infinitely many times.

First, ball 1 (a) and ball 2 (b) are put into bin B, then ball 1 (a) is taken out.
a + b - a...

Then, ball 3 (c) and ball 4 (d) are put into bin B, and ball 2 (b) is taken out.
a + b - a + c + d - b...

And so on...
a + b - a + c + d - b + e + f - c + g + h - d + i + j - e + k + l - f + m + n - g + o + p - h + q + r - i + s + t - j + u + v - k + w + x - l + y + z - m + a(2) + b(2) - n + c(2) + d(2) - o...

This is why it is impossible to tell what balls are in bin B.
Thok*
Guest

 Posted: Mon Nov 08, 2010 8:39 am    Post subject: 18 bgg1996, go back to your favorite calculus book, and figure out why 1-1/2+1/3-1/4+1/5-... is ln(2) rather than not defined. Once you can do that, then you can see what's wrong with your argument.
L'lanmal
Daedalian Member

Posted: Tue Nov 09, 2010 12:43 am    Post subject: 19

bonanova wrote:
 L'lanmal wrote: 2) The 2nd person chooses randomly amongst all balls in B. For each ball, examine the probability that it remains in B at the "end" of the process. Your spoilered text should not seem quite so inescapable. (Although be careful drawing too many conclusions from this, because just because events have 0 probability does not mean they cannot happen.)

And here I actually did mean 2) - to keep everything else the same - making a third case for the B to C process:

1. move the lowest ball in bin B [or counting number in set B] to C
2. move the highest ball in bin B ... to C
3. move a randomly chosen [but identifiable] ball from bin B ... to C

And your answer to the random case is beautiful. I see it. Thank you.

Thank you. I salute you.

Something interesting about that approach is that accepting it is roughly equivalent to believing in real numbers, even though only integers and fractions were stated in the problem.

 Quote: I don't think I can force the paradox I had in mind, to follow an endless series of steps that add 1 to the count of something which when completed leaves the count at 0. I can only recall the words of that immortal 20th century mathematician Yogi Berra, who perhaps said it best: Nobody goes to that restaurant any more; it's too crowded.

In fact, I'd agree that the number of balls in B does this, viewing it as a function of balls with respect to time. The thing that makes it not a paradox is that the number of balls in B is discontinuous at many points, especially at the point of completion. The defining of ticks at 1, 1-1/2, 1-3/4, 1-7/8, ... is a clue that a method was used to construct this discontinuity at 2. It ensures that a function is defined in one method from [0,2) and potentially different method from [2,inf).

 Quote: But we're all agreed, are we not, that moving the highest of B to C leaves ball 1 in B and in fact leaves all the odd counting numbers in B and puts all the evens in C, producing two non-empty sets?

Absolutely.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousAntraxbgg1996bonanovaJohnPL'lanmal Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum