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

Postby mike-l » Thu Sep 17, 2009 6:14 pm UTC

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.
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

Postby douglasm » Thu Sep 17, 2009 7:51 pm UTC

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

Postby mike-l » Thu Sep 17, 2009 8:16 pm UTC

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 :P
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

Postby Lostuser137 » Fri Sep 18, 2009 5:35 am UTC

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.

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

Re: Infinite Balls and Jugs

Postby jestingrabbit » Fri Sep 18, 2009 6:06 am UTC

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: 137
Joined: Mon Dec 29, 2008 7:06 pm UTC

Re: Infinite Balls and Jugs

Postby itaibn » Sat Sep 19, 2009 5:39 am UTC

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: 60
Joined: Fri Oct 24, 2008 12:34 am UTC
Location: Germany

Re: Infinite Balls and Jugs

Postby Caesar » Sat Sep 19, 2009 3:38 pm UTC

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?

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

Re: Infinite Balls and Jugs

Postby Macbi » Sat Sep 19, 2009 5:03 pm UTC

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.
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

Postby Vicious Chicken » Sun Sep 20, 2009 3:31 am UTC

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...

User avatar
Sableagle
Ormurinn's Alt
Posts: 1117
Joined: Sat Jun 13, 2015 4:26 pm UTC
Location: The wrong side of the mirror
Contact:

Re: Infinite Balls and Jugs

Postby Sableagle » Sun Oct 23, 2016 9:26 am UTC

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

Postby Schrödinger's Wolves » Thu Mar 30, 2017 8:35 pm UTC

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

Re: Infinite Balls and Jugs

Postby Poker » Fri Mar 31, 2017 4:58 am UTC

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

Postby Schrödinger's Wolves » Fri Mar 31, 2017 5:02 am UTC

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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 4 guests