Infinite Balls and Jugs [solution]

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Furanku
Posts: 4
Joined: Sun Sep 20, 2009 1:38 am UTC

Re: Infinite Balls and Jugs

Postby Furanku » Sun Sep 20, 2009 7:34 pm UTC

Goplat wrote:The problem is too poorly defined to be solvable, because the wording doesn't eliminate the "wrong" method of solving it.

Deal. I'll agree there.

Just as an addendum, assuming that we have an infinite number of balls (for some reason, people are arguing that we run out of balls to put in at some point in the iteration event-line, if we end up with zero balls in the urn), if we at any point find that there are 0 balls in the urn, we can restart the entire sequence from iteration 1. Originally, at iteration one, we added balls one to 10 to the urn, and removed one. In this future case, we add balls n to n+9 to the urn, and remove ball n. The cycle starts anew, but with n as the 'starting point'. If the number of balls in the jar hits zero, it gets added to afterwards. It can only end in zero if we run out of balls to add, which is against what was stated in the question formulation.

Bravemuta
Posts: 54
Joined: Thu Oct 11, 2007 3:48 pm UTC

Re: Infinite Balls and Jugs

Postby Bravemuta » Sun Sep 20, 2009 9:16 pm UTC

Macbi wrote:
Vicious Chicken wrote:A slight variation to case A:

Each step, you add nine balls (not ten), and instead of removing the lowest numbered ball, you get out a pen and add a '0' to the end of its number. So you add 1-9, and the 1 becomes 10; second step add 11-19, and the 2 becomes 20. So, at every step, the state of the jug (the numbers on the balls it contains) will be identical to case A, but since you never remove any balls, it seems even more nonsensical to claim the jug is empty at midnight. And yet...

Thank you! I think my modifications were broken, but this one is beautiful.
jestingrabbit wrote:I would actually argue that there are an infinite number of balls in the urn at the end of this process, but the "numbers" on them don't have a finite number of digits: they'll have an arbitrary string of digits followed by an infinite string of 0's.

That's just silly..."147", "1470", "147000..." are just symbols. What if we added 5 balls each time and multiplied the lowest by 6? Since multiplying by 6 doesn't have a nice pattern in base 10, you can't tell me what the numbers at the end will look like.

Note that I don't necessarily think that the logic for the original problem is wrong, it's just that you seem to be biting a rather large bullet here: The state of the urn is identical at the end of every step (between the original and Chicken's modification), and yet they end up in different places at infinity? The bullet that you're biting is that the way we arrive at a position can affect what happens in the end. I'm still hideously confused.


Well, what happens if at first you place ball 1 inside the urn and at each iteration you take the ball out and add a 0 to the end of the number on the ball (you can write arbitrarily small, in other words, don't worry about space).

Also, considering the 1-1+1-1... series, what happens if at each odd iteration you add a ball (numbered, consecutive different balls used for each odd step) and at each even iteration you take it out, similar to Thompson's lamp ? Same argument can be made here: at the 2nth step, ball n will be removed, so the urn should be empty. I doubt that's the case, as Thompson's lamp hardly stops in one position at the end of its time.

At first, I only thought about the "classical" solution, the "nth ball removed at nth step" one. On second thought, I think a) doesn't have a solution in the same way Thompson's lamp doesn't have a solution. Otherwise, if that argument works on this problem it should work on the 1-1+1... case and, as a result, on Thompson's lamp as well. Looking at things in this light, I think b) might also be broken when thinking about whether there is a ball which has a multiple of 10 on it. It's essentially the same problem. Add one, remove one.

(Here's something I've just thought about: in Thompson's case removing and adding balls - switching lamp's status - are done at different steps. In the original "balls and jugs" problem removing and adding were done at the same step. I'm not sure, but this might be a fundamental difference. In a way, we are ensured that Thompson's case "ends" after an even number of moves, you are assured that each adding has a corresponding removing. But can you really talk about "ending" when discussing infinity?)
Last edited by Bravemuta on Mon Sep 21, 2009 3:39 pm UTC, edited 1 time in total.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs

Postby Qaanol » Mon Sep 21, 2009 3:27 am UTC

Consider this: inside the jug is a number line. Parallel to the number line is an infinite conveyor belt of cups. The cups are unlabeled, but each cup is touching exactly one integer on the number line.

Now we put balls 1-10 in the jug, and place them in the cups above the integers 1-10 on the number line, so 1 is by 1, 2 is by 2, etc. We remove the lowest-numbered ball, ball 1. Then we slide the conveyor belt one step to the left, so balls 2-10 are in cups touching integers 1-9.

At the second time step, we put balls 11-20 in the jug, and place them in the cups by the integers 10-19. That is, the cups by the first open positive integers, and again we keep the balls "in order" with respect to the number line. So ball 11 is in the cup by 10, ball 12 is by 11, etc. We remove the lowest-numbered ball, ball 2 which is by the integer 1, and slide the conveyor belt left so now ball 3 is by the integer 1.

The continues, following the rule of variant 'a', with the added condition that the balls are each in a cup affiliated with a positive integer. After step n, balls n+1 through 10n are in cups by the integers 1 through 9n.

This means, by the logic of previous posts, at midnight every ball with a number on it will have been removed, but also every cup next to a positive integer will have a ball in it. In particular, after every time step the cup by the integer 1 has a ball in it. There is no possible way for that cup to be empty after completing a time step under these rules, and no time passes except after completing a time step.

So we can be guaranteed that by reaching into the jug and taking the cup next to 1, there will be a ball in that cup. That ball will not have a number on it. But every ball that was added has a number on it. This contradicts the fact that the only balls in the jug were added during this process.

Therefore the process is impossible, or the logic of previous posts is inapplicable.
wee free kings

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs

Postby skeptical scientist » Mon Sep 21, 2009 4:12 am UTC

Qaanol wrote:This means, by the logic of previous posts, at midnight every ball with a number on it will have been removed, but also every cup next to a positive integer will have a ball in it.

No. By the logic of previous posts, each cup next to a positive integer is empty, because every ball that ended up in that cup also left the cup, so no ball resides there to the end.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
ATCG
Posts: 470
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: Infinite Balls and Jugs

Postby ATCG » Mon Sep 21, 2009 6:16 am UTC

jestingrabbit wrote:
Vicious Chicken wrote:A slight variation to case A:

Each step, you add nine balls (not ten), and instead of removing the lowest numbered ball, you get out a pen and add a '0' to the end of its number. So you add 1-9, and the 1 becomes 10; second step add 11-19, and the 2 becomes 20. So, at every step, the state of the jug (the numbers on the balls it contains) will be identical to case A, but since you never remove any balls, it seems even more nonsensical to claim the jug is empty at midnight. And yet...

I would actually argue that there are an infinite number of balls in the urn at the end of this process, but the "numbers" on them don't have a finite number of digits: they'll have an arbitrary string of digits followed by an infinite string of 0's.

How can this be? In every case relabeling results in a longer, but always finite (both in magnitude and length) natural number. Granted, we expect the relabeling process to ultimately eliminate all balls so labeled, but therein lies the contradiction (and I believe it to be a true contradiction) that makes the problem interesting.

skeptical scientist wrote:[In response to Macbi's reference to Vicious Chicken's experiment]:
. . . Also, the state of the urn at the ends of each stage is not the same as in situation a) above, because the same ball is numbered 10 at the end of stage 1, 100 at the end of stage 2, 1000 at the end of stage 100, and so on - it just has different ink on it at those stages.

I'm not yet sold on the idea that removing the lowest-numbered ball on each step empties the urn empty while relabeling the same ball eventually fills the urn. I'd like to explore the implications of this idea by proposing another experiment that matches the original experiment (a) as closely as I can manage while filling in some details.

Let's give the (super)task of adding and removing balls to Alice, and set her up in a sealed room with the initially empty urn, a clock, and two apertures in one wall of the room. The first aperture, labeled "Ball Delivery", dispenses a fresh set of ten balls at the start of each new step, each ball labeled sequentially in neat calligraphy. The second aperture, labeled "Ball Disposal", is a chute where Alice discards the balls she removes from the urn. Alice proceeds just as specified in experiment (a): She takes the ten balls awaiting her at the Ball Delivery aperture, dumps them into the urn, removes the lowest-numbered ball from the urn, and tosses it down the Ball Disposal chute. Repeat as necessary.

We and Alice are only aware of what is going on inside the sealed room. Is that enough information to deduce the final number of balls in the urn? As I understand it, the classical analysis of the problem says "yes" with an answer of zero. I expect a fair number of people would reason that Alice finds the urn empty. At this point let's let Alice pull out the pick axe she smuggled with her into the sealed room and knock a hole through the wall penetrated by the apertures. There she discovers Bob, who has been taking balls in sequence from the infinite pile of prelabeled balls available to him and feeding them to Alice at the appropriate times by way of the Ball Delivery aperture. Meanwhile, the Ball Disposal chute has been emptying into a furnace that ensures that no ball ever makes a repeat visit to the urn. I can't find much in this scenario to distinguish it from the original experiment (a) lending support to the conclusion that the urn is left empty.

So far, so good. Now let's repeat the experiment. From Alice's point of view nothing changes: She adds and removes balls from the urn exactly as before, moving balls between the urn and the wall apertures as necessary. And, to Alice, the sequence of balls she receives through the Ball Delivery aperture is indistinguishable from that of the first run. It's hard, at least for me, to think of any reason why the number of balls that Alice finds in the urn at the end of this run of the experiment should differ from the number she found after the first run. So it might be expected that when Alice looks into the urn, she again finds it empty. As before, Alice follows up by attacking the wall separating her from Bob (we let her hang on to her pick axe), but this time she finds a change in how Bob performs his duties. The first thing Alice notices is that the furnace is gone as well as the infinite pile of balls. Instead, Bob now has a button-activated ball dispenser of his own, each button press yielding him nine new blank balls.

Bob describes his work during the second experiment run as a variation on Vicious Chicken's experiment. He starts out with ten blank balls, which he hand labels 1-10 and dispenses to Alice. She returns the ball labeled 1. Rather than destroying ball 1, Bob simply appends "1" to the end of the label, transforming it into 11. He then calls up nine new balls, labels them 12-20, and dispenses all ten balls to Alice. Alice returns ball 2, Bob alters it to read "21", and the cycle continues.

Bob concludes by noting that at no time are there ever more than ten balls in his workspace. But clearly a lot more than that emerge from Bob's button-activated dispenser. Since balls are never destroyed during the second run, these other balls must be somewhere and the only other place they could be is in the urn. Could differences in final ball count really be due solely to how Bob conducts business on his side of the wall?
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

Aetius
Posts: 1099
Joined: Mon Sep 08, 2008 7:23 am UTC

Re: Infinite Balls and Jugs

Postby Aetius » Mon Sep 21, 2009 6:30 am UTC

If "there are zero balls" holds, then the following also hold:

-If the second lowest ball is removed every time, there will be 1 ball in the urn at midnight
-if the third lowest ball is removed every time, there will be 2 balls in the urn at midnight
-if the fourth lowest ball is removed every time, there will be 3 balls in the urn at midnight
-if the fifth lowest ball is removed every time, there will be 4 balls in the urn at midnight
-if the sixth lowest ball is removed every time, there will be 5 balls in the urn at midnight
-if the seventh lowest ball is removed every time, there will be 6 balls in the urn at midnight
-if the eighth lowest ball is removed every time, there will be 7 balls in the urn at midnight
-if the ninth lowest ball is removed every time, there will be 8 balls in the urn at midnight

Ultimately what the "there are zero balls" argument concludes is the number of balls in the urn depends on which ball is removed at each iteration, which ultimately cannot be the case. A ball removed is a ball removed.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Infinite Balls and Jugs

Postby Macbi » Mon Sep 21, 2009 6:46 am UTC

The example with relabelling results in the urn being empty. This violates our intuitions of Conservation of Mass, since no ball is destroyed. But the problem is inherently non-physical anyway, so why should we care? Once you formalise everything mathematically (i.e. The urn is a string of 1's and 0's, with a 1 in place n if ball n is present, and a 0 otherwise), then everything is just a set, and there is no "Conservation of Cardinality" law to get caught on. Indeed, once you've visualised everything as a set then there is no difference between relabelling and replacement at all.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Infinite Balls and Jugs

Postby Tirian » Mon Sep 21, 2009 10:52 am UTC

jestingrabbit wrote:
Vicious Chicken wrote:A slight variation to case A:

Each step, you add nine balls (not ten), and instead of removing the lowest numbered ball, you get out a pen and add a '0' to the end of its number. So you add 1-9, and the 1 becomes 10; second step add 11-19, and the 2 becomes 20. So, at every step, the state of the jug (the numbers on the balls it contains) will be identical to case A, but since you never remove any balls, it seems even more nonsensical to claim the jug is empty at midnight. And yet...


I would actually argue that there are an infinite number of balls in the urn at the end of this process, but the "numbers" on them don't have a finite number of digits: they'll have an arbitrary string of digits followed by an infinite string of 0's.


I'm not a master of the theory, but I'll claim that that is the solution to even the original case A using surreal numbers instead of Peano's system. At the end of ω steps, there are an infinite number of balls in the urn "labelled" between ω/10 and ω (including the latter but not the former).

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

Re: Infinite Balls and Jugs

Postby jestingrabbit » Mon Sep 21, 2009 11:46 am UTC

ATCG wrote:
jestingrabbit wrote:
Vicious Chicken wrote:A slight variation to case A:

Each step, you add nine balls (not ten), and instead of removing the lowest numbered ball, you get out a pen and add a '0' to the end of its number. So you add 1-9, and the 1 becomes 10; second step add 11-19, and the 2 becomes 20. So, at every step, the state of the jug (the numbers on the balls it contains) will be identical to case A, but since you never remove any balls, it seems even more nonsensical to claim the jug is empty at midnight. And yet...

I would actually argue that there are an infinite number of balls in the urn at the end of this process, but the "numbers" on them don't have a finite number of digits: they'll have an arbitrary string of digits followed by an infinite string of 0's.

How can this be?


Look at what happens to the ball initially labeled one. It goes in the jug and gets a 0 attached to its label, making it labeled 10 now. At step 10, it gets another 0 attached, making it labeled 100. At the 10nth step, another digit is put on the ball. There are an infinite number of steps at which a 0 gets added to the label, so it ends up with an infinite number of 0s in its label.

ATCG wrote: In every case relabeling results in a longer, but always finite (both in magnitude and length) natural number. Granted, we expect the relabeling process to ultimately eliminate all balls so labeled, but therein lies the contradiction (and I believe it to be a true contradiction) that makes the problem interesting.


Sure, after a finite number of steps each ball has only a finite number of digits written on it. But, by your reasoning, if I have an urn and put a ball in it at times 1-2n for all integers n, then at time 1 there are a finite number of balls in there. Noting that something is preserved after doing a finite number of steps in a process doesn't imply that this will be preserved after an infinite number of steps. You have to prove that.

ATCG wrote:Let's give the (super)task of adding and removing balls to Alice, and set her up in a sealed room with the initially empty urn, a clock, and two apertures in one wall of the room. The first aperture, labeled "Ball Delivery", dispenses a fresh set of ten balls at the start of each new step, each ball labeled sequentially in neat calligraphy. The second aperture, labeled "Ball Disposal", is a chute where Alice discards the balls she removes from the urn. Alice proceeds just as specified in experiment (a): She takes the ten balls awaiting her at the Ball Delivery aperture, dumps them into the urn, removes the lowest-numbered ball from the urn, and tosses it down the Ball Disposal chute. Repeat as necessary.

We and Alice are only aware of what is going on inside the sealed room. Is that enough information to deduce the final number of balls in the urn? As I understand it, the classical analysis of the problem says "yes" with an answer of zero. I expect a fair number of people would reason that Alice finds the urn empty. At this point let's let Alice pull out the pick axe she smuggled with her into the sealed room and knock a hole through the wall penetrated by the apertures. There she discovers Bob, who has been taking balls in sequence from the infinite pile of prelabeled balls available to him and feeding them to Alice at the appropriate times by way of the Ball Delivery aperture. Meanwhile, the Ball Disposal chute has been emptying into a furnace that ensures that no ball ever makes a repeat visit to the urn. I can't find much in this scenario to distinguish it from the original experiment (a) lending support to the conclusion that the urn is left empty.

So far, so good. Now let's repeat the experiment. From Alice's point of view nothing changes: She adds and removes balls from the urn exactly as before, moving balls between the urn and the wall apertures as necessary. And, to Alice, the sequence of balls she receives through the Ball Delivery aperture is indistinguishable from that of the first run. It's hard, at least for me, to think of any reason why the number of balls that Alice finds in the urn at the end of this run of the experiment should differ from the number she found after the first run. So it might be expected that when Alice looks into the urn, she again finds it empty. As before, Alice follows up by attacking the wall separating her from Bob (we let her hang on to her pick axe), but this time she finds a change in how Bob performs his duties. The first thing Alice notices is that the furnace is gone as well as the infinite pile of balls. Instead, Bob now has a button-activated ball dispenser of his own, each button press yielding him nine new blank balls.

Bob describes his work during the second experiment run as a variation on Vicious Chicken's experiment. He starts out with ten blank balls, which he hand labels 1-10 and dispenses to Alice. She returns the ball labeled 1. Rather than destroying ball 1, Bob simply appends "1" to the end of the label, transforming it into 11. He then calls up nine new balls, labels them 12-20, and dispenses all ten balls to Alice. Alice returns ball 2, Bob alters it to read "21", and the cycle continues.

Bob concludes by noting that at no time are there ever more than ten balls in his workspace. But clearly a lot more than that emerge from Bob's button-activated dispenser. Since balls are never destroyed during the second run, these other balls must be somewhere and the only other place they could be is in the urn. Could differences in final ball count really be due solely to how Bob conducts business on his side of the wall?


In the first situation I believe that there would be no balls in the urn.

If Bob always appends a 1 to the label on the ball he regifts, then I maintain that the urn will be filled with balls labeled with an arbitrary finite string of digits followed by an infinite string of 1s, as I suspect you thought I would say.

Alice could just as easily be described as the mouth of the urn imo. She has now knowledge regarding the identity of the balls that she deals with.

bravemuta wrote:Also, considering the 1-1+1-1... series, what happens if at each odd iteration you add a ball (numbered, consecutive different balls used for each odd step) and at each even iteration you take it out, similar to Thompson's lamp ? Same argument can be made here: at the 2nth step, ball n will be removed, so the urn should be empty. I doubt that's the case, as Thompson's lamp hardly stops in one position at the end of its time.


In case of Thompson's Lamp, there is no difference between one instance of lamp being on and another. There is a difference between the urn containing ball n and ball n+1. A correct analogy would be if we had one ball, and at odd numbered steps we put it in the urn, and at even steps we pulled it out. There, there is no sensible end state to talk about.

aetius wrote:Ultimately what the "there are zero balls" argument concludes is the number of balls in the urn depends on which ball is removed at each iteration, which ultimately cannot be the case. A ball removed is a ball removed.


By the same token, if we had a red ball and a blue ball in the urn and removed one there is only one state in which the urn can be in, as a ball removed is a ball removed. Balls that are known to be different are different and can be separately discussed.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs

Postby Qaanol » Mon Sep 21, 2009 12:07 pm UTC

In the relabeling case where you say there will be balls labeled with "an infinite string of digits", where did those balls come from? Surely, for every string of digits that ever gets put on a ball via relabeling, that same string of digits would also occur in the "original" version of the problem where the labels never change.

In either case, every ball with finite sequence of digits on it is removed. So if you claim that "infinitely-digited" balls remain in one case, why do you discount their existence in the other?

As for abstracting this away from a physical problem, we're looking at the infinite series,

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 - 1 + …

Clearly there are [imath]\aleph_0[/imath] '+1's as well as [imath]\aleph_0[/imath] '-1's. They can be put in 1-to-1 correspondence by rearrangement, which would lend itself to the 'zero remaining balls' answer. They can also be put into 9-to-1 correspondence in either direction, or any other finite ratio of integers. Or in 1-to-1 correspondence with a finite integer left over, or indeed with [imath]\aleph_0[/imath] left over, again on either side.

So we could just as easily conclude that for every ball that was put into the urn, 9 balls were removed. Let's say inside the urn is a gremlin, who does relabeling. For the first 9 time steps, after the balls are put into the urn, the gremlin erases the label on the lowest-numbered ball and relabels it with '1'. For the next 9 time steps, after the balls are put into the urn, the gremlin erases the label on the lowest-numbered ball and relabels it with '2'. This continues, so as far as we can tell from the outside, we remove every ball 9 times. Since the labels are the only method we have to distinguish the balls, there must clearly be a negative infinite number of balls in the urn at midnight.
wee free kings

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

Re: Infinite Balls and Jugs

Postby jestingrabbit » Mon Sep 21, 2009 3:19 pm UTC

Qaanol wrote:In the relabeling case where you say there will be balls labeled with "an infinite string of digits", where did those balls come from? Surely, for every string of digits that ever gets put on a ball via relabeling, that same string of digits would also occur in the "original" version of the problem where the labels never change.


The ball labeled "111..." started out as the ball that Bob first labeled 1. It acquired its extra 1s as Bob was preparing the 2nd, 12th, 112th, 1112th etc delivery of balls to Alice. We are adding digits to balls, and, because of the way that we do this, every ball gets digits added to them an infinite number of times.

Qaanol wrote:In either case, every ball with finite sequence of digits on it is removed. So if you claim that "infinitely-digited" balls remain in one case, why do you discount their existence in the other?


If we only have balls with a finite number of digits on them, and we don't change the labeling of balls in any way, there is no possible way in which infinitely labeled balls occur. You may as well ask why I discount the existence of balls labeled "Qaanol" or "Jestingrabbit".

Qaanol wrote:As for abstracting this away from a physical problem, we're looking at the infinite series,

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 - 1 + …

Clearly there are [imath]\aleph_0[/imath] '+1's as well as [imath]\aleph_0[/imath] '-1's. They can be put in 1-to-1 correspondence by rearrangement, which would lend itself to the 'zero remaining balls' answer. They can also be put into 9-to-1 correspondence in either direction, or any other finite ratio of integers. Or in 1-to-1 correspondence with a finite integer left over, or indeed with [imath]\aleph_0[/imath] left over, again on either side.


I want to make it clear that by bringing up this sequence I was in no way trying to say that there was a strong analogy that exists between how we interpret that sequence and the balls in the urn. I merely wanted to demonstate that the process by which we take a sequence to infinity directly effects outcome.

Qaanol wrote:Let's say inside the urn is a gremlin, who does relabeling. For the first 9 time steps, after the balls are put into the urn, the gremlin erases the label on the lowest-numbered ball and relabels it with '1'. For the next 9 time steps, after the balls are put into the urn, the gremlin erases the label on the lowest-numbered ball and relabels it with '2'. This continues, so as far as we can tell from the outside, we remove every ball 9 times. Since the labels are the only method we have to distinguish the balls, there must clearly be a negative infinite number of balls in the urn at midnight.


In this case, we could conclude that the balls are somehow being relabeled and that we should then, being unable to determine the fate of any one ball, acknowledge that we do not know which balls are in the urn. Absent such a gremlin, the process of seeing what happens to any one ball makes the most sense to me because it allows us to answer questions put regarding how things happen. Let me put these questions to anyone who thinks that, in the standard problem a, there are left an infinite number of balls in the urn, none of which are labeled by natural numbers: how are the balls labeled? how did they get there? did their label change? if so, how?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Bravemuta
Posts: 54
Joined: Thu Oct 11, 2007 3:48 pm UTC

Re: Infinite Balls and Jugs

Postby Bravemuta » Mon Sep 21, 2009 3:35 pm UTC

jestingrabbit wrote:
bravemuta wrote:Also, considering the 1-1+1-1... series, what happens if at each odd iteration you add a ball (numbered, consecutive different balls used for each odd step) and at each even iteration you take it out, similar to Thompson's lamp ? Same argument can be made here: at the 2nth step, ball n will be removed, so the urn should be empty. I doubt that's the case, as Thompson's lamp hardly stops in one position at the end of its time.


In case of Thompson's Lamp, there is no difference between one instance of lamp being on and another. There is a difference between the urn containing ball n and ball n+1. A correct analogy would be if we had one ball, and at odd numbered steps we put it in the urn, and at even steps we pulled it out. There, there is no sensible end state to talk about.


I hope I'm not misunderstanding what you're saying. Let's assume that the balls are made from a material that can be detected by a device within the urn. When said device finds a ball in the urn, it closes an electric circuit which feeds Thompson's Lamp. Otherwise it opens that circuit. Then, since the urn will be empty at the end of all iterations, then the lamp should be off.

I'm afraid I don't see why it matters which ball is in the urn, as long as there is a ball.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs

Postby skeptical scientist » Mon Sep 21, 2009 3:51 pm UTC

What does this circuit+lamp setup tell us? All I see is that before midnight, when there are balls, the lamp is on, and after midnight, when there are no balls, the lamp is off.

This is very different from the original Thompson's lamp setup, because the mechanism by which the lamp is turned on and off is different.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Bravemuta
Posts: 54
Joined: Thu Oct 11, 2007 3:48 pm UTC

Re: Infinite Balls and Jugs

Postby Bravemuta » Mon Sep 21, 2009 4:16 pm UTC

The only version of Thompson's Lamp I know is the one from Wikipedia. It says there that a being toggles the switch. The being's actions are determined up until two minutes have passed, so it might just as well be a device. Or, imagine that the being toggles the device by placing and extracting balls from the urn. The two setups are identical.

User avatar
jaap
Posts: 2078
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Infinite Balls and Jugs

Postby jaap » Mon Sep 21, 2009 4:26 pm UTC

skeptical scientist wrote:What does this circuit+lamp setup tell us? All I see is that before midnight, when there are balls, the lamp is on, and after midnight, when there are no balls, the lamp is off.

This is very different from the original Thompson's lamp setup, because the mechanism by which the lamp is turned on and off is different.


Try a version that detects whether the number of balls in the urn is even or odd (say off for even, on for odd). Every iteration the number of balls changes by 9, so the state of the lamp changes. This is therefore just like the original Thompson's lamp setup. The state of the lamp at the end is indeterminate, but if the urn were definitely empty the lamp would be off. Or does this just confuse the issue even more...

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs

Postby skeptical scientist » Mon Sep 21, 2009 5:03 pm UTC

No, it's still completely different. In the original, the current state of the lamp is tied to the past history (whether it was last switched off or on), so when you can't tell which occurred last, you can't tell whether it is off or on. In all of the new versions just proposed, the current state of the lamp is tied to the current state of the jug, so to tell whether it is off or on, you need only know the current state of the jug. If the current state of the jug can be known through other means - say, a ball-by-ball analysis - then the current state of the lamp can also be known.

In all of these types of scenarios, it is important not just the description of a sequence of states (there are balls numbered 32-310 in the jug) but also how things change from state to state (because balls numbered 301-309 were just added, and ball 31 was relabeled ball 310), which is why superficially similar scenarios (a lamp based on the parity of the number of balls in the jug and a lamp which is repeatedly turned on and off) can result in very different conclusions.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

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

Re: Infinite Balls and Jugs

Postby jestingrabbit » Mon Sep 21, 2009 5:06 pm UTC

Bravemuta wrote:
jestingrabbit wrote:
bravemuta wrote:Also, considering the 1-1+1-1... series, what happens if at each odd iteration you add a ball (numbered, consecutive different balls used for each odd step) and at each even iteration you take it out, similar to Thompson's lamp ? Same argument can be made here: at the 2nth step, ball n will be removed, so the urn should be empty. I doubt that's the case, as Thompson's lamp hardly stops in one position at the end of its time.


In case of Thompson's Lamp, there is no difference between one instance of lamp being on and another. There is a difference between the urn containing ball n and ball n+1. A correct analogy would be if we had one ball, and at odd numbered steps we put it in the urn, and at even steps we pulled it out. There, there is no sensible end state to talk about.


I hope I'm not misunderstanding what you're saying. Let's assume that the balls are made from a material that can be detected by a device within the urn. When said device finds a ball in the urn, it closes an electric circuit which feeds Thompson's Lamp. Otherwise it opens that circuit. Then, since the urn will be empty at the end of all iterations, then the lamp should be off.

I'm afraid I don't see why it matters which ball is in the urn, as long as there is a ball.


I take it you are refering to the situation in which we put ball 1 in, then take ball one out, then put ball 2 in etc.

Let us consider the case of a device turning the lamp on and off as you suggest. If the only rules for the device are that it alternates its position in the usual way then we have no reason to believe that the device has just turned the lamp on or just turned the lamp off. If there was some hard coded instruction like "when you get to the end of your lamp switching you must make sure that the lamp is off" then we would agree, I expect, that after the switching had been and gone, the lamp was definitely off. I claim that the fact that we can know something about the device that is doing the switching takes the place of the hard coded instruction at the end of the lamp flickering on and off.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Qaanol » Mon Sep 21, 2009 5:23 pm UTC

Also consider the process "in reverse". That is, ten minutes after midnight, I add a ball to the urn and remove ten. These balls are labeled 1-10. In 'version a', the ball I added was labeled 1, so clearly the others were labeled 2-10. This leaves the urn empty.

Five minutes after midnight, I added a ball to the urn and removed ten. The ball I added was labeled 2, and the balls I removed were labeled 11-20. Clearly balls 2-10 must be in the urn when I finish this, so balls 3-20 must have been there when I started.

At 2.5 minutes after midnight, I added a ball to the urn and removed ten. The ball I added was labeled 3, and the balls I removed were labeled 21-30. This continues.

Once again we see that n time-steps before I finish, the lowest-numbered ball in the urn was n+1. So, by the previous logic, just before I started, "at midnight" the urn was empty.

The only things I'm allowed to do are at each time step add one ball and remove ten. Clearly there cannot have been a "first time-step", because if there were then immediately following it there would have been -9 balls in the urn. (Of course we know a priori that this sequence of times does not have a "first element".) So the question becomes "How do I go from doing nothing to performing a set of discrete actions, if I cannot perform a 'first action' (ie. 'start doing something')?"

My understanding is, "I can't." Similarly, with the problem as originally stated, the question to ask is, "How can I go from performing a discrete set of actions to doing nothing, if I cannot perform a 'last action' (ie. 'stop doing things')?"
Last edited by Qaanol on Mon Sep 21, 2009 6:12 pm UTC, edited 1 time in total.
wee free kings

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

Re: Infinite Balls and Jugs [solution]

Postby jestingrabbit » Mon Sep 21, 2009 5:42 pm UTC

Okay, just finished a split and removing spoilers from stuff in here. Don't put spoilers on stuff in here. Don't put solutions in the other thread. -jr
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Infinite Balls and Jugs [solution]

Postby mike-l » Mon Sep 21, 2009 7:57 pm UTC

Wow, I posted this then went on vacation, I'm really impressed by how much discussion has followed.

I admit, I am mildly troubled by ATGC's Alice in a room/Bob outside the room modification. I will point out that from Bob's perspective, every ball enters and leaves the urn infinitely often, so he also can't say which ball is in the urn. But I can't convince myself that Bob sees the Urn as empty, only that the limit doesn't exist (which is an adequate solution). But I where I have trouble is more information causing the limit to not exist.

With the lamp setup, there's no reason limits should commute in this case, so even if the behaviour is identical to Thompson's lamp, I don't see any contradiction.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: Infinite Balls and Jugs [solution]

Postby lordatog » Mon Sep 21, 2009 8:09 pm UTC

My thinking on this problem as a whole is that there are compelling arguments for both sides. "Every ball that is added is later removed, so there cannot be anything in the urn" - check. "The number of balls in the urn strictly increases in each step" - also check. The fact that the two arguments come to opposing conclusions doesn't necessarily mean that either of them is wrong. It could instead mean that the problem as a whole is inconsistent, which is the answer I favor.

Alright, let's try yet another variation. You have an infinite number of balls, lined up in a nice row. They are numbered in order, 1, 2, 3, and so on. At each step, you put the next ten balls into the urn, remove the lowest-numbered ball from the urn, and, using any kind of method you want, choose an integer larger than the largest number in the urn. Relabel the removed ball with that number, put it in the appropriate spot in the row of balls, and add one to the number of every ball above it, including the one that previously held that number. Then, repeat. Now, every ball that is added to the urn is later removed - and every ball that is removed from the urn is later added again. How many balls are in the urn at the end of the process?

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs [solution]

Postby skeptical scientist » Mon Sep 21, 2009 9:09 pm UTC

lordatog wrote:Alright, let's try yet another variation. You have an infinite number of balls, lined up in a nice row. They are numbered in order, 1, 2, 3, and so on. At each step, you put the next ten balls into the urn, remove the lowest-numbered ball from the urn, and, using any kind of method you want, choose an integer larger than the largest number in the urn. Relabel the removed ball with that number, put it in the appropriate spot in the row of balls, and add one to the number of every ball above it, including the one that previously held that number. Then, repeat. Now, every ball that is added to the urn is later removed - and every ball that is removed from the urn is later added again. How many balls are in the urn at the end of the process?

Here the answer is undefined (according to JR and my logic), since each individual ball enters and exits the jug infinitely often. To use Macbi's above language, each individual ball performs a supertask, so not even the partial supertask axiom can be used to analyze this situation, and no conclusive analysis is possible.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Bravemuta
Posts: 54
Joined: Thu Oct 11, 2007 3:48 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Bravemuta » Mon Sep 21, 2009 9:54 pm UTC

lordatog wrote:My thinking on this problem as a whole is that there are compelling arguments for both sides. "Every ball that is added is later removed, so there cannot be anything in the urn" - check. "The number of balls in the urn strictly increases in each step" - also check. The fact that the two arguments come to opposing conclusions doesn't necessarily mean that either of them is wrong. It could instead mean that the problem as a whole is inconsistent, which is the answer I favor.

Alright, let's try yet another variation. You have an infinite number of balls, lined up in a nice row. They are numbered in order, 1, 2, 3, and so on. At each step, you put the next ten balls into the urn, remove the lowest-numbered ball from the urn, and, using any kind of method you want, choose an integer larger than the largest number in the urn. Relabel the removed ball with that number, put it in the appropriate spot in the row of balls, and add one to the number of every ball above it, including the one that previously held that number. Then, repeat. Now, every ball that is added to the urn is later removed - and every ball that is removed from the urn is later added again. How many balls are in the urn at the end of the process?


You add and remove each ball an infinite number of times, so, yeah, it looks undefined to me as well. The problem here is, that from the urn's mouth point of view, the original case and this modified one are identical. Then why are the outcomes different? Perhaps from the urn's POV the results will be identical, but from the POV of someone who knows how the selection of the balls works the result might be different. Are there any other situations where the amount of known information changes the outcome?

mike-l wrote:With the lamp setup, there's no reason limits should commute in this case, so even if the behaviour is identical to Thompson's lamp, I don't see any contradiction.


The argument I was making was the following:

In case a), where you remove the lowest ball, one can argue that because each ball has been removed at a certain step, then the urn will end up being empty. However, consider the case where the algorithm consists of adding a ball with n written on it on the (2n-1)th step and removing it on the (2n)th step. Again, if there is a ball n at the end in the jar, then it should've been removed on the 2nth step, so the jar is empty. If you connect the jar to Thompson's Lamp, then the lamp should end up being switched off, but that isn't the case, since the Lamp doesn't really stop in one state.

Now, skeptical has argued that the information needed at each step is different in the two cases (Thompson's case and the "2n-1, 2n" case). In the former, you require to know the lamp's last position to toggle the switch, while, by connecting the lamp to the urn, it becomes irrelevant, since you can just determine the state of the urn, and thus, that of the lamp's. While skeptical is right, he did not disprove my point. I only connected the lamp to the jug to try and show the fact that the two cases are analogous.

The state of the lamp can be determined by the current step's number, if it is an odd step, the lamp is off, otherwise it's on. Similarly, the state of the jug (empty or non-empty) can be determined by the current step's number, if it is an odd step, the jug is non-empty, otherwise it's empty. Or, if you only want to know the state of the lamp without numbering the steps(if the lamp is off, turn it on, otherwise turn it off), you can also have an analog in the jug's case: if the urn is non-empty, remove the ball from it and write n on a piece of paper, otherwise add a ball with n+1 on it and erase the paper).

Also, I'm considering the case where each ball added is a different one because jestingrabbit, I believe, argued that having different balls at each step changes the outcome, something I'm not convinced of.

jestingrabbit wrote:Let us consider the case of a device turning the lamp on and off as you suggest. If the only rules for the device are that it alternates its position in the usual way then we have no reason to believe that the device has just turned the lamp on or just turned the lamp off. If there was some hard coded instruction like "when you get to the end of your lamp switching you must make sure that the lamp is off" then we would agree, I expect, that after the switching had been and gone, the lamp was definitely off. I claim that the fact that we can know something about the device that is doing the switching takes the place of the hard coded instruction at the end of the lamp flickering on and off.


I'm not sure I'm understanding what you're saying, but I believe that, basically, you're arguing that by connecting the lamp to the jug the original Thompson's paradox is no longer valid, because the switching of states is done on different grounds, namely the state of the jug. In that case, the above applies. Otherwise, I'm afraid I might need you to explain your point again.

I'm starting to believe that the jug problem doesn't have a solution because it is analogous with the Lamp one. You can argue the jug is empty because all balls are removed, but you can argue it is non-empty because balls are always added. I'm not saying that either argument is wrong. They both make sense, but neither trumps the other. Rearranging the terms of the 1-1+1-1.. series changes the apparent result, but, in reality, no result is correct because there exists no result.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs [solution]

Postby skeptical scientist » Mon Sep 21, 2009 11:04 pm UTC

Bravemuta wrote:Now, skeptical has argued that the information needed at each step is different in the two cases (Thompson's case and the "2n-1, 2n" case). In the former, you require to know the lamp's last position to toggle the switch, while, by connecting the lamp to the urn, it becomes irrelevant, since you can just determine the state of the urn, and thus, that of the lamp's. While skeptical is right, he did not disprove my point. I only connected the lamp to the jug to try and show the fact that the two cases are analogous.

But they are not analogous, because in the lamp case, the switch itself is performing a supertask, and there is no way to deconstruct the setup into individual components which are not performing supertasks. In the balls+jug situation, however, while the entire system performs a supertask, the individual balls do not, and so a component-wise analysis is possible and completely explains the scenario. Apart from the superficial similarity that in both cases you have a lamp turning on and off an infinite number of times, the two setups are very different, because the mechanism controlling the lamp comes to a limit in the scenario with the balls, but not in the scenario with the switch.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Infinite Balls and Jugs [solution]

Postby mike-l » Mon Sep 21, 2009 11:33 pm UTC

What I'm saying is there is no reason that Lamp (lim Urn (t) ) = lim Lamp (Urn (t)), so I don't see any issue with the LHS being Off and the RHS being undefined (Defining all terms in the way that makes sense).
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
ATCG
Posts: 470
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: Infinite Balls and Jugs

Postby ATCG » Tue Sep 22, 2009 12:37 am UTC

jestingrabbit wrote:
ATCG wrote:
jestingrabbit wrote:I would actually argue that there are an infinite number of balls in the urn at the end of this process, but the "numbers" on them don't have a finite number of digits: they'll have an arbitrary string of digits followed by an infinite string of 0's.
How can this be?
Look at what happens to the ball initially labeled one. It goes in the jug and gets a 0 attached to its label, making it labeled 10 now. At step 10, it gets another 0 attached, making it labeled 100. At the 10nth step, another digit is put on the ball. There are an infinite number of steps at which a 0 gets added to the label, so it ends up with an infinite number of 0s in its label.

Your premise that "There are an infinite number of steps at which a 0 gets added to the label" is certainly true, but I don't see that "so it ends up with an infinite number of 0s in its label" follows as a conclusion.

Let's say we set out on the supertask of constructing the set of natural numbers by starting with the base element 0 and repeatedly adding 1 to form new elements to add to the set. Clearly no finite number of repetitions will complete the set - an infinite number is required. So by the time we're done we will have added 1 to 0 an infinite number of times. Intuitively, it would seem that our completed set must contain an infinite element. Yet we know that the set of natural numbers, while infinite in size, contains nothing but finite elements.

The same principle applies here. We start out with the label "1", then move on to "10", "100", and so on an infinite number of times resulting in an infinite number of labels. We see that the length of the first label is 1, the second 2, and so on through the natural numbers. Even with an infinite number of labels, we never encounter a label of infinite length.

jestingrabbit wrote:
ATCG wrote: In every case relabeling results in a longer, but always finite (both in magnitude and length) natural number. Granted, we expect the relabeling process to ultimately eliminate all balls so labeled, but therein lies the contradiction (and I believe it to be a true contradiction) that makes the problem interesting.
Sure, after a finite number of steps each ball has only a finite number of digits written on it.

And, as noted above, after an infinite number of steps as well.

jestingrabbit wrote:If Bob always appends a 1 to the label on the ball he regifts, then I maintain that the urn will be filled with balls labeled with an arbitrary finite string of digits followed by an infinite string of 1s, as I suspect you thought I would say.

Actually, I was hoping (and hope yet) to persuade you that nothing but Grade A, 100%-certified natural numbers ever appear as labels, regardless of how Bob goes about doing his job. But more than that, I'd like to show this leading inevitability to a genuine contradiction, which I see as resulting from an inconsistency in the unspoken premises taken on in framing and working the problem.

jestingrabbit wrote:Alice could just as easily be described as the mouth of the urn imo. She has no knowledge regarding the identity of the balls that she deals with.

I'm comfortable with such a description. Alice and Bob may both be viewed as nothing more than automata carrying out a fixed procedure. What I regard as important is the traffic at the mouth of the urn as characterized by the labels entering or leaving it. I would contend that the substrate bearing a label is unimportant beyond requiring that there be one substrate for each label and vice versa. Taken this way, the sequence of events at the mouth of the urn is identical between the two runs of the experiment.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Qaanol » Tue Sep 22, 2009 12:47 am UTC

skeptical scientist wrote:But they are not analogous, because in the lamp case, the switch itself is performing a supertask, and there is no way to deconstruct the setup into individual components which are not performing supertasks. In the balls+jug situation, however, while the entire system performs a supertask, the individual balls do not, and so a component-wise analysis is possible and completely explains the scenario. Apart from the superficial similarity that in both cases you have a lamp turning on and off an infinite number of times, the two setups are very different, because the mechanism controlling the lamp comes to a limit in the scenario with the balls, but not in the scenario with the switch.

What if we make them analogous?

We have a switch, and we toggle it at 11:50, 11:55, 11:57:30, etc.

The switch has two outputs. One goes to the room on the right and changes the state of Thompson's Lamp. The other goes to the room on the left and performs "Task a: place the next ten sequential balls into the urn, and remove the lowest-numbered ball from the urn."

These rooms are completely isolated. No information comes out of them: not from one room to the other, nor from either room to the switch room. Information only travels from the switch into the two rooms.

We are interested in the state of the switch at midnight if:

i) The machines in both rooms are functioning properly.
ii) Thompson's Lamp is disconnected from the switch, but the ball-and-urn device functions properly.
iii) The ball-and-urn device is disconnected, but Thompson's lamp works.
iv) Neither machine does anything.

And of course in each case, we at the switch do not and cannot know which (if either) machine or machines are actually connected to the switch.
wee free kings

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs

Postby skeptical scientist » Tue Sep 22, 2009 12:56 am UTC

ATCG wrote:Let's say we set out on the supertask of constructing the set of natural numbers by starting with the base element 0 and repeatedly adding 1 to form new elements to add to the set. Clearly no finite number of repetitions will complete the set - an infinite number is required. So by the time we're done we will have added 1 to 0 an infinite number of times. Intuitively, it would seem that our completed set must contain an infinite element. Yet we know that the set of natural numbers, while infinite in size, contains nothing but finite elements.

You aren't repeatedly adding one to a single, fixed element. You are repeatedly taking the largest element of the set, incrementing it, and adding the new number to the set. If you repeatedly incremented a single number and asked what happened to that number, you would be doing something very different from constructing the naturals.

I really don't see how you can argue that taking a one and writing infinitely many zeros after it doesn't result in a one with an infinite sequence of zeros after it.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
ATCG
Posts: 470
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: Infinite Balls and Jugs

Postby ATCG » Tue Sep 22, 2009 3:36 am UTC

skeptical scientist wrote:I really don't see how you can argue that taking a one and writing infinitely many zeros after it doesn't result in a one with an infinite sequence of zeros after it.

I quite agree. If I write a one and follow it with infinitely many zeros, then I wind up with precisely that: a one followed by an infinite sequence of zeros. What I would claim is that taking a one and writing infinitely many zeros after it is something that never happens.

skeptical scientist wrote:
ATCG wrote:Let's say we set out on the supertask of constructing the set of natural numbers by starting with the base element 0 and repeatedly adding 1 to form new elements to add to the set. Clearly no finite number of repetitions will complete the set - an infinite number is required. So by the time we're done we will have added 1 to 0 an infinite number of times. Intuitively, it would seem that our completed set must contain an infinite element. Yet we know that the set of natural numbers, while infinite in size, contains nothing but finite elements.

You aren't repeatedly adding one to a single, fixed element. You are repeatedly taking the largest element of the set, incrementing it, and adding the new number to the set. If you repeatedly incremented a single number and asked what happened to that number, you would be doing something very different from constructing the naturals.

I can't help but think that it is attempts to combine "infinite" and "process" in the same discussion that lead to trouble. So let me back up and try again from a different angle that avoids the notion of process and, I hope, stands on a little firmer ground.

Consider the set of steps performed prior to midnight. Put the elements of this set into one-to-one correspondence with the elements of the set of naturals N so that the step taking place at time midnight-2-n(10 minutes) <= t < midnight-2-(n+1)(10 minutes) pairs with n for every n in N. Relabeling occurs exactly once during each and every step and at no other time - so we've got all the relabelings pretty well surrounded. Every relabeling leaves the relabeled ball marked with the decimal numeral of 10(n+1) (n being the index of the step in which the relabeling takes place). Every n in N is finite, therefore every label resulting from relabeling is a string of finite length, as claimed.

As long as I'm at it, let me conclude with a second, informal argument, starting with a resurrected argument from Qaanol:
Qaanol wrote:In the relabeling case where you say there will be balls labeled with "an infinite string of digits", where did those balls come from? Surely, for every string of digits that ever gets put on a ball via relabeling, that same string of digits would also occur in the "original" version of the problem where the labels never change.
Indeed, but all the same let's abandon the idea of appending zeros (or ones) to existing labels. In the second run of the Alice/Bob experiment we had Bob touching up each recycled ball by adding a new trailing digit, hand labeling nine newly dispensed blank balls, and then sending the collection of ten on to Alice. Instead, Bob can completely remove the existing label from the recycled ball (some sort of 3M™ Post-it® product might come in handy here) and simply treat all ten balls as blanks to be labeled. It's hard to see how labels of infinite length could arise in this case.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs

Postby skeptical scientist » Tue Sep 22, 2009 3:42 am UTC

ATCG wrote:Indeed, but all the same let's abandon the idea of appending zeros (or ones) to existing labels. In the second run of the Alice/Bob experiment we had Bob touching up each recycled ball by adding a new trailing digit, hand labeling nine newly dispensed blank balls, and then sending the collection of ten on to Alice. Instead, Bob can completely remove the existing label from the recycled ball (some sort of 3M™ Post-it® product might come in handy here) and simply treat all ten balls as blanks to be labeled. It's hard to see how labels of infinite length could arise in this case.

I agree. JestingRabbit's and my claims of a label of infinite length were specifically for a situation where new labels were obtained by appending a single character to an old label, and this procedure was repeated infinitely often.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

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

Re: Infinite Balls and Jugs [solution]

Postby jestingrabbit » Tue Sep 22, 2009 9:41 am UTC

I've been having a bit of a think regarding the Vicious Chicken/ATCG modifications. I think they're subtly different, and I've got some of the disposition of the endstate of ATCG's variation wrong.

My analysis, once again, focuses on what happens to each individual ball, and, moreover, I'm going to focus on what happens to each "potential digit position", or pdp, on each individual ball too. The ball that initially gets a 1 written on it is generic (more or less), so I'll focus on it and its pdps. I hope we can all agree that the path of this ball is as follows.

  1. Bob takes a ball, writes a 1 on it in the first pdp, and moves it through the delivery hole.
  2. Alice takes the ball, puts it in the urn.
  3. Alice takes it out of the urn and puts it through the disposals hole.
  4. Bob takes it and writes a 1 on it in the second pdp, and moves it through the delivery hole.
  5. Alice takes the ball, puts it in the urn.
  6. Alice takes it out of the urn and puts it through the disposals hole.
  7. Bob takes it, writes a 1 on it in the third pdp, and moves it through the delivery hole.
  8. Alice takes the ball, puts it in the urn.
  9. Alice takes it out of the urn and puts it through the disposals hole.
  10. etc.

Lets accept this relabeling of steps for the discussion that follows.

To begin with, for every n, there is a step 3n-2, and on this step the nth pdp gets a 1 written in it. I conclude that every pdp has a 1 written in it.

But, to conclude, where is the ball? Every step of the form 3n-1 is followed by 3n is followed by a 3n+2 etc, so I contend that it is a true Thompson's Lamp analog. It is neither in the urn, nor not in the urn at the end. Likewise, it is neither on Bob's side of the wall nor Alice's.

So, I contend that the label on the ball is an infinite string of 1s (with a start but no end), and it has no sensible position that can be assigned it. This is not to say that it has disappeared or something else, it exists, with the label described, but its position isn't something about which a consistent account can be formed.

Vicious Chicken might be relabeling the balls without removing them from the urn, in which case I say the balls stay in the urn.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Infinite Balls and Jugs [solution]

Postby Macbi » Tue Sep 22, 2009 3:51 pm UTC

So imagine the case where we put in ball 1. Then we take it out and put in ball 2. Then we take out ball 2 and put in ball 3, and so on. No ball performs a supertask, they all leave the urn and are not put back in, so we can concluded that the urn is empty at the end. But then someone comes along and says "Consider the variable 'number of balls in the urn', that remains constant at 1; It doesn't do a supertask either, so we can conclude that the urn ends up with one ball in it, which contradicts the previous result, so your Partial Supertask Axiom doesn't work!"
At this point we have to say something like "The variable 'number of balls in the urn' isn't a fundamental dimension of the statespace: it's something you compute from the other variables which are fundamental, like 'ball 1 is in the urn'. The PSA only applies to fundamental variables, and then you compute the rest of your variables from where they end up."

The problem is that when you get messy complications, it becomes difficult to decide how to mathematically represent your state space, and therefore impossible to decide which variables are fundamental. Someone earlier in the thread said something like "suppose we keep track of each individual atom of ink" which seems silly, but could be the only way of talking about these things. I approve of JR's example above, of keeping track of each pdp.

I think we're running dangerously close to philosophical questions like "Are two unlabeled balls identical (in the same way as say the two 3's in the factorisation of 18 are identical), or can we tell them apart (in the way that, like, enables us to juggle)?" That is to say, should the way of representing unlabeled balls look like: "there are thirty four unlabeled balls in the box"
OR should it look like: "unlabeled ball A is in the box, unlabeled ball B is not in the box, unlabeled ball C is in the box..."
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
ATCG
Posts: 470
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: Infinite Balls and Jugs [solution]

Postby ATCG » Tue Sep 22, 2009 4:56 pm UTC

jestingrabbit wrote:Vicious Chicken might be relabeling the balls without removing them from the urn, in which case I say the balls stay in the urn.

Then let's stick with Vicious Chicken relabeling balls inside the urn since that fixes their location. But now what if we change the relabeling procedure: Instead of appending a zero to the existing label, the relabeler reads the label as a natural number, multiplies that number by 10, and replaces the existing label with the result. (To me this seems like trading six for half a dozen, but what the heck. I just want to bypass the whole infinite-string-of-digits debate.)

If, in fact, there can never be a label inside the urn that can't be read as a natural number, then surely the urn must be left empty. And if balls never leave the urn, then surely the urn must be left full. How do we account for this contradiction?
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs [solution]

Postby skeptical scientist » Tue Sep 22, 2009 6:05 pm UTC

The balls are there, it's only the labels that are uncertain. If the labels are removed and a new label added, then the balls are blank (by the same logic as before), since every label that is attached is later removed. If the labels are changes by adding a 0 at the end, we're again at the infinite string of zeros solution. And if the labels are a digital display that can be modified, or similar, then we have a thompson's-lamp-style issue where there is no clear end-state, because a single object changes states infinitely often without coming to a limit.

Macbi wrote:At this point we have to say something like "The variable 'number of balls in the urn' isn't a fundamental dimension of the statespace: it's something you compute from the other variables which are fundamental, like 'ball 1 is in the urn'. The PSA only applies to fundamental variables, and then you compute the rest of your variables from where they end up."

Exactly. So far all the examples have been such that one set of variable is clearly natural, and other sets are artificial, so the PSA seems to work just fine. If anyone has an example of a supertask where there are two equally valid, equally natural sets of variables that lead to different conclusions using the PSA, then I would accept that such a supertask is as impossible to analyze as Thompson's lamp, and it may be that such supertasks can be described. But for the balls-and-jug puzzle, I think the PSA works perfectly well, and I find the explanation it provides completely satisfying.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Infinite Balls and Jugs [solution]

Postby Macbi » Tue Sep 22, 2009 6:13 pm UTC

I've got a spectrum of scenarios that I think are very hard to answer consistently. In all of them we start with an empty urn, an infinite line of identical blank balls outside the urn, a label for each positive integer (also outside the urn), and an incinerator (outside the urn):

Alpha) At the first time-step we take nine balls, stick on the labels from one to nine and put them in the urn. We then strip label 1 from its ball and incinerate this label, we then take label 10 from the line and stick it to this ball, keeping the ball in the urn all the time. The next step we continue as you'd expect, adding 11 to 19, and turning 2 to 20.

Beta) At the first time-step we take nine balls, stick on the labels from one to nine and put them in the urn. We then strip label 1 from its ball, take it out of the urn, and stick it to a new blank ball, then we incinerate both the ball and the label. We then take label 10 from the line and stick it to the blank ball now in the urn (which has never left the urn). The next step we continue as you'd expect, adding 11 to 19, and turning 2 to 20.(This is the same as alpha, but now we stick each of the labels we're going to incinerate to a new blank ball before we incinerate them)

Gamma) At the first time-step we take nine balls, stick on the labels from one to nine and put them in the urn. We then get label number 10 and stick it to a new blank ball and put this in the urn. Keeping both balls inside the urn we peel labels 1 and 10 off their balls and put them back on the other ball. We then take out the ball now labeled with 1 (keeping its label on it), and incinerate it. At the next step we continue as you'd expect, adding 11 to 19, and with the ball originally labeled as 2 ending up labeled 20. (This is the same as beta, but now we do some of the sticking in the urn rather than outside it)

Delta) At the first time-step we take nine balls, stick on the labels from one to nine and put them in the urn. We then get label number 10 and stick it to a new blank ball and put this in the urn. I hold the balls labeled 1 and 10 in the urn and use my magical powers to teleport the balls to each other's position keeping the labels in the same position. That is, the two balls now have each other's label. We then take out the ball now labeled with 1 (keeping its label) on it, and incinerate it. At the next step we continue as you'd expect, adding 11 to 19, and with the ball originally labeled as 2 ending up labeled 20. (This is the same as gamma except we swap the labels on the balls by teleporting the balls, rather than moving the labels)

Epsilon) At the first time-step we take nine balls, stick on the labels from one to nine and put them in the urn. We then get label number 10 and stick it to a new blank ball and put this in the urn. We then take out the ball labeled with 1 (keeping its label on it), and incinerate it. At the next step we continue as you'd expect, adding 11 to 19, and with the ball originally labeled as 2 replaced with one labeled 20. (This is the same as delta, but we don't bother swapping two identical balls)

We already know that if you think that the urn is empty at the the end of alpha then you have to explain where they went. If you think that the urn is full at the the end of epsilon then you have to name one of the balls in the urn. If you think that alpha ends up full but epsilon ends up empty, then between which pair of scenarios does the flip occur? I'm guessing that most people will say between delta and epsilon, but see here. What if I replace "ball" with "electron" and "label" with "numbered electron container"?

What's really going to bake your noodle later on, is that the labels do the same thing in every case, so how can moving the balls around affect them? Might moving the air in the urn also affects what happens? How could we tell?
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs [solution]

Postby skeptical scientist » Tue Sep 22, 2009 6:49 pm UTC

Macbi wrote:We already know that if you think that the urn is empty at the the end of alpha then you have to explain where they went. If you think that the urn is full at the the end of epsilon then you have to name one of the balls in the urn. If you think that alpha ends up full but epsilon ends up empty, then between which pair of scenarios does the flip occur? I'm guessing that most people will say between delta and epsilon,

Yes, exactly. I see no inconsistency so far.
Macbi wrote: but see here. What if I replace "ball" with "electron" and "label" with "numbered electron container"?

In that case, I have no idea. Balls are distinguishable, whether labeled or not, whether identical or not, indistinguishability of electrons notwithstanding. I lack the intuitive understanding of the way electrons behave necessary to make any reasonable guesses as to what would happen if you replaced balls with electrons, but I see no inconsistency in imagining that the result of an experiment performed with distinguishable objects may be different from the result of the same experiment performed with indistinguishable ones.

Macbi wrote:What's really going to bake your noodle later on, is that the labels do the same thing in every case, so how can moving the balls around affect them? Might moving the air in the urn also affects what happens? How could we tell?

This isn't going to bake my noodle at all, since it's simplicity itself: every label is incinerated in every scenario, so moving the balls around doesn't affect them at all. In scenarios alpha through delta, all the balls end up blank.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Infinite Balls and Jugs [solution]

Postby Macbi » Tue Sep 22, 2009 7:22 pm UTC

skeptical scientist wrote:If anyone has an example of a supertask where there are two equally valid, equally natural sets of variables that lead to different conclusions using the PSA, then I would accept that such a supertask is as impossible to analyze as Thompson's lamp, and it may be that such supertasks can be described. But for the balls-and-jug puzzle, I think the PSA works perfectly well, and I find the explanation it provides completely satisfying.
I'm not sure if there is such and example, but I'm working on finding one, I think Qaanol came close with the conveyer belt example, but I haven't got a good scenario yet.

skeptical scientist wrote:In that case, I have no idea. Balls are distinguishable, whether labeled or not, whether identical or not, indistinguishability of electrons notwithstanding. I lack the intuitive understanding of the way electrons behave necessary to make any reasonable guesses as to what would happen if you replaced balls with electrons, but I see no inconsistency in imagining that the result of an experiment performed with distinguishable objects may be different from the result of the same experiment performed with indistinguishable ones.
Balls are made from fundamental particles, if the particles can be identical then we can make two balls that are identical (besides, we're working in maths now; we can define them to be identical). I don't believe that "instantaneously swapping two identical things" is even an action, so currently I believe that alpha and epsilon end up with the same outcome, and in particular that the urn ends up empty both times. No electron containers, no electrons (there aren't electrons just floating loose in the urn). Similarly, if there are no labels then there are no balls.
I think the proper way to represent identical balls is either as a single fundamental variable: "amount of balls in urn", or as a variable calculated from knowing which labels are in the urn (since each label has a ball). The "amount of balls in urn" variable does a supertask (it goes to infinity), the second variable can be calculated to be 0 by considering the labels.
    Indigo is a lie.
    Which idiot decided that websites can't go within 4cm of the edge of the screen?
    There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Qaanol » Tue Sep 22, 2009 11:50 pm UTC

Just as we defined the balls to be indistinguishable except for the labels, I also define "ball count" to be a conserved property. That is, balls cannot spontaneously pop into or out of existence (I would simply say, "each ball has mass M", but that would entail performing infinite work in infinitesimal time, which is clearly nonphysical.)

Alice has 2 urns with infinite capacity, 1 box that can hold up to 10 balls, 1 cup that can hold up to 1 ball, and an infinite line of balls labeled 2-100, 102-200, 202-300, namely all the positive integers not congruent to 1 modulo 100. The cup initially contains the ball labeled '1'.

The "urn-urn-box-cup" system initially contains only the 1-ball.

Alice takes the ball from the cup and the first 9 balls from the line, so balls 1-10. She puts these into urn P, and removes the lowest-numbered ball, which she puts into the box.

At the next time-step, she takes the next 10 balls from the line, puts them into urn P, and removes the lowest-numbered ball, which she puts into the box.

She continues taking balls from the line until balls 1-10 are in the box (and 11-100 are in urn P). Now she takes the 10 balls from the box, puts them into urn Q, and removes the lowest-numbered ball, ball 1, which she puts into the cup. She edits the label on the ball in the cup so it shows the lowest positive integer she has not yet seen, in this case 101.

At the next time-step, she takes the next 9 balls from the line (balls 102-110), and the ball from the cup (101), and puts them into urn P, then removes the lowest and puts it into the box.

This continues "until midnight". At every time-step, urn P gets the next 10 balls added to it and the lowest removed. At every 10th time-step, the same thing happens to urn Q.

Now, you would say "each ball performs a supertask", but hold your tongue. The labels are the only way to distinguish the balls. Bob stands on the mouth of urn P and observes the balls going into and coming out of urn P. Maybe Bob actually takes the balls from Alice and puts them into the urn himself, and then takes out the lowest one and hands it to Alice. In any event, Bob sees "the next ten go in, and the lowest one comes out". Bob sees each ball perform a simple task. Every ball goes in exactly once, and every ball come out exactly once. Bob sees that for any integer N, there comes a time *strictly before midnight* at which ball N leaves urn P and never returns.

Similarly from the mouth of urn Q, every ball enters exactly once, and leaves exactly once, strictly before midnight. And of course Alice sees that every label number gets edited to something else, exactly once, prior to midnight. The box and cup together can hold no more than 11 balls. No balls can ever be "in limbo" between states—a ball is either in urn P, urn Q, the box, the cup, or the line. Furthermore, no balls ever leave the urn-urn-box-cup system. But an infinite number of balls enter that system.

Bob says, "Urn P is empty. It was empty when we started. Every ball that went in had a positive integer label. Every positive integer label went in exactly once, attached to a ball. Every positive integer label came out exactly once, attached to a ball. No labels changed inside. In fact, I kept the balls sorted by label inside the urn, so there wasn't any funny-business at all."

Whoever is by the mouth of urn Q says the same about it.

What's more, Alice sees that the line of balls is empty as well. "Every ball in the line had a distinct positive integer label. For each positive integer, there came a time strictly before midnight when all the balls in the line had a number larger than that on their label. So no balls with positive integer labels are in the line. But that was the only type of ball in the line, so there aren't any at all."
wee free kings

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Infinite Balls and Jugs [solution]

Postby skeptical scientist » Tue Sep 22, 2009 11:55 pm UTC

When I said that balls are distinguishable even if identical, I meant that they are classical objects, rather than quantum objects. Classical objects, even if identical, can be distinguished by simply following the path each one takes. This is possible for classical objects, but not quantum objects, because we know that quantum objects (thanks to the two slit experiment) don't take single paths.

In any case, I'm going to give up trying to argue this, because it's all meaningless anyways. We're trying to predict the outcome of an experiment which is impossible in practice, so there's no way of deciding who is right and who is wrong, just how different people think about infinity and infinite tasks. Clearly all we have concluded is that my conception of what happens in a supertask is different from yours, and since supertasks (at least of the type we are describing) are impossible, there's no objective way to decide whose conception is better.

If you want to argue and want me to defend my claim that my conception is internally consistent, I'll be happy to do so, but I no longer believe it is "right" in any meaningful sense.

I do, however, find it interesting that according to my conception, the jug still ends up empty in puzzle c), when the balls are removed at random, but that this ceases to be true if the balls are added at a sufficiently quickly increasing rate.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Infinite Balls and Jugs [solution]

Postby Qaanol » Wed Sep 23, 2009 12:03 am UTC

skeptical scientist wrote:supertasks (at least of the type we are describing) are impossible

Quoted for truth.

Thanks for the mind-stretching discussion.
wee free kings


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests