|
||||||||||||||||||||||||
|
Title: Re: Chew on This Post by aero_guy on Apr 2nd, 2003, 11:47am Argument 1 is correct, and the lowest numbered ball is numbered infinity, but half the infinity of the total number of balls. There are people here who know much more about the concept than I, but I am pretty sure that is the answer. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by wowbagger on Apr 2nd, 2003, 12:05pm I agree that argument 1 is correct. But let's hear what Icarus has to say. I'm sure he just has to comment on this one! edited to make subject agree with new thread title |
||||||||||||||||||||||||
|
Title: Impish Pixie Post by THUDandBLUNDER on Apr 2nd, 2003, 1:54pm on 04/02/03 at 11:47:47, aero_guy wrote:
And the second-lowest ball will be numbered infinity+1, I presume. ??? At every stage, only balls with finite numbers on them are placed in the bucket. |
||||||||||||||||||||||||
|
Title: Re: Chew on This Post by LZJ on Apr 2nd, 2003, 4:59pm The rate at which something reaches infinity counts too: for example, as x => infinity, e^x reaches infinity much faster than x does, and so does 2x. (Sorry for stating the obvious) |
||||||||||||||||||||||||
|
Title: Re: Chew on This Post by Icarus on Apr 2nd, 2003, 7:14pm on 04/02/03 at 12:05:22, wowbagger wrote:
Of course! But I am going let you ponder it awhile longer before putting in my two cents. I will give the following hint: [hide] What sets contain all numbers on balls in the final bucket? The intersection of all such sets is obviously the answer, since the answer is one of these sets.[/hide] As you might expect from two such rational sounding approaches giving different answers, the true answer reveals a nasty (ie anti-intuitive) fact about infinite processes. |
||||||||||||||||||||||||
|
Title: Re: Chew on This Post by SWF on Apr 2nd, 2003, 8:19pm on 04/02/03 at 12:05:22, wowbagger wrote:
I thought you meant Icarus would comment on the irrelevant subject for this thread. I'll take care of this one... THUDandBLUNDER, please use a descriptive title when you start a thread. As a member, you can go back and edit the thread title, or maybe change the question so it fits the title. For example, make the balls, numbered gumballs being throw into a giant gumball machine. Posting of new puzzles is always welcome, but this one probably should have been put in the easy section. |
||||||||||||||||||||||||
|
Title: Impish Pixie Post by THUDandBLUNDER on Apr 2nd, 2003, 8:57pm > "THUDandBLUNDER, please use a descriptive title when you start a thread." OK, I will do so in future. > "As a member, you can go back and edit the thread title..." Unfortunately, this does not rename the titles of the replies. > "Posting of new puzzles is always welcome, but this one probably should have been put in the easy section." If you think this puzzle belongs in the Easy section I would say that you are doubly mistaken. What is your Easy answer and the simple reasoning behind it? Now explain, so that an educated layperson can understand, what is wrong with the other answer(s). In my opinion, that's what makes this puzzle 'hard'. Getting the correct answer may not be hard, but being sure that it is right is surely not Easy, or even Relatively Medium. ;) |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by LZJ on Apr 3rd, 2003, 5:29am Just to end it off, Increase = 2 * t Decrease = 1 * t Net change = (2 - 1) * t = t Therefore, as t => infinity, net change => infinity. Argument 1 is correct, but I think argument 2 is flawed (of course, I don't know much about infinities: perhaps Icarus would care to elucidate?) |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 3rd, 2003, 5:55am > "perhaps Icarus would care to elucidate?" Why not stick around for Daedulus while we are at it? After all, (unlike Icarus) we know for sure that Daedulus is on his way. ;D As for Argument 1 being correct, I believe that SWF will either agree with you or be able to point out your mistake so that you can easily understand it. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 3rd, 2003, 5:28pm on 04/03/03 at 05:55:25, THUDandBLUNDER wrote:
??? I'm afraid I don't understand this remark. How do we know "that Daedalus is on his way"? They are expecting me to reply because when it comes to infinities, I have an infinite amount of bombast. ;) This is a good puzzle. It even fooled me at first glance, and I have enough experience with this that I should have known better. (I will say in my defense that it was only at first glance that I was fooled.) I am still holding off yet on giving my analysis. And SWF is mistaken - this one definitely belongs in the hard section. Your only mistake was not giving it a good name from the start - a very common newbie blunder you have already corrected. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 3rd, 2003, 9:56pm > '"I'm afraid I don't understand this remark. How do we know "that Daedalus is on his way"?' I merely meant that your mythical namesake died when he flew too close to the sun - unlike his father, Daedalus . |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by wowbagger on Apr 4th, 2003, 7:30am on 04/03/03 at 21:56:29, THUDandBLUNDER wrote:
I'm sure Icarus is aware of who his father is/was. ;) Not sure about Daedalus being on his way either, though. Back to the riddle: Based on Icarus's hint, I came up with the following: [hide]Let Si be the set of the natural numbers without the first i numbers, so ("-" denotes set difference) Si = N - {1,2,3,...,i}. As all natural numbers will eventually be put in the bucket, and all will somewhen be taken out again, the set S of all finally remaining numbers has to be a subset of Si for all i. On the other hand, it can't be a superset of S0 = N. This is why - as Icarus pointed out - the set S is the intersection of all Si: S = interi=0oo Si To me as a person without set-theoretical background, the set S seems to be empty. So much for my initial answer! To make sure I'm on the right track, consider the following alteration: The impish pixie takes that ball back out which has the lowest odd number. So we add 1, 2, take out 1, add 3, 4, take out 3, add 5, 6, ... This should lead to a set S consisting of all even natural numbers - and infinitely many balls in the bucket! [/hide] What do you all think of this? |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Ulkesh on Apr 4th, 2003, 11:29am Didn't Cantor say that two sets are equal in magnitude if their elements can be put into one-to-one correspondence with each other? wowbagger's alternative wording of the original problem is equivalent to it, I think. And, the set of integers can be put in one-to-one correspondence with the set of even integers. Doesn't this make the answer [hide] zero [/hide]? |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by cho on Apr 4th, 2003, 12:52pm Let's throw in one more variation. Throw in 2 balls and take the highest numbered ball out. 1,2 in; 2 out; 2,3 in, 3 out; 3,4 in, 4 out... To summarize: Infinity-infinity=infinity, according to argument one. infinity-infinity=0, according to argument two. infinity-infinity=1/2 infinity, leaving the even balls in. infinity-infinity=infinity-1, if the balls that come out go back in. And if you think an infinitely long discussion of infinity would be infinitely pointless and impractical, has anybody heard the news about a problem with quantum theories. If space and time are quantized, then space should be like a foam and photons passing through it will take different paths and slightly different speeds. That should make light traveling vast distances blurry, but Hubble photos of galaxies 5 billion light years away are razor sharp. So no quanta. If no quanta then time and space can be divided into infinitely small units. That should mean that the Big Bang began with an infinitely hot universe in an infinitely small space. Not possible. So we'd better figure out this infinity quickly or the whole universe may be an impossibility and cease to exist. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 4th, 2003, 1:07pm Ulkesh, I believe Wowbagger's conclusion is correct. As I see it, if after minute #N I take out ball #N there will be no balls left. If instead I take out ball #2N (or, like Wowbagger, 2N-1) there will be an infinite number of balls left. And for any natural number k, if I take out ball #N+k there will be k balls left. :o While it is true that the transfinite sets that you mentioned are the same size, the answer also depends very much on the ordering of the balls, strange though that may seem. There are in fact three schools of thought: an infinite number of balls, no balls, or an indeterminate number of balls. (Balls, no balls, or bollocks, you might say.) ;) (Warning: discussions of this puzzle often generate more heat than light.) |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 4th, 2003, 4:11pm Thanks, wowbagger! I was afraid nobody would get my hints that they really need to rethink the answer. My comments: A technical way of approaching this problem is as a limit of sets: Denote [langle]n, k[rangle] = {m | m is an integer and n <= m <= k}. [langle]n[rangle] = {m | m is an integer and n <= m}. After the nth turn, the set of numbers corresponding to balls in the basket is [langle]n+1, 2n[rangle]. The problem essentially asks, what is Limn[to][subinfty] [langle]n+1, 2n[rangle] ? How do you take the limit of a sequence of sets? The accepted method is this: Given a sequence {Sn} of sets, define Limsup Sn = [bigcap]k=1[supinfty] [bigcup]n=k[supinfty] Sn Liminf Sn = [bigcup]k=1[supinfty] [bigcap]n=k[supinfty] Sn (The Unions in the Limsup definition contain every Sk for k >=n, so they "ought" to also contain any sort of limit of these sets. Since they all contain it, so does their intersection. So Limsup Sn is a "biggest possible" limit set. Similarly Liminf Sn is a "smallest possible" limit set.) Define Lim Sn = A, if Limsup Sn = Liminf Sn = A. Now, [bigcup]n=k[supinfty] [langle]n+1, 2n[rangle] = [langle]k+1[rangle], and [bigcap]n=k[supinfty] [langle]k+1[rangle] = [emptyset]. So, Limsup [langle]n+1,2n[rangle] = [emptyset]. The Liminf is always a subset of Limsup, so it must be that Liminf [langle]n+1,2n[rangle] = [emptyset] as well. Hence the limit is empty. There are no balls in the basket when the job is finished. What nasty thing about infinite processes does this teach? That cardinality is not well-behaved with respect to them. The number of balls in the basket is growing with each step, but when you move from a finite number of steps to an infinite number, instead of becoming infinite, the number of balls becomes zero! And as ThudandBlunder has indicated, you can vary the procedure so that the individual sets in the sequence stay the same size, but the limit set can have any number of balls from 0 to [smiley=varaleph.gif]0 (the countable cardinal infinity). The fact is, cardinality is not continuous with respect to the limit expressed above. This is the flaw with the first argument: It assumes that because the set sizes are growing, the Limit set must be infinite. Unfortunately this is not the case. But people are so wedded to the idea that even after ThudandBlunder pointed out the ridiculous conclusion that it leads to (what is the smallest ball still in the basket?), everyone was still sure it was correct, and hoped that infinite numbers would provide an answer. But the balls are labeled with Natural numbers, which are not infinite, so there is no ball labeled "infinity". The second argument is a simple application of logic: Claim: there are no balls in the basket at the end. Proof: for every natural number k, ball k was removed from the basket at step k, so it cannot be in at the end. Since every ball has a natural number label, there can be no balls in the basket. I have more to say on the subject, but I am out of time. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by towr on Apr 6th, 2003, 7:10am One could also consider that the proces is simply impossible.. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 6th, 2003, 10:13am on 04/06/03 at 07:10:18, towr wrote:
In the same way that 1/2 + 1/4 + 1/8 + 1/16 +......+ 1/2n +........ cannot possibly be equal to 1? |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by towr on Apr 6th, 2003, 12:21pm yes :p well there is a difference of course.. For every ball taken out, two are put in, so the bucket can't be empty. At the same time every ball with a label has been taken out, and since they're all labeled the bucket must be empty. That can't be true at the same time. In short I do not think it makes sense for any real-world problem. So impish pixies that do this can't exist.. 1/2 +1/4 + ... does make sense in the real world, but honoustly, you can only apply infinite processes by approximation in real life. Infinite processes would take infinite energy, if not infinite time. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Chronos on Apr 6th, 2003, 7:08pm I'm still a bit uneasy with this one. To explain why, consider a few simpler examples. Case 1: I have the aforementioned balls with numbers on them. At each step, I take out the current ball, and place its successor ball in the bin. How many balls are left in the bin, after I'm done? By the same argument as in the original puzzle, there is no natural number left, so no balls. Case 2: Instead of having an infinite number of balls at my disposal, I have just one. But the numbers are written in pencil. At each step, I take the ball out, erase the number on it, and write the successor number on it. This is equivalent to Case 1, is it not? Case 3: Since I'm just erasing and re-writing the numbers, suppose that I just leave the ball in the basket, while I'm making the change. This is equivalent to Case 2, is it not? Case 4: Suppose that I represent the numbers in such a way that I don't have to erase the old one in order to write the new one. For instance, I might represent 1 by a single dot, 2 by two dots, etc. In this case, the process of changing a number consists solely of adding a dot to the ball. So in each step, I add one dot to the ball. This is equivalent to Case 3, is it not? But on the other hand, if I have a ball in a basket and add a dot to it an infinite number of times, I do know what I have: A ball with a transfinite number (specifically, aleph-0) of dots. So now what I have is a ball in the basket, with markings on it. Those markings don't correspond to any natural number, but the ball is still in the basket. In what step did this become different from my Case 1? A similar puzzle, by the way: Suppose I have a light bulb which is initially off. After half an hour, I flip it on. A quarter-hour after that, I flip it back off. An eighth of an hour after that, I flip it on again, and so on. Describe the state of the bulb after 1 hour. If you're going to dismiss this one as unrealistic, by the way, be prepared to explain why the balls-in-basket puzzle is not similarly unrealistic. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 6th, 2003, 8:03pm on 04/06/03 at 19:08:23, Chronos wrote:
Yes. Quote:
No. It LOOKS like Case 1 after any finite number of steps, but it is different. In Case 1, each ball makes two transitions: once into the basket, once out. Thus we can logically determine the location of all balls at the finish. In case 2, we have one ball going in and out infinitely many times. Case 2 is "[omega]-inconsistent". That is, there is no way to define it's final state. Quote:
No. Now the ball makes 1 transition only. Its final state is well-defined: in the basket. It is also not equivalent to Case 1, even though the contents of the basket look the same after any finite number of steps. There is something [omega]-inconsistent here, though. What label is on the ball at the end? This cannot be determined. Quote:
For the ball, yes. For the label, no. The label on the final ball is now discernable, which of course is exactly why you introduced this case: Quote:
Case 2 and Case 3. Quote:
As in Case 2, the light changes states infinitely many times - so there is no way to decide its state at the finish. Of course as towr points out, even the finite time does not make this problem realistic. To me though, the realism or unrealism of the puzzle is immaterial. The puzzle is not meant to be realistic. Neither is it realistic to believe 100 red-eyed monks will kill themselves 3+ months after some stranger mentions something they already knew, or that a bee/fly/bird would fly thousands of miles from one train to another AT CONSTANT SPEED, then turn around and head back WITHOUT ANY LOST TIME. Yet I have never heard anyone complain about the unreality of these puzzles. The point of all such puzzles is: if such a thing were possible, could you arrive at a unique logically consistent answer? (Unique in the sense that to come up with a different answer requires assuming things not found in real life or suggested in some way by the puzzle.) For this puzzle such an answer exists. Since each ball makes only two moves, its location at the finish is well-defined. And for all balls in the puzzle, that location is outside the basket, so the basket must be empty. The other analysis does not provide a second solution, since it depends on a false assumption: that a sequence of sets of increasing size must "converge" to an infinite set. For Case 2 or the light, there is no answer. The position of the ball, and the state of the light, at the finish cannot be discerned from the given information. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by towr on Apr 6th, 2003, 11:26pm I still don't buy it. At every step k, k+1 is clearly in the bucket, so at every step there must be at least one ball in the bucket. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 7th, 2003, 5:06pm At every step after the first there are many balls in the bucket. And the number of balls is growing. If Bn is the contents of the bucket at step n, then But this limit does not actually have anything to do with how many balls are in the bucket at the finish. Cardinality is not continuous here. It's similar to but 00 = 1. It should be clear that every individual ball is not in the bucket at the finish. The ball is placed in the bucket at some point in the proceedings, and then removed at a later time. After that, it is never touched again. The only way for the bucket to still contain balls is if new ones magically appeared (one guy in a Usenet discussion of this puzzle actually proclaimed that this was a valid way of modelling the situation ::)). So we have the following situation: Card(Bn) [to] [infty] Card(B[subinfty]) = 0 Cardinality is not continuous. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 7th, 2003, 5:18pm Quote:
I'm not sure if that's a good example, as this is only true by definition. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 7th, 2003, 5:42pm Actually, it is an excellent example. (Minor nitpick - of course it is only true by definition - everything that is true is only true by definition! What you meant was, it is only true by convention... but then, I suppose the same complaint can be raised with that! :P) We define 00 = 1 because it is a far more useful definition than the other candidate: 00 = 0. But even if the other definition were chosen, I would have given the example: but 00 = 0." In any case, it is but one example of a discontinuous function. Cardinality is another. One normally does not think of cardinality and continuity together. That is because most cardinals are discrete: they have no neighbors that approach them closer and closer... . But when you start tossing in infinite cardinals, this is no longer the case. Some cardinals are called "limit cardinals", because they have no immediate predecessors. Instead they are approached by an infinite number of cardinals below them. The first of these is [smiley=varaleph.gif]0 - the cardinality of the natural numbers. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 7th, 2003, 6:53pm Yes, I was going to say that, although it is quite easy to accept - or visualize - that the limit of f(x) as x->a is not necessarily equal to f(a), in this (discrete) case the discontinuity is at infinity - making it rather difficult to visualize, much less accept. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 7th, 2003, 7:35pm So - Bring it in from infinity! Instead of labeling the sets B with integers, label them with egyptian fractions: The symbol representing the nth set is B1/n. The final set is B0 The limit may be stated as: while Card(B0) = 0, (with the understanding that x is restricted to numbers of the form 1/n, n [in] [bbn]). This is completely equivalent to the original statement. When it comes to limits, infinity is no different than ordinary numbers. If you add [infty] and -[infty] to the real line, one at each end, then what you get is topologically equivalent to a closed interval, such as [-1, 1] ("topologically equivalent" means that it behaves the same as far as limits and continuity are concerned). You have to get into higher infinities before topological behaviour gets weird. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Rujith de Silva on Apr 9th, 2003, 11:58am I think intuition fails us here because asking "What is the state after an infinite time?" is radically different from asking "What is the state after a really long time?" Similarly, saying "Dog created the universe an infinitely long time ago" is equivalent to saying "The universe has always existed." |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Chronos on Apr 9th, 2003, 7:46pm Actually, my claim is that the question is meaningless. Once you accept that there exist similar questions which are meaningless (like whether the light bulb is on or off), then you have a bit more of the burden of proof, to show that this question is, in fact, meaningful. I can think of two ways to model this question: By reality, or by mathematics. But I can't model it by anything in reality, because nothing can move balls around that fast. And on the other hand, I've never seen a precise mathematical way of expressing this question. The closest I can come is by stating a function that gives the state of the basket (and the balls in it) as a function of time. But as described in the problem, this function only has a domain of (-oo, +1 hour). If you ask me what the value of this function is at a point greater than or equal to one hour, I have to extend the function in some way. But heck, I can think of a heck of a lot (2^(2^Aleph0), to be precise) different ways of extending it, to give any answer you like. That's no good. So, how does one express this problem in a mathematically precise way? |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 9th, 2003, 9:27pm The way wowbagger and I have already expressed it is quite precise mathematically. For each k, the location of ball k at the end of the process is easily determined. Ball k was put in the basket early in the process, and removed a short time later. After this, ball k was never touched again. To claim that the question of its location after the process ends is "meaningless" is rather incredible! Ball k changes its position twice. Its position for every time after its second move is the same, including times after the process is finished. That position is "outside the basket" for every k. Presuming that the only balls available to be in the basket are those meantioned in the puzzle, it is clear that the basket must be empty at the finish, for the position of every ball at that time is "outside the basket". As I stated in my previous posts, your light switch example is NOT similar to this one. That example has an object jumping between two discrete states infinitely many times. Its final state cannot be determined. This puzzle does NOT have anything necessary to it which jumps infinitely many times between discrete states. Not even the set of balls in the basket does this, because the sets are not truly discrete: they converge to a limit set: [emptyset]. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by BNC on Apr 10th, 2003, 12:12am on 04/09/03 at 11:58:43, Rujith de Silva wrote:
Sounds like an interesting religion :P |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Evenstar on Apr 10th, 2003, 4:03am on 04/02/03 at 10:53:10, THUDandBLUNDER wrote:
I can't help thinking "After an infinite amount of time has elapsed"... How can there be anything after an infinite amount of time? At what point would that be? Icarus also talks about "when the process is finished". But given that it is infite, how can it be finished? Anybody patiently enough willing to explain that? Kind regards, The Evenstar. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Rujith de Silva on Apr 10th, 2003, 5:43am on 04/10/03 at 04:03:42, Evenstar wrote:
Yes, but it will take an infinite length of time to explain! |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 10th, 2003, 10:13am Quote:
Evenstar, if you can't be bothered reading the question properly then please don't waste people's time by replying. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by visitor on Apr 10th, 2003, 10:21am on 04/10/03 at 00:12:59, BNC wrote:
Rujith is obviously an agnostic dyslexic insomniac, lying awake at night wondering if there is a Dog. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Evenstar on Apr 11th, 2003, 1:14am on 04/10/03 at 10:13:33, THUDandBLUNDER wrote:
Yes, you have a point there. I had read the question completely, but between the time the question was asked and the time the answers started comming in, my mind had left out that part. My apologies for that. Maybe it's because I have this mental block which prevents me from trying to cram an infinite amount of things into a finite container. Then again, I never had a problem with 1/2 + 1/4 + 1/8 + 1/16 + ... = 1, which is pure math. Transforming them from numbers to slices of time I can grasp, attaching an action to the timeslice is what makes it difficult for me. Mind you, it's not that I doubt that the reasoning behind it is wrong. The proof is quite, hmmm, how could I put it in english... it's quite sound. It's just me who can't wrap my brain around the idea that had the pixie taken out the highest numbered ball instead of the lowest, the bag would hold an infinite amount of balls instead of none. The two actions (removing the lowest/highest numbered ball) seem identical yet have a totally different outcome. Kind regards, The Evenstar |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on Apr 11th, 2003, 4:02am Quote:
Yes, it is really counter-intuitive, isn't it? ??? How about Simpson's Paradox for a really easy to understand yet counter-intuitive result? (Sorry for being so brusque earlier.) |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Jacky Poon on Apr 13th, 2003, 6:55pm At first I thought argument 2 would be correct, but that removing the highest numbered ball instead would alter the result is making me uneasy. Consider the following scenario: You have an infinite number of small balls, only they are numbered from 1 upwards once in pen and in pencil so that the pencil numbers (which are changable) and pen numbers (permanent) coincide. Every minute you throw in the two balls as in the question. But every minute: 1. The Pixie swaps the pencil numbers around so the lowest numbered ball in pen has the highest number in pencil. 2. The Pixie removes that ball. (Pen: smallest, Pencil largest) QUESTION: After an infinite number of time how many balls are there? 1. Looking only at the pen numbers this is equivalent to the original question, each time the pixie is removing the lowest value of the ball. Therefore according to the there is 0 balls left. 2. Looking at the number of pencil numbers that are written on the remaining balls - this is equivalent to removing the highest pencil number each round, so there should be infinite pencil no's written on the balls. Since there is only ever 1 pencil number per ball, there are infinite balls. But infinite balls does not equal no balls. Therefore either a) there is a flaw in this argument or b) there is a flaw in 0 as a solution to the original problem. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 13th, 2003, 7:28pm The answer is (a) there is a flaw in the argument. You shouldn't be looking at the markings, pen or pencil, at all. You have to look at the BALLS. With or without the pen markings, with or without the pencil markings, the basket is empty - because each ball was put in once, and was removed once. From there on out, it is not in the basket. When the infinite process is finished, each ball must be outside the basket, so the basket must be empty. What will happen in your scenario in the end is that (1) the basket is empty. (2) each ball, outside the basket will have 2 numbers written on it, with the number in pencil being twice that in ink. The outcome of this process is not controlled by the numbers, and the puzzle could have been stated without numbers at all: You have a countably infinite number of balls (this means there are no more balls than there are natural numbers). You put them into the basket two at a time. The imp removes the ball (or one of the two balls) that have been in the basket longest. Stated as such, the basket will still be empty, because every ball is eventually removed and never touched again. Change the imp's behavior to: "the imp removes one of the two balls you just put in." Then, the basket will contain infinitely many balls at the end, because out of every two balls you put in, one of them is never removed. Change the imp's behavior to: "For the first 12,642,970 times you put two balls in, the imp removes a ball at random. After this, the imp ignores the balls still in the basket, but removes the ball that has been in the basket longest of all those placed in after this point." - In this case at the end, the basket will contain 12,642,970 balls - namely the ones put and never removed before the behavior change. Change the imp's behavior to "The imp removes a ball completely at random", and you do not have enough information to determine the result completely. You can say that the probability of the basket being empty is 100% (with infinitely many cases, this is not the same as saying that the basket must be empty). - I read this result in another discussion of this puzzle, and have not checked myself if it is true, but it sounds right. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by mypalmike on Apr 24th, 2003, 1:03am Suppose we do refine the question to involve the pixie taking out the "oldest ball". Consider the alternate timing suggestion, where the timing between successive events is halved as t approaches 60 seconds. At the "end of the process", the time slice is exactly zero. Which ball is oldest when all balls are the same age? Arguably, the process can not be brought to a conclusion because the pixie can not identify the oldest ball. This is not simply playing with semantics or words. In the original question, the set theory explanation assumes that the lowest numbered ball can be identified through completion of the process. Is this a valid assumption? |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Apr 24th, 2003, 5:50pm The time slice between any two steps is never actually zero. By the time it gets to zero, the process is finished, so the imp does not have to worry about choosing which ball is oldest. There are no balls left to choose between. There is an interesting discussion about a variant of the same puzzle at this site, (http://www.faqs.org/faqs/puzzles/archive/logic/part5/) - It's the third puzzle on the page." In particular, he mentions an "alternative model" that in my opinion is just barely at the borders of being reasonable/unreasonable. To be fair, though, I should say that the solution given here is unique only under the following assumptions: 1) The only things that could possibly be in the basket at any time are the balls mentioned in the puzzle. 2) If a ball is not moved at all after some point in time, then its position at that time will also be its position at the finish. Both of these assumptions seem reasonable enough to me to be taken for granted. If we were to allow violation of them here, then why should we not allow similar violations in other puzzles? ("He can't know what his hat color is, because the judge was hiding a chartreuse hat behind his back!" "None of the prisoners can figure out their hat colors because the hats sponeously rearrange themselves between guesses.") |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by rmsgrey on May 14th, 2003, 2:21pm I'm still not convinced that the canonical solution (which I accept as consistent with accepted mathematics and generally useful) is the only consistent way of modelling this type of situation - my intuitive answer is that at time oo there are oo many balls left inside, labelled oo+1 to 2oo... Going back to the original post, the second argument (what is the lowest numbered ball in the bucket) is susceptible to the counter: "what is the number of the last ball put into/taken out of the bucket?" Looking at Icarus' last post in more detail, it seems that, to support his solution's uniqueness, his first assumption should be that only balls with finite labels are involved - the original statement of the problem only says that there are an infinite number of uniquely numbered balls available. Whether they are restricted to natural numbers only or allow countable transfinite numbers is not made clear. Of course, changing his assumption this way means that it is no longer a special case of a universal underlying assumption for "nice" riddles (as opposed to "joke" riddles or "bad" riddles). |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by wowbagger on May 15th, 2003, 2:30am on 05/14/03 at 14:21:45, rmsgrey wrote:
And at what time was ball number oo+1 put into the bucket? Quote:
That's like asking: "What is the largest natural number?" Hm, the naturals are not bounded above... |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by rmsgrey on May 15th, 2003, 1:07pm on 05/15/03 at 02:30:41, wowbagger wrote:
At time 1+oo/2. I don't see a problem. As I said, this isn't the standard extension of numbers to infinity. I should probably say that I'm using oo to indicate a fixed (unspecified) countable infinity rather than the unique countable infinity of the standard version. I'm also not certain how useful this alternate model is, or even if it can be formalised in a consistent fashion. If it can, then there seems to be no reason why "realistic" processes should prefer one model of infinity to any other since there is no direct experience of infinity in real life. Quote:
So there is no last ball moved either into or out of the bucket? In that case either no balls are ever moved, the process can never end, or the argument that there are no balls in the bucket because you can't name the smallest is seriously flawed. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by rmsgrey on May 15th, 2003, 1:23pm on 04/04/03 at 12:52:01, cho wrote:
The quantized foam would be on a scale of 10-33m while the distant galaxies are only around 1026m away and (if I remember correctly) have a size of about 1020m or an initial granularity of one in 1053 or so. For fuzziness to be visible, the accumulated error would have to come to about one part in 104 and even then, that only represents a hairs-breadth of error over a canvas one meter across... I'm more impressed that the optical instruments on Hubble can resolve an object roughly a million times as far away as it is large with such clarity than that planck length effects don't distort the image. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on May 15th, 2003, 10:43pm Quote:
rmsgrey, if there are an infinite number of infinities and you invent another, how many infinities do we now have? |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by rmsgrey on May 16th, 2003, 11:55am on 05/15/03 at 22:43:29, THUDandBLUNDER wrote:
Depends on your model of infinity. The standard model takes the continuum hypothesis (that the smallest infinity greater than aleph-null is aleph-one) as an axiom, but it has been shown that the continuum hypothesis is independent of the other axioms in the standard model (as with the parallel postulate in geometry). If you work within the standard model, then, if I remember correctly, there are only countably many infinities (formed inductively by diagonalisation for example) so as soon as you get an infinite number of them, you can no longer introduce new ones. If you assume the negation of the continuum hypothesis, then it depends on the properties of the lowest infinity greater than aleph-null, and the number of infinities could remain countable or become uncountable. Though, of course, you're not really making up a new infinity in that case, simply changing the rules so that the "new" infinity (and all its consequences) have "always" been there. The question of "inventing" a new infinity is misleading - and ambiguously phrased - if you have an infinity of infinities, which of them is the cardinality of the set of infinities? The only possible answer to your question is, of course, "an infinite number", but not necessarily the same infinite number. If this debate goes on much further, I'll have to go back to the axioms and see what sort of system I can construct (which will probably keep me quiet for a while). The major advantage of the standard model is that any time a countable infinity comes up, it's guaranteed to be the same aleph-null (give or take a minus sign). For my non-standard model, it looks like you can only compare two countable infinities if you can compare their generating processes - pick one to be your reference and describe the other(s) relative to it. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by THUDandBLUNDER on May 17th, 2003, 7:43am Quote:
rmsgrey, you talk the talk, but.... ....as this puzzle does not involve uncountable infinities, I fail to see what it has to do with CH. Furthermore, you want "oo to indicate a fixed (unspecified) countable infinity". Isn't the onus on you to 'specify' exactly what you are referring to? (And are there any unfixed infinities?) Once you have done that, I will try to take half-seriously your answer of '(1 + 00)/2'. Perhaps the first axiom of your system is that 00 is an odd number? A very odd number. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on May 17th, 2003, 9:28am Looking carefully at the wording of the puzzle as originally stated, I have to agree with rmsgrey that it does indeed allow for the possibility of non-natural number labels on the balls, and since the stop time is indicated as "after an infinite amount of time", it does not imply that only finitely counted steps were taken. So it is indeed possible for infinitely labeled balls to come into play. This could be fixed with one or two small rewordings of the puzzle. But since that shuts the discussion down, instead let's see what we can come up with for the puzzle "as is", along with my two conditions given in my previous post, also "as is". I have said before in other threads that there are all sorts of infinities, and you can define new ones at need - provided of course that your definitions are consistent. There are some conditions on the infinities allowed here, though. In particular, since our process takes place in time, it has to be totally ordered, and therefore the balls affected by it must also have ordered labels. (There can be all sorts of balls not in this order, but they will never be manipulated by any step in the process. So by the second of my conditions, they won't ever be in the basket). This still leave things open to multiple types of infinite numbers. I will have to consider it longer to see what I come up with. I do have some comments to make on this, however: Quote:
I was not aware there was a "standard model" of infinities. The are three common types (or models) of infinite numbers, and again, others can be defined. The common ones are Cardinals - which appear to be the ones you are refering to by this, Ordinals - you might want to consider them as labels, and of course the continuum infinities at the ends real line or the complex plane. Assuming that you mean Cardinals - they do not depend on the Continuum hypothesis. And for most results it is not needed. The Continuum hypothesis merely asserts that the cardinality of the real numbers is the second infinite cardinal (it must be at least the second). The generalized continuum hypothesis says that for any infinite set A, If P(A) is the set of all subsets of A, then Card(P(A)) is the next cardinal higher than Card(A). This hypothesis is useful in relating cardinals with sets, but is not particularly important in the existance and behavior of cardinals themselves. Quote:
Sorry, but you do not remember correctly. Maybe Russell-Whitehead style set theory can handle the concept of the cardinality of all cardinals (I don't know - I've never studied cardinality in that system), but in the more commonly used Zermelo-Frankel approach, the is no such thing as the set of all cardinals (to have such a thing introduces paradoxes). And without that set you cannot define how many cardinals there are. But while you can't get a full set of cardinals, you can get a set of all cardinals less than a particular one, and - if I recall correctly - some of these sets are uncountable. A result which does not depend on the continuum hypothesis. |
||||||||||||||||||||||||
|
Title: Impish Pixie Post by THUDandBLUNDER on May 17th, 2003, 12:10pm Quote:
Icarus, I don't understand how that can be, as there are an INTEGRAL number of operations - unless you are likening "an infinite amount of time" to the real line? But even the real line is punctuated by integers, just as "an infinite amount of time" is punctuated by one-minute intervals. Or perhaps it is possible to interpret the phrase to mean (for example) "after alephn units of time"? In all the threads and sub-threads that I have read about this puzzle, I have never seen any claims that we may be using an uncountable number of balls. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on May 18th, 2003, 1:20pm You don't need an uncountable number of balls to have balls with infinite labels come into play. All you need is to toss in one more ball after you have already taken infinitely many. Since the puzzle only specifies "after an infinite amount of time", this is actually allowable, since [infty] + 1 is still infinite. To make this more understandable to those less aquainted with infinity, consider it according to the "increasing speed" variation: the first step takes 1/2 minute, the second step takes 1/4 minutes, the third 1/8 minute, etc. So all natural numbered balls have their turn within the first minute. Instead of stopping immediately after that minute, you toss in balls [omega] and [omega]+1 ([omega] is the symbol normally used to denote the least infinite ordinal), and the imp takes out [omega]. You have still executed an infinite number of steps. The balls are still all numbered starting with 1 and going up. It fits the wording of the puzzle (adjusted for the increasing speed variation), and leaves a single ball, labeled [omega]+1, in the basket. Note that this does not violate the main point of this puzzle: after finishing with the integer balls, the basket is still empty. Rather, this approach makes use of a technical loophole to allow an extra step or steps which repopulate the basket. If you keep going, using ordinal-labeled balls, until you get every ball up to but not including 2[omega] (you worked twice as fast, so this took only an additional 1/2 minute), the basket is empty again. Keep going and the bucket repopulates, only to empty again at 3[omega]. Keep at it, and by the time you reach two minutes from the start you have arrived at (but not yet used) ball [omega]2. The basket is once again empty. Redouble the speed, and a minute later you've reached 2[omega]2. Redouble again... by 4 minutes you've reached [omega]3. ... Only countable ordinals are reachable in a finite amount of time by this "increasing speed" method. If you accept that the wording of the puzzle implies a "well-orderedness" on the balls or process steps, then it is impossible to reach an uncountable number except after "an uncountably infinite time" by any model. And if you accept the "well-orderedness", you might as well use the ordinals to label the balls, as any other type of "well-ordered infinite numbers" are equivalent to the ordinals, as far as this puzzle goes. (This includes the use of cardinals.) In this situation, AT NO TIME does the bucket ever contain an infinite number of balls, but the bucket could have any finite number of balls when you stop, depending on just when you choose to. One can reasonably argue that using this scenario, or a similar one, violates the normal understanding people have of the word "infinity". But one can also argue that the normal understanding people have of the word "infinity" is not robust enough to make the puzzle sensible at all. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixies Post by Josh on Jun 7th, 2003, 4:19pm The answer is that you will run out of balls to put into the basket. You have an infinite number of them, and you add two at each step. An infinite number of steps requires twice as many balls. Quote:
Are you sure this is true? If you can have an infinite number of numbered balls, and an infinite number of discrete steps, you can have an inifinite number on an infinite number of balls. I don't think Natural numbers are involved in this question at all. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixies Post by Josh on Jun 7th, 2003, 4:21pm on 06/07/03 at 16:19:12, Josh wrote:
Um, never mind this part... :-[ |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Jun 8th, 2003, 8:21pm Josh: 2[infty] = [infty]. (More exactly, 2[smiley=varaleph.gif]0 = [smiley=varaleph.gif]0.) An example: Compare the Natural numbers [bbn] with the even naturals [smiley=bbe.gif], and the odd naturals [smiley=bbo.gif]. Fact 1) There are no more or less natural numbers than there are Even natural numbers. This must be the case, since you can match up [smiley=bbe.gif] one-for-one with [bbn]: 1 [smiley=leftrightarrow.gif] 2 2 [smiley=leftrightarrow.gif] 4 3 [smiley=leftrightarrow.gif] 6 etc. Hence the cardinality of [smiley=bbe.gif] is also [smiley=varaleph.gif]0. Fact 2) There are no more or less natural numbers than there are Odd natural numbers. Same Argument: 1 [smiley=leftrightarrow.gif] 1 2 [smiley=leftrightarrow.gif] 3 3 [smiley=leftrightarrow.gif] 5 etc. Hence the cardinality of [smiley=bbo.gif] is also [smiley=varaleph.gif]0. Fact 3) The natural numbers are the disjoint combination of the Evens and the Odds: [bbn] = [smiley=bbe.gif] [smiley=uplus.gif] [smiley=bbo.gif]. So, [smiley=varaleph.gif]0 = [smiley=varaleph.gif]0 + [smiley=varaleph.gif]0 = 2[smiley=varaleph.gif]0. Looked at another way, if you run out of balls, then you have placed an infinite number of balls in the basket. This cannot of happened after any finite number of steps, because on the Nth step you have only put in 2N balls, a finite number. Putting it another way: when you do run out of balls, you are finished, and puzzle is to figure out the contents of the basket at this point. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by BNC on Jun 9th, 2003, 2:05am I've been thinking about this problem for a long (though < oo) time now. I have read the thread several times very carefully. And I still have a problem with it. I will try to state my problem, and hopefully someone will be kind enough to response. Disclaimer: I have never studied "discreet mathematics" or set theories, so my knowledge of infinities is limited at best (I did learn quite a lot of calculus at the time). The way I learned it, infinity is not a "number" but rather is a "concept" -- a definition of what is happening for very large or very low numbers (processes). Also, English is not my mother tongue so I may use the wrong terms; I hope that they would be understandable from the context. Here goes: As far as I remember, a number series an is defined to have a limit at infinity if: for every number M there exist a number N (N=N(M)), such that for every n>N, an > M. Now, what is the number series of the number of balls in the basket? a1 = 1 a2 = 2 . . an = n lim n->oo an = oo So, number of balls is infinity. Counter claims: 1) The cardinality is not continuous. Thus, the limit has nothing to do with the actual value. >> BUT: to prove the opposite claim of 0 balls, you still use a limit (a limit of sets, not numbers -- but still a limit). 2) What is the lower numbered ball in the basket? It cannot be any finite number, as they are all out. >> BUT: of course all finite number balls are out after a finite amount of time. But the same number s still in the basket. What is the number in the basket? Heck, I don't know. What is the number of the last ball that was removed before process end (thanks to rmsgrey)? And what is the "minute number" at which it happened? Similar questions may be asked regarding the alternative “shortening time slices” version. To me, this reasoning could be used to achieve absurd results: I flip a fair coin. Head: I keep quite. Tail: I start counting from 1 upward 1,2,3,… ad infinum, one number per minute, and thus am never quite. Question: What happened after an infinite time? Head: I'm quite. Tail: I must be quite too. Otherwise, what number am I saying? Every number was already said at a previous finite time. Thus, I'm quite. But Tail means I’m never quite. And therefore, the (fair) coin must have probability 1 for Head. I will accept a reply of "that's the definition / convention for that case" (like in 00) -- but than I don't accept it as a valid riddle. Thanks in advance for your time. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by rmsgrey on Jun 9th, 2003, 8:50am Having consulted with some friends doing Maths doctorates at Cambridge University, I'm now of the opinion that, for infinite time (at least for small infinities), the value of the number of balls in the jar can be any natural number - basically, at time w (omega, the smallest infinity) the bucket is empty. At times after w the number of balls is the same as after the equivalent finite time. The trouble with the arguments BNC highlighted (cardinality being discontinuous and not being clear on numbers on balls) is that they just show that the immediate attempts to answer are flawed, and don't show why the 'correct' method is. At the moment, I'm accepting argument by authority, with a caveat that my friends are themselves not entirely comfortable playing with infinity in this way, so may have overlooked something subtle. As to BNC's coin toss, there's a flaw in the argument - if you stop counting at time w on a tail, then it's not true that you're never quiet when the coin comes up tails. Since it was only specified that counting continues until infinity ("ad infinitum" in Latin) what happens after that is unspecifed, so you can't argue based on what you'll be doing then. In fact, the argument seems to show that you'll be quiet after infinite time whether you throw H or T |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Jun 9th, 2003, 7:11pm on 06/09/03 at 02:05:18, BNC wrote:
Yes, infinity is a concept (actually a number of different concepts are all described by the same word "infinity" - that's why I've said elsewhere that there are several type of infinities), but "one" is also just a concept! All things mathematical are nothing more than concepts. To make these concepts useful we have to come up with consistent definitions. Then we can examine the properties of these things we have defined. It is inaccurate to say "infinity is not a number". There is no fixed definition of the term "number" in mathematics. It is applied to many things you would not normally think of as numbers (matrices, for example ). There are several definitions of sets of "numbers" which include infinite numbers. What your instructors should of said (but didn't, because they didn't want to confuse their students further by explaining all this) is that infinity is not a REAL number (as in the set of real numbers [bbr]). Quote:
No - that only shows that the limit of the number of balls at finite times is infinity. To conclude that the number of balls in the basket at time [omega] (that is, when first an infinite number of steps is accomplished) is infinity, you must prove that this limit counts the balls in the basket AT [omega]. The whole basis of argument 1 is the hidden assumption that this is true. But in fact it is false. Quote:
The problem with your limit approach is not the limit, but the hidden, never justified, assumption that the limit of the number of balls at finite times is the number at time [omega]. In the limit approach that I gave, there was no such assumption (other than a mistaken belief that the puzzle statement only allowed integer numbered balls - a rereading prompted by rmsgrey's last post on 5/16/03 revealed this to be false, which I admitted in my next post following). But the problem does not need to be done by limits at all. With the following clarifications of the original problem, which I have also stated before, it can be deduced by simple set theory logic that the basket is empty: (1) The only things available to be in the basket at any time are the balls described in the problem - one ball for each natural number. (2) If a ball is never moved after time K - where K is finite, then its position at time [omega] is the same as at time K. (I have said before, and still maintain, that these are reasonable assumptions about modeling the problem, and need not be specified in it, any more than one specifies any number of other assumptions. But there are apparently some who disagree). From (1), the only possible contents are the integer balls, but by (2) all of them are outside the basket at time [omega]. Hence the basket is empty. So what is the difference between your assumption that the limit represents the balls at time [omega], and my assumptions (1) and (2)? My assumptions are about how to model the "physical" situation using mathematics. Modeling is by definition an assumption about how the world (real or imaginary) works. Your assumption is within the mathematics itself. And within the mathematics it can (and has) been shown false. Quote:
??? You seem to be saying here that the ball is in the basket and out of the basket at same time. ??? Could you please clarify this? Quote:
There was no last ball removed. At time [omega], there terms "last" and "previous" are undefinable. Quote:
The "shortening time slices" statement is simply to allow people to get their heads around the concept of "time [omega]". It does not offer anything different from the regular version. Quote:
"But Tail means I’m never quiet." - How so? You can easily prove this for finite times, but you are assuming it against all evidence after infinite times. Quote:
Like T&B, and I suppose most other people, you are not understanding my point with 00. I was NOT saying that the basket was empty because we define it to be. (Just to be clear, T&B's disagreement was entirely different.) The basket must be empty, because (given the two modeling assumptions mentioned above) logic demands it. To say that it is not empty is to give rise to a contradiction. Quote:
Reasoned debate with someone who is intellectually honest is never a waste of my time. on 06/09/03 at 08:50:47, rmsgrey wrote:
Yes, that was my conclusion (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049309591;start=50#51) too, after noting that the problem statement does not limit the balls to having finite labels. However, this is clearly an unintended oversight. As most people (not being familiar with the concept of infinite numbers) would understand the problem, only finite numbers are available. And with this added limitation, at time [omega] there are no more balls to put in, and as you have said, the bucket is empty. Quote:
What in the world are looking for in "showing why the 'correct' method is"? In this thread, you have seen Wowbagger's original solution (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049309591;start=0#9) My limit of sets explanation (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049309591;start=0#16) and at the bottom of the same thread, a short logical proof. This was followed by several posts raising supposed counter examples, all of which I answered, demonstrating why the counter-examples fail to apply. I have also re-examined and made explicit the modeling assumptions made, and admitted the caveat that you were correct about the puzzle allowing transfinite numbers. But with the two modeling assumptions as I have stated them in this post above (slightly changed from a previous post to limit to make explicit the limitation to finite numbers), I have demonstrated repeatedly that they logically lead to only one conclusion. So what is it you require? Quote:
The modeling side of this puzzle is (and will always be) a little shaky. This is because it does represent a fundamentally impossible scenario, so there is no way to demonstrate "what really happens". But the mathematical side is quite sound. Before I say "yay or nay" concerning your refutation of BNC's argument, I would like to see his clarification of it, so that I can decide if this problem is in his argument or our understanding of his argument. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by BNC on Jun 10th, 2003, 1:13am Thanks, guys! I see now that my understanding of infinity (or infinities) is even more limited than I thought :-[ I didn't realize about "transinfinte" numbers, and the w thingi. I wouldn't amagine one may count "past infinity". Oh, well. One more thing to add to my (too long) list of "things to read / learn / experiment at the sonnest available time". |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Jun 10th, 2003, 8:06pm *** Warning *** I'm about to go off on another of my rambles about infinite numbers, so all those given to drowsiness should stop reading now, less they enter a comatose state. :-X One way that you can get a better idea about infinite or "transfinite numbers" is to look at models of them within the real numbers. I gave a quick overview of the definition of the three main types of infinities in this post (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027804564;start=125#135). It is the third type, ordinals, that we have been discussing here. By definition, ordinals are "order types" - ways of "well-ordering" a set. A set is well-ordered if it has an ordering (<) for which every non-empty subset has a least element. It turns out that if you have any two well-ordered sets A and B, then either there is a K in B such that the set BK = {x | x is in B and x < K} can be matched up 1-1 with A by an order-preserving correspondance (if r,s in A and x,y in BK, with r ~ x and s ~ y, then r < s if and only if x < y), or there is a K in A for which the reverse is true. One way of interpreting this result is that there is one "universal" well-ordering. Any particular well-ordering you come across is just a chunk off the front of the universal one. All the "chunks off the front" comprise the ordinal numbers. If you have two disjoint well-ordered sets A and B, then you can define an ordering on A [cup] B as (x < y [bigleftrightarrow] [ (x,y [in] A or x,y [in] B) and x < y ] or (x is in A and y is in B) ). So every element of B is greater than every element of A. This is easily seen to be a well ordering, and addition of ordinals is defined by The cross product A [times] B also has a well-ordering (r, x) < (s, y) [bigleftrightarrow] (r < s or (r=s and x<y)). (This is sometimes called the "dictionary" ordering.) Ordinal multiplication is defined by With these, we start building the ordinals. Because two ordered sets cannot have an order-preserving correspondence between them unless they have the same number of elements, ordered sets of different sizes (cardinality) necessarily have different ordinals. On the other hand, all well-orderings of a finite set are equivalent. So the first ordinals are just the Natural numbers [bbn] (for convenience, I am including 0 in the Natural numbers): 0 = ord( [emptyset]) 1 = ord({0}) 2 = ord({0,1}) etc. The natural numbers are themselves well-ordered, so we define [omega] = ord([bbn]). A little work shows that if R is an infinite subset of [bbn], then ord(R) = [omega] as well. Thus [omega] is the least infinite ordinal. We can build larger ordinals using the ordinal addition and multiplication: [omega] + 1 = ord({0} [times] [bbn] [cup] {(1,0)}), where the order is defined by: [forall] n [in] [bbn], (0,n) < (1,0). [omega] + 2 = ord({0} [times] [bbn] [cup] {(1,0), (1,1)}) etc. After all [omega] + k, k [in] [bbn], we get [omega] + [omega] = ord({0} [times] [bbn] [cup] {1} [times] [bbn]) = ord({0,1} [times] [bbn]) = 2[omega] then 2[omega]+1, 2[omega]+2,...,3[omega],...4[omega],...[omega]*[omega] = [omega]2,...[omega]3... . This allows the definition of P([omega]), for any polynomial P with integer coefficients. These comprise all the ordinals of countable sets. The least ordinal greater than all P([omega]) is the first uncountable ordinal. So what was that about modeling them in the Real numbers [bbr]? Consider the equivalence n ~ 1-1/(n+1) between [bbn] and N1 = {1-1/(n+1) | n [in] [bbn]}. This is an order preserving equivalence, so the latter set is well-ordered, and gives us an alternative way of viewing how the natural numbers are distributed. In particular, we can add another element to the "top" of N1 easily: N1* = N1 [cup] {1}. By extending the equivalence, we get [omega] ~ 1. We can continue extending: k*[omega] + n ~ k - 1/(n + 1); k,n [in] [bbn]. By this means we have a model for all ordinals less than [omega]2 within the real numbers. This gives a better idea of the "topological" behavior of these ordinals (that is, their behavior with respect to order and limits). We can see the exact same behavior in a fairly simple set of real numbers. In particular, each ordinal exhibits one or the other of two "behaviors". Most are discrete - no other ordinals approach them beyond some fixed distance - these are the ordinals k*[omega] + n, where n > 0. The corresponding points on the real line are the non-integer elements in the set S={k-1/(n+1) | k,n [in] [bbn], k>0}. All non-integer elements of S are discrete - for each there is a distance d such that no other element is within d of them. However, the integer elements do not have this property. For any d, there are infinitely many points of S within d of each integer. These are called the "limit" or "cluster" points of S. The corresponding ordinals are the "limit ordinals" n*[omega], for natural n [ge] 1. Each is only approached on its lower side. On the upper side, there is a discrete distance (1/2 in S) between each limit ordinal and its immediate successor. We can create correspondences between sets of Real numbers and larger collections of countable ordinals as well. The set of all ordinals < [omega]k+1 has the correspondence ak[omega]k+ak-1[omega]k-1+ ... a0 ~ ak - 1/(ak-1+1) - 1/(ak-1+1)(ak-2+1) - ... with a set Sk of Real numbers. The limit points of Sk are exactly those for which a0 = 0. Points for which a1 = 0 as well are limit points of the limit points. I do not believe it is possible to find a subset of the reals which corresponds to the set of all countable ordinals (I.e. no uncountable set of Real numbers is well-ordered.) But I don't recall for sure right now. A countable ordinal P([omega]) = ak[omega]k+ak-1[omega]k-1+ ... a0 is of "limit order" n if al = 0 for all l < n, and an > 0. The degree of a countable ordinal is the degree of its polynomial. To examine the arithmetic properties of ordinals requires a different tack, since under the correspondences above, addition and multiplication are poorly behaved. And the correspondence between the ordinal P([omega]) and the polynomial P is not much better. The problem is that ordinal addition and multiplication are not commutative. I.e., in general, x + y [ne] y + x, and xy [ne] yx. To see this, look at [omega]+1. By definition this is the ordinal of the set [bbn] [cup] {a}, where a > n [forall] n [in] [bbn]. This ordering must be distinct from that of [bbn], since it has an element, a, with infinitely many things less than it, where as every element of [bbn] has only finitely many things less than it. But 1+[omega] is the set {b} [cup] [bbn], where b < n [forall] n [in] [bbn]. The ordering on this set is equivalent to the ordering on [bbn]. In fact the correspondence {b}[cup][bbn] [smiley=leftrightarrow.gif] [bbn] b ~ 0 n ~ n+1 n [in] [bbn] is order-preserving between the two sets. So 1+[omega] = [omega] < [omega]+1. More generally, if x and y are two ordinals and deg(x) < deg(y), then x + y = y. And if x=ak[omega]k+ak-1[omega]k-1+ ... a0 y=bn[omega]n+bn-1[omega]n-1+ ... b0 (n [ge] k), then y + x = bn[omega]n + bn-1[omega]n-1 + ... + bk+1[omega]k+1 + (bk + ak)[omega]k + ak-1[omega]k-1 + ... + a0. Multiplication can be deduced from the rule if x is finite, then [omega]x = [omega], combined with associativity and distributivity, both of which hold for all ordinals. Edit: corrected some typos. Thanks, Wowbagger, for pointing out some of the errors (yeah - only some, I found a couple more that you missed). Edited again to make use of the new mathematical symbolry. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by rmsgrey on Jun 13th, 2003, 7:11am I apologise for the unclear phrasing in my last post - I'm under time constraints in my internet access since I'm currently restricted to the local public library... Anyway, I am happy with the arguments Icarus has presented for the correct answer under the assumption of termination at time w (as I have said before) but the point I was trying to address was that the specific arguments BNC listed were negative and non-constructive. The arguments which are constructive (and conclusive) weren't mentioned by BNC - possibly because he missed them or possibly because they are more subtle than those he did mention. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by xlh on Jun 23rd, 2003, 8:29pm Sigh, lost my first post attempt for not filling out an email, I'll make this brief, especially since I'm disagreeing with everyone ;D This problem looks to me like a tarted up version of the sum of an alternating series which doesn't converege absolutely. Consider the model: Define a the queue by the order with which the bucket will be emptied (so the next ball to leave the bucket is position 0, the second is position 1, etc). Now take the liminf of the set of filled positions in the queue and you get N. Thus the number of balls in the queue (and thus in bucket) goes to infinity not 0. Why is this model any worse then the model which considers which balls end up in the bucket? If the "proof" that the bucket winds up empty is valid, then what about this: Take SUM( 2 -1 +2 -1 + 2 ...) and label the numbers with naturals with one label per unit and different labels for positive and negative. {1,2} - {1} + {3,4} - {2} +{5,6} - {3} + .... Thus SUM(2-1+2-1+2...) is apparently well defined and equal to 0. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by wowbagger on Jun 24th, 2003, 4:24am on 06/23/03 at 20:29:58, xlh wrote:
xlh, a concept like absolute convergence doesn't make sense when considering sets, i think - but who knows what these mathematicians kill their time with? Quote:
I'm not sure I fully understand your model, but I think that's not even necessary. Did you read Icarus's post (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049309591;start=0#16)? I don't want to stress the technical part, the most important bit is probably this: on 04/04/03 at 16:11:32, Icarus wrote:
The limit of the number of balls after finitely many steps tends to infinity, yet after the process has ended, there are no balls left. This counter-intuitive result is what makes this riddle so intriguing. Quote:
Please read Icarus's explanation. :) |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by xlh on Jun 24th, 2003, 6:23am Quote:
You probably should attempt to understand my model before dismissing it, especially since my point is that you can get different answers with different equally valid models. Quote:
You can't point to a single ball thats left in the bucket, but yet you can't point to a space in the bucket that isn't filled by a ball. Why is one model right while the other is wrong? Quote:
Sorry to be so snarky but please read my explanation. :) |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by wowbagger on Jun 24th, 2003, 9:16am on 06/24/03 at 06:23:20, xlh wrote:
Well, actually I did attempt to understand it. So what do you do in your model? You have a queue that is empty at the beginning, then we add numbers 1 and 2, then we remove number 1, then we add numbers 3 and 4, then we remove number 2, and so forth. Right? In which way do you think this differs from what's happening in the bucket? Every number enters the queue exactly once, and every number leaves the queue exactly once. That's why the queue has to be empty after the whole process is done. Quote:
Yes, I can. Every point in the bucket that was occupied by ball number n is no longer occupied after removing that ball in step n. And after this removal, ball n is never touched again, it remains out of the bucket. Quote:
;D |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by xlh on Jun 24th, 2003, 4:21pm I guess I was too brief after my initial posting mishap. A queue works by adding at the end and taking from the front. A "position" in the queue corresponds to how far from the front of the queue an item is. Think of it like a soda rack: when you pull a bottle out all the others slide forward. This means the sets of positions in the queue are: {} starts empty {1,2} 2 bottles added {1} imp takes one, other slides forward {1,2,3} 2 bottles added {1,2} imp takes one, others slide forward etc. The lim inf is Z+ so the queue never empties. If it concerns you note that the we don't care about the "take from front add to back" aspect of the queue. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Jun 24th, 2003, 5:27pm xlh - The problem with saying that the limit of the number of balls at finite times is infinite, so there must be an infinite number of balls in the basket, is that it's failing is not in the "model". Its failing is in the mathematics! It assumes this "continuity of cardinality" - which can be shown (as I have above) to be false in a strict mathematical sense. At step n, the contents of the bucket correspond to the set Sn = {n+1, n+2, ..., 2n} lim card(Sn) = [infty] lim Sn = [emptyset] Just because the cardinality is growing doesn't mean you will have anything at the limit. On the other hand, the only problem with the "what balls are in the bucket at the end" approach are strictly in the model - that is, the relationship between the "real" situation and the mathematics used to describe it. The logic and mathematics behind this approach are sound. The only question is whether there are "equally valid" models which give different answers. Your "queue" model is a variation of the one I refered to in this post, (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049309591;start=25#41) wherein the placing of balls in the same position infinitely many times results in a "limit ball" in that location at step [omega]. This model may be considered to meet the criteria of the original puzzle, which is why I said there that the "canonical" solution is unique only with the following added assumptions (which I still say are reasonable to take for granted): (1) That the only possible contents are the balls mentioned in the puzzle itself. (1a) That the labeled balls are labeled only with natural numbers (thanks, rmsgrey, for pointing out that this is not actually specified in the puzzle statement). (2) That the only way for the balls to change position is when you or the imp physically move them. These assumptions disallow "limit ball" models such as yours, since there are no balls available to fill the limit positions. Concerning your alternating sum "counterexample". I'm sorry, but the mathematics behind the "canonical solution" do not behave at all like you are claiming in it. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by xlh on Jun 24th, 2003, 7:34pm Please explain why you think the queue model is prevented by your 3 assumptions. My explanation about soda bottles sliding around was simply to help describe the concept, there is obviously no reason we can't define our queue positions without physically moving the balls. Repeating that cardinality is not necessarily continuous or arguing that your model leads to an empty bucket are not useful because I already think both of those things. My question remains "why is cardinality well defined here?" I'm a little confused why you refer me to that link when its discussion ends with: Quote:
and Quote:
This is exactly why I don't think the question has a unique answer. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by wowbagger on Jun 25th, 2003, 4:03am xlh, I had no problem with your model because of it using a queue, I'm more or less familiar with that concept. My impression was just that your model doesn't add anything to simply counting the number of balls in the bucket. It seems to be an unnecessary comlication of your argument. on 06/24/03 at 19:34:27, xlh wrote:
If you understand that cardinality is not continuous, why don't you accept the consequence? My (admittedly sometimes rather naive) grasp of mathematics tells me that the cardinality of the empty set is well-defined. Maybe the question you want to ask is why the limit of sets is well-defined. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by xlh on Jun 25th, 2003, 6:13am Quote:
Sure. If you can tell me why the limit of the sequence of sets from the queue is really {} and not Z+ then I'll gladly concede. Alternatively, explain why the queue model is not legitimate for this problem. |
||||||||||||||||||||||||
|
Title: Re: Impish Pixie Post by Icarus on Jun 25th, 2003, 4:07pm Quote:
The 3 assumptions allow for nothing to ever be in the bucket except the integer-labeled balls. At the end time, after the task is completely finished, they are all demonstrably somewhere else. So the bucket must be empty. Your queue model, like the one described in the link, works by setting up a situation with an infinite number of state changes (ie - the contents of each queue position). In order for it to be a complete model, you must define in some fashion the state at time [omega]. This is the extension to "supertasks" the link describes. There are several ways of doing this for the original problem, but they must be logically consistent with the rest of the puzzle. For instance, you cannot declare that position 1 contains ball #862 at time [omega], because ball #862 was removed from the bucket at step 862, and has never been replaced. And of course the same is true of any other integer ball. What is not excluded by the original puzzle is the possibility of a new "limit ball" occuring in the spot, since it was always occupied. My additional 3 assumptions preclude the existance of any such ball, or anything else being in that position at time [omega]. Hence the only available state for position 1 at time [omega] is "empty". Quote:
It is only illegitimate for the problem given the 3 additional assumptions. If you are allowed to break either assumption 1 or 2, then it can work. Quote:
No - YOUR question was "why ISN'T cardinality well-defined here"? My argument was not based on cardinality. It is the other, false, argument that assumes that cardinality is not only well-defined here, but is "continuous". That is why Argument 1 is false, even for models such as yours that do end up with an infinite number of balls in the bucket. For those models it gets the right answer for the wrong reasons, just like "cancelling the 6s" in 64/16 to get 4/1 = 4. Cardinality is well-defined for any set. The problem does not come in defining the cardinality, but rather the set corresponding to the contents of the bucket at the end time. Quote:
The sequence of sets is Sn = {n+1,n+2,...,2n} The limit inferior of a sequence of sets is by definition the set {x | [exists] N [in] [bbn] such that [forall] n > N, x [in] Sn} The limit superior of Sn is by definition the set {x | [forall] N [in] [bbn], [exists] n > N such that x [in] Sn} The limit exists if and only if these two sets are the same. For Sn = {n+1,n+2,...,2n}, they are both empty. Now the question of what model you use determines whether or not this particular definition of limit provides the balls found in the bucket at time [omega]. But my point in giving it was to show out why argument 1 is false reasoning. And that holds true no matter what model you use. |
||||||||||||||||||||||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |