Infinite Balls and Jugs

[mike-l]

Suppose I have infinitely many balls, numbered 1,2,.. and so on.

At 10 minutes to midnight, I put balls 1-10 in the jug, and remove a ball. At 5 minutes to midnight I put balls 11-20 in the jug and remove a ball. At 2.5 minutes to midnight, etc (halving the time between insertions ad infinitum, putting the next 10 balls numerically in the jug each time).

How many balls are in the jug at midnight if:

a) I always remove the lowest numbered ball
b) I always remove the highest numbered ball
c) I remove balls uniformly at random.

Solution thread.

Hints:

Spoiler:

The answers are not all the same.

Spoiler:

The balls are numbered. If there are balls at midnight, which ones are they?

Spoiler:

Some math is required to figure out whether c is the same as a or the same as b. Uniform is important.

[douglasm]

What order do you add the balls in? I assume in ascending numerical order starting at 1, but you need to state that for a problem like this.

Can a removed ball ever be added back in, or are the removed balls kept in a separate group and never used again?

Both of these details are rather important to the problem.

[mike-l]

Edited the original post to make it more precise.

Since the problem is posed to be fun, if something is ambiguous, solve it both ways for twice the fun

[Lostuser137]

Well, That depends on how many times you halve the time, if you keep it reasonable, (lets say only interacting with the jug 5 times) you'd come up with one number.

But, if you were to keep halving until you were getting into mili-secs, you'd end up with an entirely different number, which, would be far larger.

[jestingrabbit]

Well, That depends on how many times you halve the time, if you keep it reasonable, (lets say only interacting with the jug 5 times) you'd come up with one number.

But, if you were to keep halving until you were getting into mili-secs, you'd end up with an entirely different number, which, would be far larger.

I believe that the idea is that we're interacting with the jug an infinity of times, otherwise the answers to a, b and c are all the same ie 9n where n is the number of times that we add 10 and remove 1.

[itaibn]

One possibility:

Spoiler:

At midnight the jar explodes and an infinite number of balls come out. You try to read the number on one of them, but the handwriting is too small to see anything.

What I believe:

Spoiler:

It is impossible to fit any arbitrarilly large number of balls in a jar, especially when you do it arbitrarilly quickly.

[Caesar]

I understand the solution (I even got it myself) but it's still hurting my brain. This seems like a problem you can't approach with a limit but with set theory. Is there a guideline to easily recognize what kind of infinity we're talking about in a given problem? If you know what I mean?

[Macbi]

What about the version where at each step I:

Add the next ten balls.
Find the ball with the lowest number in the urn, and find the ball with the highest number in the urn.
Swap the numbers on these two balls, removing all traces of the original number.
Put the two balls back in the urn.
Remove the...
A)ball which now has the highest number
B)ball which now has the lowest number

EDIT: Or rather, suppose the numbers are on stickers that I swap. The paradox being that

Spoiler:

under the current logic we end up with an urn full of balls but which contains no stickers, or vice-versa, even though each ball always has an associated sticker.

[Vicious Chicken]

A slight variation to case A:

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

[Sableagle]

Assuming you're using this jug, you've got 1 litre of space. Balls don't space-fill, so they have to have less than a decilitre of volume each. The puzzle doesn't specify a minimum size beyond what can be read and manipulated, and doesn't rule out the use of a microscope to do this, so your minimum size may be around 10 microns in diameter. This gives us quite a range of possibilities, from 10 microns up to maybe 40 millimetres. We also don't know the density, but can make assumptions: the balls have higher density than air and are not undergoing radioactive decay at high enough rate to prevent you completing this weird activity you have invented. Let's call that 2 to 15 kg/m³. This gives a mass range of 1*10^-15 to 5*10^-4 kg. The bottom-most ball in the jug has to move 250mm to be moved into the jug. The time available (x) in which to do this is decreasing.

1kg of TNT yields 4184000 J of energy. Assuming that the jug is unable to withstand the release of this much energy within in, a point will come when:

4.184*10⁶ < 0.5 * 1*10^-15 * (250mm/x)² * c / ( c - (250mm/x)) for the tiny "dust particle" balls

or

4.184*10⁶ < 0.5 * 5*10^-4 * (250mm/x)² * c / ( c - (250mm/x)) for the larger "ping pong" balls

Determining the value range for x is left as a rather dull exercise for the reader.

When x is more than the time between insertions of ten balls into the jug, the jug explodes.

If the jug is stronger, the lower limit on x will be smaller. Continuing to the point where x reaches the reciprocal of 1.2 GHz is not recommended.

At x = 1ns, for example,
0.5 * 1*10^-15 * (250mm/x)² * c / ( c - (250mm/x))
= 0.5 * 1*10^-15 * (250mm/1ns)² * c / ( c - (250mm/1ns))
= 5*10^-16 * (2.5*10⁸)² * c / ( c - 2.5*10⁸)
= 488498133082605467.9 J
= 116.754 MT TNT,

and at that point the jug doesn't really matter.

Disclaimer: I'm sober, so the maths is a load of bollocks and I'm out by several orders of magnitude, I know, but you still don't want to be throwing ten balls into a jug in under one nanosecond, do you?

[Schrödinger's Wolves]

Suppose I have infinitely many balls, each labelled with a different specification for a Turing machine(of which there are countably many) so that I have all the Turing Machines ordered in some easily specifiable way. I set the value N to 1 and turn my attention toward the first TM. At 10 minutes, then 5 minutes, then 2.5 minutes till midnight and so on, I perform the following action. I iterate the TM I am paying attention to and put its corresponding ball into the jug if it halts. Then, I turn my attention toward the next TM in the order that has not halted yet, unless I just iterated TM#N, in which case I add one to N and turn my attention to the first TM in the order that has not halted yet. At midnight, which balls will be in the jug?

I'd really like to know.

[Poker]

Suppose I have infinitely many balls, each labelled with a different specification for a Turing machine(of which there are countably many) so that I have all the Turing Machines ordered in some easily specifiable way. I set the value N to 1 and turn my attention toward the first TM. At 10 minutes, then 5 minutes, then 2.5 minutes till midnight and so on, I perform the following action. I iterate the TM I am paying attention to and put its corresponding ball into the jug if it halts. Then, I turn my attention toward the next TM in the order that has not halted yet, unless I just iterated TM#N, in which case I add one to N and turn my attention to the first TM in the order that has not halted yet. At midnight, which balls will be in the jug?

I'd really like to know.

Spoiler:

The balls placed in the jug should be the limit as n approaches infinity of the sequence of sets H_n where H_n is the set of all Turing Machines that halt after n steps. This limit should be the set of all Turing Machines that halt after a finite number of steps. If you're worried about the fact that you've just solved the Halting Problem by doing this, you had to take an infinite number of steps to do it, which should resolve the apparent contradiction.

[Schrödinger's Wolves]

Suppose I have infinitely many balls, each labelled with a different specification for a Turing machine(of which there are countably many) so that I have all the Turing Machines ordered in some easily specifiable way. I set the value N to 1 and turn my attention toward the first TM. At 10 minutes, then 5 minutes, then 2.5 minutes till midnight and so on, I perform the following action. I iterate the TM I am paying attention to and put its corresponding ball into the jug if it halts. Then, I turn my attention toward the next TM in the order that has not halted yet, unless I just iterated TM#N, in which case I add one to N and turn my attention to the first TM in the order that has not halted yet. At midnight, which balls will be in the jug?

I'd really like to know.

Spoiler:

The balls placed in the jug should be the limit as n approaches infinity of the sequence of sets H_n where H_n is the set of all Turing Machines that halt after n steps. This limit should be the set of all Turing Machines that halt after a finite number of steps. If you're worried about the fact that you've just solved the Halting Problem by doing this, you had to take an infinite number of steps to do it, which should resolve the apparent contradiction.

I understand that I solved the Halting Problem, that was the point. That's why I said "I'd really like to know.", since solving the Halting Problem would obviously be invaluable. I was showing one of the more extreme problems with this kind of supertask working in the real world, as it is very possible that whatever computer runs the universe would be literally unable to simulate this.