## Infinite Balls and Jugs

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

### Infinite Balls and Jugs

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.

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.
Last edited by mike-l on Thu Sep 17, 2009 8:16 pm UTC, edited 1 time in total.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: Infinite Balls and Jugs

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
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Infinite Balls and Jugs

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
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Lostuser137
Posts: 2
Joined: Fri Sep 18, 2009 5:26 am UTC

### Re: Infinite Balls and Jugs

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
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Infinite Balls and Jugs

Lostuser137 wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

itaibn
Posts: 140
Joined: Mon Dec 29, 2008 7:06 pm UTC

### Re: Infinite Balls and Jugs

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.
I NEVER use all-caps.

Caesar
Posts: 61
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

### Re: Infinite Balls and Jugs

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
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

### Re: Infinite Balls and Jugs

What about the version where at each step I:

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.
Last edited by Macbi on Sat Sep 19, 2009 5:08 pm UTC, edited 1 time in total.
Indigo is a lie.
Which idiot decided that websites can't go within 4cm of the edge of the screen?
There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

Vicious Chicken
Posts: 13
Joined: Mon Sep 24, 2007 4:02 pm UTC

### Re: Infinite Balls and Jugs

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
Ormurinn's Alt
Posts: 1874
Joined: Sat Jun 13, 2015 4:26 pm UTC
Location: The wrong side of the mirror
Contact:

### Re: Infinite Balls and Jugs

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/m3. 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*106 < 0.5 * 1*10-15 * (250mm/x)2 * c / ( c - (250mm/x)) for the tiny "dust particle" balls

or

4.184*106 < 0.5 * 5*10-4 * (250mm/x)2 * 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)2 * c / ( c - (250mm/x))
= 0.5 * 1*10-15 * (250mm/1ns)2 * c / ( c - (250mm/1ns))
= 5*10-16 * (2.5*108)2 * c / ( c - 2.5*108)
= 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?
Oh, Willie McBride, it was all done in vain.

Schrödinger's Wolves
Posts: 14
Joined: Fri Mar 24, 2017 3:28 am UTC

### Re: Infinite Balls and Jugs

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
Posts: 60
Joined: Fri Jun 15, 2007 2:33 am UTC
Location: Multiple Places (only one now that you read this...)

### Re: Infinite Balls and Jugs

Schrödinger's Wolves wrote: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 Hn where Hn 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
Posts: 14
Joined: Fri Mar 24, 2017 3:28 am UTC

### Re: Infinite Balls and Jugs

Poker wrote:
Schrödinger's Wolves wrote: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 Hn where Hn 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.