Balls and gremlins puzzle

As to Bill H.'s question (“Why is this even debatable?”) – I’m not a math major, but here’s my take.

A lot of mathematics is intuitive, and that’s no accident. There’s usually an attempt to match up with either a physical phenomena or at least to make things work on a simple and easily understood level. For example, it’s good to have the concept of addition actually correspond to what we perceive as addition, i.e., two + two = four lets us use arithmetic to know[sup]*[/sup] that two monkeys + two monkeys = four monkeys. If instead, a+b = ‘one more than a’ it would not have much (if any) practical use. So we use the mathematics that fits with what we know.

There’s often some point, though, at which things become less intuitive. Infinity is naturally going to be one of those; by its nature it doesn’t have a knowable correspondence with a physical situation. That’s exactly the sort of thing that confuses us in this case. We know that if anyone actually sat down and starting throwing the balls in the urn (and knowing that a person – or an imp – can only put in or remove balls in a finite amount of time) that we would never see the number of balls in the urn shrink.

In order to find out the answer, we ask the mathematicians. And yes, they do come up with a definite answer – sort of. What they say is “starting with this, using these definitions of sets, and limits, etc. you get this” and that answer could not be different. That’s something everyone can agree on [sup]**[/sup]. But in these cases, the answer goes against what we expect.

While nobody disagrees with one particular conclusion, there is real debate. If you look at ZenBeam’s first post in this thread, you’ll notice that there are academic papers written discussing this particular problem[sup]+[/sup]. There’s often papers that argue about a number of mathematical oddities (some of which arise as thread topics here). Not everyone agrees with the solution to the problem.

There’s probably two main causes for debate. In reference to a particular problem, there may be the question of what I’ll call ‘the model’ of the problem. Often a basic question, of great interest when attempting to apply mathematics, is whether or not the mathematical tools used are actually modelling the ‘physical’ (or in this case, the ‘stated’) problem. This is what’s called into question with the second formulation of the problem (the two urns, and relabelling of the balls) – are they in fact equivalent; and why or why not?

The other cause for debate is whether the math is good enough at all. In some way it’s related to physical correspondence but has to do with simplicity and ‘fitting in’ with the rest of mathematics. By good enough roughly what I mean is if despite its non-intuitive behavior in one case, does it follow intuitive behavior in other (simpler) cases? It’s a bit harder to define, and it can get a little wrapped up in technical details, but I suppose that’s why it becomes a topic for debate.

This is the reason why ultrafilter had to have a second long post about his definitions of convergence. He had to show that these generally fit the way convergence ‘should’ behave – in his words “why I think this is a good general notion of convergence for sequences of sets”. For example, I could, if I so desired, say that “all infinite sets converge to being empty”, and solve the problem - it’d look somewhat like ultrafilter’s solution, and it could not be argued that it does not show the urn empty at the end. However, it’s clear that such a definition of convergence is nonsense. It not only doesn’t fit our conception of what should happen to a sequence of sets, but it doesn’t allow some of the basic operations to work that make it a useful tool for math.

So despite the fact that mathematics proceeds in an orderly fashion to a single ‘right’ answer, it is the rigid definitions that shape the process that are called into question and the heart of many debates in mathematics; in more subtler cases, there are conflicting assumptions that both lead to ‘good’ results as we know now, but might be abandoned later.

[sup]*[/sup]According to common usage, but perhaps not by the strictest of epistemological standards.
[sup]**[/sup]Again, this raises a philosophical question (“why must there be universal agreement?”) that doubtless people are working on, but mostly we just accept that mathematics works the way it does because it does, or gives useful results, or whatever we like.

[sup]+[/sup]This is completely unrelated to the rest of my post, but in the paper by John Byl linked to, I noticed what looks like an error when he is attempting to reconcile the continuity conditions : “… assuming that any ball coming to rest at a position which it does not leave before noon is still at that position at noon, then all balls in the urn just before noon should still be there at noon …”

ultrafilter wrote

of course not.

Manduck , my point was, that the infinite numbers of balls are labeled to begin with, so all of them already have a meaningful label.

Imagine that the goblin doesnt discard/eat the ball, but puts it in another bucket. So if one says that the first bucket is empty after the infinite time, the second one has to have an infinite number of balls in it. What would be the labels on them then?

In a purely mathematical way I’d say that both buckets will contain an Infinite number of balls.

But as an answer to the riddle I’d say that the answer is “Who knows?” Because you never get around to check anyways because you are putting balls in the bucket till all eternity.

We are given as an initial condition that all the balls are numbered. The logic of the problem leads us to conclude that the gremlin takes out all the numbered balls, but we also have to conclude that an infinite number of balls remain, but they can’t be numbered. That violates one of our initial conditions, so that proves that one of the conditions must be wrong. Either there can’t be an infinite number of steps, or the balls can’t be numbered, or the imp or the player can’t behave as discribed.

If the answer with the smallest numbered ball removed is that there are an infinite number of non-integral balls remaining, then the consistent answer when removing the smallest composite number is that what is remaining is 1, all the primes, and an infinite number of non-integral balls. There’s no reason there can’t be both an infinite number of named balls, and an infinite number of non-named balls (if you accept non-named balls in the first place).

First, not having a limit is not the same as having a limit of zero. Second, it doesn’t matter that this sequence has no limit, because the question is not which balls are in the urn, but how many. Even though which balls are in urn B is not defined, is anyone here willing to say there is not an infinite number of balls in urn B?

Both Orbifold’s and ultrafilter definitions show that the numbers on the balls don’t converge, but we already know that. Again, the question is “how many?”, not “which?”. Their definitions can be used to deduce that an infinite number of balls remain. At each step, there can always be an enumeration of the balls in the urn, and there’s nothing which prevents us from using this enumeration, rather than the numbers printed on the balls. The simplest enumeration is to order them from lowest to highest. After the first step, there is always a first ball (the lowest numbered ball). After the second step, there is always a second ball, the second-lowest numbered ball. And so forth. For any n, there is always an nth ball, the nth-lowest numbered ball in the urn. Taking the limit as n approaches infinity gives us an infinite number of balls.

This is a very simple statement of the solution. I am sure it’s right on.

Thanks to all, especially ZenBeam!

ZenBeam: my definition shows that the set of balls in the urn approaches the null set, and no other. If you believe otherwise, either point out the error in my argument, or prove what you’re claiming.

The question is most definitely “which”, as the scenario in which the gremlin always removes the odd-numbered balls does result in an infinite number of balls left at the end (in the limit sense).

In fact, I can come up with a scenario where the contents of the urn converge to any S [symbol]Í[/symbol] N. Here’s how it goes:[ol]
[li]At each step, you put in the next two balls (starting with 0 and 1).[/li][li]The gremlin removes the lowest-numbered ball which is not in S.[/li][/ol]Using my definition, you can show that this sequence of sets converges to S, no matter what S is–N, [symbol]Æ[/symbol], {1}, or anything else.

No, the question has always been “how many”.

Your scenario removing composites is one case of this. I believe my answer there applies to the general case as well. That is, this doesn’t add anything new to the argument.

Your definition shows that there is a first ball in the limit set, and a second ball, and so forth. It may be that your definition needs to be tightened up a bit. Having the number of elements in each set in the sequence of steps which aren’t in the limit set approaching infinity doesn’t give the warmest feeling that things are converging.

Bricker, thanks for the thanks, but keep in mind there are three possible answers here: zero, infinity, or undefined. I believe zero is wrong, but undefined remains a possibility.

Please explain this to me in great detail.

So, if removing the highest ball results in an infinite set of balls, and removing the lowest ball results in zero balls, how many balls would remain if a random ball is removed?

All right, let me go through a detailed proof that which balls we take out are important. Assume we’ve got the setup in the OP, save that the gremlin is always removing the lowest-numbered ball whose label is in some set S. As always, every ball is labeled with an element of N, and there’s a ball corresponding to every natural number. We’ll also assume that there is no ball labeled 0, as in the OP. I’m also going to be a little sloppy about the distinction between a ball and its label, although I can correct that for interested parties.

So we start dropping balls in two at a time, and the gremlin is removing them one at a time. The question is, which balls are left after step n? Well, at most there are the first n elements of S (if S is N), and at worst, there are no elements left (if S has no elements less than n + 1, for instance). The key observation is that once the gremlin removes a ball, it never gets put back in. We can all agree on that, right?

There are two cases we need to consider, the case where S is infinite, and the case where S is finite.

In the case where S is infinite, let’s look at two sequences, <s[sub]n[/sub]> and <t[sub]n[/sub]>. <s[sub]n[/sub]> is the sequence of elements of S, and <t[sub]n[/sub]> is the sequence of elements of N - S.

When is s[sub]k[/sub] placed in the jar? Well, at the nth step, we’re putting in the balls 2n - 1 and 2n. If s[sub]k[/sub] is odd, we’re putting it in at step (s[sub]k[/sub] + 1)/2, and if it’s even, we’re putting it in at step s[sub]k[/sub]/2. As the gremlin only removes balls whose labels do not fall in S, s[sub]k[/sub] is never removed.

When is t[sub]k[/sub] removed from the jar? This is a little trickier, as that depends on S. So we’ll come up with an upper bound instead. At step t[sub]k[/sub], we have removed at most t[sub]k[/sub] - 1 balls from the jar. Every lower ball whose label is not in S has been removed by now. So t[sub]k[/sub] will be removed on step t[sub]k[/sub], if not earlier. It could be earlier, if S has a member lower than t[sub]k[/sub]. And as we noted before, every ball taken out is never put back in.

So by my definition, the sequence of sets of balls in the urn converges to S.

If S is finite, things are a little easier. S has a maximum element, [symbol]s[/symbol], which will be put in on step ([symbol]s[/symbol] + 1)/2 if [symbol]s[/symbol] is odd, and step [symbol]s[/symbol]/2 otherwise. After that, all elements of S are in every iteration. As before, t[sub]k[/sub] is removed by step t[sub]k[/sub], and never placed back in. Again, by my definition, the sequence of sets of balls in the urn converges to S.

That’s why you can’t just count the number of balls left. You have to know which ones are there.

Depends on which ones got pulled out. However, the probability that a finite number of balls is left works out to be zero. Why? Well, every probability is a measure, and the measure of a countable set is always zero, and there are a countable number of finite subsets of N.

ultrafilter- I could be wrong, but based on your conclusion, seems like it should be :
“the gremlin is always removing the lowest-numbered ball whose label is [not] in some set S.”

(So if S = empty, the urn contains S (i.e. is empty) at the end.)

The conclusion still makes sense.

Oops. Good catch.

ultrafilter wrote

Yes, but.l. What you’re saying is that the probability of pulling out a given ball, say ball #1403 approaches zero. If this is true (and I assume it is), then isn’t that logic true even if you’re pulling out the lower balls? I.e. if you have a big urn with every odd number in it, the odds of actually pulling out a given numbered ball is zero.

That is correct, but it’s not quite relevant. Measure theory gets to be pretty tricky, and you have to rely on proofs rather than intuition.

Actually, if you have a big urn with all the odd-numbered balls in it, the probability of pulling out a given ball is undefined. This stuff gets really nasty, really quickly.

While the sequence of steps is being executed, there is a lowest ball, which is taken to be the “first” ball, there is (after the second step) a second-lowest ball, the “second ball”, and so on. I didn’t want to say that in the limit set, the balls will necessarily be orderable, so I didn’t want to call them “lowest”, “second-lowest”, but they are the balls corresponding to the lowest, second-lowest, etc. balls in the sequence of sets of balls. Taking the balls in order in the sequence of steps isn’t important, it’s just an easy way of enumerating them.

ultrafilter, I said “It may be that your definition needs to be tightened up a bit.” Here’s a clearer example of why I think this: Suppose I have a sequence of sets, S[sub]n[/sub], n = 1,2,…, each of which consists of two numbers: 1/(n+2) and 1 - 1/(n+2). Your definition of the limit of this sequence of sets gives me the null set, since no number ever appears more than one time. Therefore the number of elements in the limit set is zero. This is highly counterintuitive since both the number of elements and what they should be seems to be very well defined.

While the sequence of steps is being executed, there is a lowest ball, which is taken to be the “first” ball, there is (after the second step) a second-lowest ball, the “second ball”, and so on. I didn’t want to say that in the limit set, the balls will necessarily be orderable, so I didn’t want to call them “lowest”, “second-lowest”, but they are the balls corresponding to the lowest, second-lowest, etc. balls in the sequence of sets of balls. Taking the balls in order in the sequence of steps isn’t important, it’s just an easy way of enumerating them.**
[/quote]

Every ball in the limit set has to be put in at some point. We’re only putting balls in whose labels have natural numbers. Therefore, the limit set is a subset of the natural numbers, which is a well-ordered set (meaning that every non-empty subset has a least member). So if the limit set is non-empty, there definitely is a ball with lowest label.

**

If no number ever appears more than once, you have convergence to the null set. It may not be desirable or intuitive, but that’s what you get. My definition is well-defined and preserves important operations, which is good. Not only that, but Orbifold’s definition, which is standard, gives the same result.

Remember, when you’re talking to a mathematician, you’re not generally talking to someone who cares whether something behaves intuitively. They only care that its nature is well-defined. Ever heard of the Banach-Tarski paradox?

Sorry for the delay; real life has been intruding. (Although I see you’ve got the 0.999… != 1 folks to keep you busy. :wink: ) Anyway…

Yeah, it’s been covered here. I’m not sure of the relevance here, though. I can qualitatively see how that could be done.

To put it in a “balls and Gremlins” form, assume the Gremlin starts with a stick of length unity. At the first step, he divides it into two sticks of lengths 1/3 and 2/3. At the next step he cuts a bit off the shorter piece and adds it to the longer piece so he has two sticks of length 1/4 and 3/4. At the next step, the sticks are 1/5th and 4/5ths, and so forth. If I ask how many sticks he has after an infinite number of steps, and what the total length is, are you saying the answers are no sticks (since we’ve converged to the null set), and zero total length (since there are no sticks)?