Marble Dropping
Moderators: jestingrabbit, Moderators General, Prelates
Marble Dropping
Hey, this is my first nonhowareyougoing style post. I hope it is appropriate:
You have two identical glass marbles and a 100 storey building. You want to find out the highest floor in the building that you can drop marbles off without them breaking using the fewest number of drops.
After dropping a marble, if it breaks you can't use it any more. If it survives, then it isn't weakened or anything like that, so you will always get the same result if you drop a marble from the same floor.
EDIT:
Solution/spoiler discussion: http://forums.xkcd.com/viewtopic.php?t=201
You have two identical glass marbles and a 100 storey building. You want to find out the highest floor in the building that you can drop marbles off without them breaking using the fewest number of drops.
After dropping a marble, if it breaks you can't use it any more. If it survives, then it isn't weakened or anything like that, so you will always get the same result if you drop a marble from the same floor.
EDIT:
Solution/spoiler discussion: http://forums.xkcd.com/viewtopic.php?t=201
Last edited by Andy on Tue Aug 29, 2006 1:15 pm UTC, edited 1 time in total.
Hmm, I don't really understand how you can be very efficient here. You could go up in twos, and if your marble breaks you simply go down a level and test the other marble although that might leave you with two broken marbles, you will know where they break, but I don't see how you can do any better, unless theres something you're missing.
 Torn Apart By Dingos
 Posts: 817
 Joined: Thu Aug 03, 2006 2:27 am UTC
Are we looking for the best average case or the best worst case?
I guess it's okay to break both if that'll tell you what storey you're looking for? If not, you could only use the first marble and try floors 1,2,3,4,5... in order.
If there were infinitely many floors, I'd probably do this: try the first marble on floors 2^n, until it breaks, and then use the second marble to try consecutive floors from the last floor that was okay. If I do this with 100 floors, and try the hypothetical floor 128 if I have to, where I assume it will break, it'd take an average of 17.97 tries, and a worst case of 42. That's not so good.
But there's certainly better than that for 100 floors... one being trying floors 10,20,30,...,100 with the first marble and then trying floor by floor with the second marble. Worst case 18, average 10.
I'll have to think about it some more.
I guess it's okay to break both if that'll tell you what storey you're looking for? If not, you could only use the first marble and try floors 1,2,3,4,5... in order.
If there were infinitely many floors, I'd probably do this: try the first marble on floors 2^n, until it breaks, and then use the second marble to try consecutive floors from the last floor that was okay. If I do this with 100 floors, and try the hypothetical floor 128 if I have to, where I assume it will break, it'd take an average of 17.97 tries, and a worst case of 42. That's not so good.
But there's certainly better than that for 100 floors... one being trying floors 10,20,30,...,100 with the first marble and then trying floor by floor with the second marble. Worst case 18, average 10.
I'll have to think about it some more.
 Torn Apart By Dingos
 Posts: 817
 Joined: Thu Aug 03, 2006 2:27 am UTC
I've got another solution, but unfortunately it wasn't better than my last one. It was easier to analyze, though (I used Python to calculate averages with my two first methods).
It seems the only scheme you can use is to try to exclude as many floors as possible with the first marble, and use the second marble floorbyfloor. If we first try floor above floor n_1 (*), then the floor above n_1+n_2, then the floor above n_1+n_2+n_3, etc, the number of tries we need are in this list:
[2,3,...,n_1,1; 3,4,...,n_2,2; 4,5,...,n_3,3; ...]
(the nth element in the list is the number of tries we need if floor n is the first floor from which the marble will break).
I thought it was natural to give each segment the same average, so I tried with n_1 = 19, n_2 = 18, n_3 = 17, ..., n_10 = 10. Then we have 10 segments, each with average 10, so the average number of tries is 10, and the worst case is 19.
Apparently there are better choices for n_k (my earlier post had a better worstcase), but now it's clearer how to find the solution.
EDIT:
(*) Actually, my convoluted explanation of n_k isn't quite right. If you can make out from the list what it represents, you've got it. I'll maybe fix this later.
It seems the only scheme you can use is to try to exclude as many floors as possible with the first marble, and use the second marble floorbyfloor. If we first try floor above floor n_1 (*), then the floor above n_1+n_2, then the floor above n_1+n_2+n_3, etc, the number of tries we need are in this list:
[2,3,...,n_1,1; 3,4,...,n_2,2; 4,5,...,n_3,3; ...]
(the nth element in the list is the number of tries we need if floor n is the first floor from which the marble will break).
I thought it was natural to give each segment the same average, so I tried with n_1 = 19, n_2 = 18, n_3 = 17, ..., n_10 = 10. Then we have 10 segments, each with average 10, so the average number of tries is 10, and the worst case is 19.
Apparently there are better choices for n_k (my earlier post had a better worstcase), but now it's clearer how to find the solution.
EDIT:
(*) Actually, my convoluted explanation of n_k isn't quite right. If you can make out from the list what it represents, you've got it. I'll maybe fix this later.
Last edited by Torn Apart By Dingos on Mon Aug 28, 2006 5:07 pm UTC, edited 1 time in total.
 RealGrouchy
 Nobody Misses Me As Much As Meaux.
 Posts: 6704
 Joined: Thu May 18, 2006 7:17 am UTC
 Location: Ottawa, Ontario, Canada
 Contact:
Is it implied that the marble won't break when dropped from the first storey, and will break from the 100th?
Not sure if it matters, but it keeps my simple brain occupied.
 RG>
Not sure if it matters, but it keeps my simple brain occupied.
 RG>
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
RealGrouchy wrote:Is it implied that the marble won't break when dropped from the first storey, and will break from the 100th?
Not sure if it matters, but it keeps my simple brain occupied.
 RG>
It's not implied that it will break from the 100th, but it seems to be implied that it will not break from the 1st (since it seems to imply such a floor exists). I'm going to assume that it can break from the first, though.
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
ulnevets wrote:what if you give it a very slight upward velocity?
then it wouldn't be counted as a drop.
i win.
That doesn't actually change anything; the amount gravity accelerates it downwards while it gets to the peak is precisely countered by the acceleration it takes to get back down, so tossing it up is exactly the same as tossing it down with the same force.
Shoofle wrote:ulnevets wrote:what if you give it a very slight upward velocity?
then it wouldn't be counted as a drop.
i win.
That doesn't actually change anything; the amount gravity accelerates it downwards while it gets to the peak is precisely countered by the acceleration it takes to get back down, so tossing it up is exactly the same as tossing it down with the same force.
nonono
i mean, a drop is defined as starting with zero velocity
 RealGrouchy
 Nobody Misses Me As Much As Meaux.
 Posts: 6704
 Joined: Thu May 18, 2006 7:17 am UTC
 Location: Ottawa, Ontario, Canada
 Contact:
That's rediculous. Presumably, you have to lift the marble to some degree, and when you drop it, it will be from zero vertical velocity.
If you throw it up, it will reach zero vertical velocity and continue to accelerate downwards...
Oh, I give up. I'm really too tired to be discussing marble droppings.
 RG>
If you throw it up, it will reach zero vertical velocity and continue to accelerate downwards...
Oh, I give up. I'm really too tired to be discussing marble droppings.
 RG>
Jack Saladin wrote:etc., lock'd
Mighty Jalapeno wrote:At least he has the decency to REMOVE THE GAP BETWEEN HIS QUOTES....
Sungura wrote:I don't really miss him. At all. He was pretty grouchy.
RealGrouchy wrote:That's rediculous. Presumably, you have to lift the marble to some degree, and when you drop it, it will be from zero vertical velocity.
If you throw it up, it will reach zero vertical velocity and continue to accelerate downwards...
Oh, I give up. I'm really too tired to be discussing marble droppings.
 RG>
you guys don't understand
when you drop something, it leaves your hand at zero velocity. throwing it upwards slightly would be considered a throw, and any amount of these are allowed.
if you're concerned with the slight upward velocity, you could always move your hand a little lower to account for it.
xkcd wrote:ulnevets wrote:Jesster wrote:Even if it wouldn't be counted as a drop, you would still have two broken marbles.
strategy: start at bottom floor and move up one at a time until it breaks. best case: 0 drops. worst case: 0 drops.
Why do people always forget the worst case of "raptor attack"?
would it be worse if the raptors had magic powers?
 hassellhoff
 Posts: 30
 Joined: Mon Jul 28, 2008 8:40 am UTC
 Contact:
Re: Marble Dropping
gah..
i was hoping for a little riddle i could do at 4 in the morning.. but then i see 1 guy had to use python.
i give up
consolation prize?
i was hoping for a little riddle i could do at 4 in the morning.. but then i see 1 guy had to use python.
i give up
consolation prize?
Exenon wrote: I play Call of Duty. That's for real men !
Re: Marble Dropping
therapist wrote:gah..
i was hoping for a little riddle i could do at 4 in the morning.. but then i see 1 guy had to use python.
i give up
consolation prize?
The prize is a smack in the head for dragging up a two year old thread and adding nothing.
Peshmerga wrote:A blow job would probably get you a LOT of cheeseburgers.
But I digress.
Re: Marble Dropping
first marble, try: 10, 20, 30, ... 100.
If it is still unbroken, then the answer is 100.
If it breaks at any point, then go back down 9 floors, and go up oneata time until it breaks.
If it does, then the floor under that is the solution.
If it does not break, then the last floor tried is the solution.
Coupla scenarios:
10,20,30,40,(break), 31,32,33,34,35 (break) => answer: 24 (9 tries)(also, the avg. number of tries need to solve with this solution.)
10,20,30,40,50,60,70,80,90,100 (no break) => answer: 100 (10 tries)
1 (break) => answer: 0 (1 try)(min solution)
10,20,30,40,50,60,70,80,90,100 (break),91,92,93,94,95,96,97,98,99 => answer: 99 (18 tries)(also, the max tries need to find a solution.)
We could try different ways to break up the floors, but I think this is optimal because we have equalized the max number of tries for the first marble and second marble (9 tries). Any solution using more floors for the first marble (and less tries), would result in more tries for the second marble. I'm not smart enough to "proof" this. Or maybe I'm just lazy.
If it is still unbroken, then the answer is 100.
If it breaks at any point, then go back down 9 floors, and go up oneata time until it breaks.
If it does, then the floor under that is the solution.
If it does not break, then the last floor tried is the solution.
Coupla scenarios:
10,20,30,40,(break), 31,32,33,34,35 (break) => answer: 24 (9 tries)(also, the avg. number of tries need to solve with this solution.)
10,20,30,40,50,60,70,80,90,100 (no break) => answer: 100 (10 tries)
1 (break) => answer: 0 (1 try)(min solution)
10,20,30,40,50,60,70,80,90,100 (break),91,92,93,94,95,96,97,98,99 => answer: 99 (18 tries)(also, the max tries need to find a solution.)
We could try different ways to break up the floors, but I think this is optimal because we have equalized the max number of tries for the first marble and second marble (9 tries). Any solution using more floors for the first marble (and less tries), would result in more tries for the second marble. I'm not smart enough to "proof" this. Or maybe I'm just lazy.
Re: Marble Dropping
You can do it in 15. There's an answers thread with the answer posted, along with much more difficult math. I was happy about solving an unsolved puzzle until I realized this. At least I got the answer right
Re: Marble Dropping
crzftx wrote:You can do it in 15. There's an answers thread with the answer posted, along with much more difficult math. I was happy about solving an unsolved puzzle until I realized this. At least I got the answer right
Actually you can do it in 14
"Everything I need to know about parenting I learned from cooking. Don't be afraid to experiment, and eat your mistakes."  Cronos
Re: Marble Dropping
14?
How was this possible. I guess I may not have understood the answer then. I thought you could take the first marble first by 14 floors, then 13, etc. The other marble would then go 1 by 1 as needed to figure out which floor it is. This method can take up to 15 tries. It'd be 15 if the critical floor is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, or 99.
I guess it only takes 14, since I don't need to break both marbles, necessarily, to find the floor. Oops.
I guess it only takes 14, since I don't need to break both marbles, necessarily, to find the floor. Oops.
Re:
ulnevets wrote:RealGrouchy wrote:That's rediculous. Presumably, you have to lift the marble to some degree, and when you drop it, it will be from zero vertical velocity.
If you throw it up, it will reach zero vertical velocity and continue to accelerate downwards...
Oh, I give up. I'm really too tired to be discussing marble droppings.
 RG>
you guys don't understand
when you drop something, it leaves your hand at zero velocity. throwing it upwards slightly would be considered a throw, and any amount of these are allowed.
if you're concerned with the slight upward velocity, you could always move your hand a little lower to account for it.
He's right you know...
Last I checked I don't drop a basket ball, or baseball. They all reach zero vertical velocity. Granted their parabolic paths are much larger than in the marble dropping experiment. As far as this experiment, the only way I can come up with this being feasible is making a contraption out of cardboard toilet paper rolls, some scotch tape, 3 feet of floss, 3 cotton balls and 5 straws. 'Taint any rules abou' that!
Re: Marble Dropping
Due to very fierce winds, your hand gets cut off if you try to make a measurement without dropping the marble.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
 Penitent87
 Posts: 28
 Joined: Wed Apr 15, 2009 2:30 am UTC
 Location: London
Re: Marble Dropping
afarnen wrote:Spoiler:
I think you forgot to look carefully enough at the final few marbles in some lists. You just kept the pattern going instead of actually thinking about it. (e.g. the number of marble drops required to identify the 100th floor, given an increment of 9, is 12, not 13. 9,18,27,36,45,54,63,72,81,90,99,100.) These alterations mean that 9, 10, and 11 all have the same average case of 10.9 drops.

 Posts: 1
 Joined: Mon Jun 29, 2009 10:40 pm UTC
Re: Marble Dropping
May we assume that the building is of such a height that the marble, having been dropped from a height below the top floor, will not reach terminal velocity? Otherwise, we could optimize our algorithm given the height of each floor, the force of air resistance on the marble, and the force of gravity by determining the highest floor which it even makes sense to try (since all higher floors would presumably yield the same result).
Re: Marble Dropping
This is a pretty easy problem, and you can even generalize it to an arbitrary number of marbles.
Spoiler:
Re: Marble Dropping
That isn't the solution for worst case.Soljer wrote:This is a pretty easy problem, and you can even generalize it to an arbitrary number of marbles.Spoiler:
Spoiler:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Who is online
Users browsing this forum: Yahoo [Bot] and 2 guests