Marble Dropping

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Andy
Posts: 45
Joined: Mon Aug 28, 2006 10:23 am UTC

Marble Dropping

Postby Andy » Mon Aug 28, 2006 10:47 am UTC

Hey, this is my first non-how-are-you-going 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
Last edited by Andy on Tue Aug 29, 2006 1:15 pm UTC, edited 1 time in total.

User avatar
mister k
Posts: 643
Joined: Sun Aug 27, 2006 11:28 pm UTC
Contact:

Postby mister k » Mon Aug 28, 2006 12:02 pm UTC

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.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Postby Torn Apart By Dingos » Mon Aug 28, 2006 1:26 pm 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.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Postby Torn Apart By Dingos » Mon Aug 28, 2006 2:09 pm 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 floor-by-floor. 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 worst-case), 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.

User avatar
RealGrouchy
Nobody Misses Me As Much As Meaux.
Posts: 6704
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada
Contact:

Postby RealGrouchy » Mon Aug 28, 2006 3:51 pm UTC

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

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Postby GreedyAlgorithm » Mon Aug 28, 2006 10:21 pm UTC

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 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
ulnevets
Posts: 186
Joined: Wed Aug 09, 2006 1:45 am UTC
Contact:

Postby ulnevets » Tue Aug 29, 2006 5:03 am UTC

what if you give it a very slight upward velocity?


then it wouldn't be counted as a drop.



i win.

User avatar
Shoofle
Posts: 409
Joined: Sun Apr 09, 2006 9:28 pm UTC
Location: Location, Location.
Contact:

Postby Shoofle » Tue Aug 29, 2006 12:44 pm UTC

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.

Andy
Posts: 45
Joined: Mon Aug 28, 2006 10:23 am UTC

Postby Andy » Tue Aug 29, 2006 1:18 pm UTC

Are we looking for the best average case or the best worst case?

Sorry, we were optimising the worst case.

User avatar
ulnevets
Posts: 186
Joined: Wed Aug 09, 2006 1:45 am UTC
Contact:

Postby ulnevets » Tue Aug 29, 2006 5:12 pm UTC

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

User avatar
RealGrouchy
Nobody Misses Me As Much As Meaux.
Posts: 6704
Joined: Thu May 18, 2006 7:17 am UTC
Location: Ottawa, Ontario, Canada
Contact:

Postby RealGrouchy » Wed Aug 30, 2006 2:43 am UTC

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

User avatar
ulnevets
Posts: 186
Joined: Wed Aug 09, 2006 1:45 am UTC
Contact:

Postby ulnevets » Wed Aug 30, 2006 3:02 am UTC

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.

User avatar
Jesse
Vocal Terrorist
Posts: 8635
Joined: Mon Jul 03, 2006 6:33 pm UTC
Location: Basingstoke, England.
Contact:

Postby Jesse » Wed Aug 30, 2006 7:47 am UTC

Even if it wouldn't be counted as a drop, you would still have two broken marbles.

User avatar
ulnevets
Posts: 186
Joined: Wed Aug 09, 2006 1:45 am UTC
Contact:

Postby ulnevets » Wed Aug 30, 2006 2:54 pm UTC

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.

User avatar
xkcd
Site Ninja
Posts: 365
Joined: Sat Apr 08, 2006 8:03 am UTC
Contact:

Postby xkcd » Wed Aug 30, 2006 5:19 pm UTC

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"?

User avatar
Jesse
Vocal Terrorist
Posts: 8635
Joined: Mon Jul 03, 2006 6:33 pm UTC
Location: Basingstoke, England.
Contact:

Postby Jesse » Wed Aug 30, 2006 7:30 pm UTC

Because they are uninformed. Also, at what speed can raptors climb stairs?

Ooh, new problem. At what height does a dropped marble gain maximum raptor killing velocity?

Penguin
Posts: 98
Joined: Wed Jul 05, 2006 2:54 pm UTC
Location: Cambridge, MA
Contact:

Postby Penguin » Wed Aug 30, 2006 7:33 pm UTC

I like this game better! What is the minimum floor you have to drop a marble from to kill a raptor?

If the marble doesn't break, you get a bonus!
<3!

User avatar
Jesse
Vocal Terrorist
Posts: 8635
Joined: Mon Jul 03, 2006 6:33 pm UTC
Location: Basingstoke, England.
Contact:

Postby Jesse » Wed Aug 30, 2006 7:39 pm UTC

Although, the marble wouldn't be retrievable.

Don't forget, raptors are intelligent and one would be hiding around the corner until you came to retrieve them.

User avatar
ulnevets
Posts: 186
Joined: Wed Aug 09, 2006 1:45 am UTC
Contact:

Postby ulnevets » Wed Aug 30, 2006 9:27 pm UTC

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?

User avatar
Jesse
Vocal Terrorist
Posts: 8635
Joined: Mon Jul 03, 2006 6:33 pm UTC
Location: Basingstoke, England.
Contact:

Postby Jesse » Wed Aug 30, 2006 9:39 pm UTC

They already do.

User avatar
hassellhoff
Posts: 30
Joined: Mon Jul 28, 2008 8:40 am UTC
Contact:

Re: Marble Dropping

Postby hassellhoff » Mon Aug 04, 2008 11:06 am UTC

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?
Exenon wrote: I play Call of Duty. That's for real men ! :mrgreen:

User avatar
hyperion
"I'll show ye...."
Posts: 1569
Joined: Wed Nov 29, 2006 2:16 pm UTC
Location: Perth

Re: Marble Dropping

Postby hyperion » Mon Aug 04, 2008 11:23 am UTC

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.

Crosby
Posts: 21
Joined: Tue Aug 05, 2008 6:46 pm UTC

Re: Marble Dropping

Postby Crosby » Tue Aug 05, 2008 7:38 pm UTC

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 one-at-a 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.

crzftx
Posts: 371
Joined: Tue Jul 29, 2008 4:49 am UTC
Location: Rockford, IL

Re: Marble Dropping

Postby crzftx » Wed Aug 06, 2008 9:24 am UTC

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

User avatar
BoomFrog
Posts: 1069
Joined: Mon Jan 15, 2007 5:59 am UTC
Location: Seattle

Re: Marble Dropping

Postby BoomFrog » Wed Aug 06, 2008 11:52 am UTC

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


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

crzftx
Posts: 371
Joined: Tue Jul 29, 2008 4:49 am UTC
Location: Rockford, IL

Re: Marble Dropping

Postby crzftx » Wed Aug 13, 2008 7:35 pm UTC

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.

afarnen
Posts: 157
Joined: Mon May 05, 2008 12:12 pm UTC

Re: Marble Dropping

Postby afarnen » Thu Aug 14, 2008 4:10 am UTC

Spoiler:

Code: Select all

using the increment algorithm where you go up by n stories, starting with n, and when the first marble breaks, you go up starting at one plus the last story at which the first marble survived the fall, here's a graph i made:

example: 10, 20, 30 (break), 21, 22, 23 (break).. that's 6 drops

         increment
       +----------
#      | 1 2 3 4 5
   +---+----------
d  | 1 | 1 2 2 2 2
r  | 2 | 2 2 3 3 3
o  | 3 | 3 3 3 4 4
p  | 4 | 4 3 3 4 5
s  | 5 | 5 4 4 3 5

inc.  avg drops  pattern
---------------------------------------------
1     50.5       1,2..100
2     26.5       2,2,3,3..51,51
3     18.83      2,3,3,3,4,4..34,35,35,35
4     15.25      2,3,4,4,3,4,5,5..26,27,28,28
5     13.3       2,3,4,5,5,3,4,5,6,6..21,22,23,24,24
6     12.14      2,3,4,5,6,6,3,4,5,6,7,7..17,18,19,20,21,21,18,19,20,21
7     11.46      2,3,4,5,6,7,7,3,4,5,6,7,8,8..15,16,17,18,19,20,20,16,17
8     11.06      2,3,4,5,6,7,8,8,3,4,5,6,7,8,9,9..13,14,15,16,17,18,19,19,14,15,16,17
9     10.91      2,3,4,5,6,7,8,9,9,3,4,5,6,7,8,9,10,10..12,13,14,15,16,17,18,19,19,13
10    10.9       2,3,4,5,6,7,8,9,10,10..11,12,13,14,15,16,17,18,19,19
11    10.91      2,3,4,5,6,7,8,9,10,11,11..10,11,12,13,14,15,16,17,18,19,19,11
12    10.94      2,3,4,5,6,7,8,9,10,11,12,12..9,10,11,12,13,14,15,16,17,18,19,19,10,11,12,13

the most efficient increment algorithm is 10.

ctxcm2002
Posts: 9
Joined: Sun Aug 17, 2008 6:23 pm UTC

Re:

Postby ctxcm2002 » Tue Aug 19, 2008 2:17 am UTC

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! :)

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Marble Dropping

Postby Cauchy » Wed Aug 20, 2008 12:59 am UTC

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.

User avatar
Penitent87
Posts: 28
Joined: Wed Apr 15, 2009 2:30 am UTC
Location: London

Re: Marble Dropping

Postby Penitent87 » Sat Jun 06, 2009 2:17 pm UTC

afarnen wrote:
Spoiler:

Code: Select all

using the increment algorithm where you go up by n stories, starting with n, and when the first marble breaks, you go up starting at one plus the last story at which the first marble survived the fall, here's a graph i made:

example: 10, 20, 30 (break), 21, 22, 23 (break).. that's 6 drops

         increment
       +----------
#      | 1 2 3 4 5
   +---+----------
d  | 1 | 1 2 2 2 2
r  | 2 | 2 2 3 3 3
o  | 3 | 3 3 3 4 4
p  | 4 | 4 3 3 4 5
s  | 5 | 5 4 4 3 5

inc.  avg drops  pattern
---------------------------------------------
1     50.5       1,2..100
2     26.5       2,2,3,3..51,51
3     18.83      2,3,3,3,4,4..34,35,35,35
4     15.25      2,3,4,4,3,4,5,5..26,27,28,28
5     13.3       2,3,4,5,5,3,4,5,6,6..21,22,23,24,24
6     12.14      2,3,4,5,6,6,3,4,5,6,7,7..17,18,19,20,21,21,18,19,20,21
7     11.46      2,3,4,5,6,7,7,3,4,5,6,7,8,8..15,16,17,18,19,20,20,16,17
8     11.06      2,3,4,5,6,7,8,8,3,4,5,6,7,8,9,9..13,14,15,16,17,18,19,19,14,15,16,17
9     10.91      2,3,4,5,6,7,8,9,9,3,4,5,6,7,8,9,10,10..12,13,14,15,16,17,18,19,19,13
10    10.9       2,3,4,5,6,7,8,9,10,10..11,12,13,14,15,16,17,18,19,19
11    10.91      2,3,4,5,6,7,8,9,10,11,11..10,11,12,13,14,15,16,17,18,19,19,11
12    10.94      2,3,4,5,6,7,8,9,10,11,12,12..9,10,11,12,13,14,15,16,17,18,19,19,10,11,12,13

the most efficient increment algorithm is 10.


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.

GeneralFailure
Posts: 1
Joined: Mon Jun 29, 2009 10:40 pm UTC

Re: Marble Dropping

Postby GeneralFailure » Mon Jun 29, 2009 10:46 pm UTC

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

Soljer
Posts: 29
Joined: Fri Feb 27, 2009 6:31 pm UTC

Re: Marble Dropping

Postby Soljer » Thu Nov 05, 2009 10:43 pm UTC

This is a pretty easy problem, and you can even generalize it to an arbitrary number of marbles.

Spoiler:
For 1 marble, you can't do better than a linear search.

For 2 marbles, and n floors, drop the first marble at increments of root(n) - you'll make at most root(n) drops. Once the first one breaks (let's call it floor p*root(n)), go to floor (p-1)*root(n), where you know the first marble was unbroken, and linearly search upwards till the second one breaks, you know the highest floor is one less than where it broke. This step will also take at most root(n), for a final run time of 2*root(n) or O(root(n)).

For three marbles, drop the first marble in increments of n^(2/3). This will take be at most n^(1/3) drops. Once that breaks (at floor p*n^(2/3)), go to floor (p-1)*n^(2/3) and use the two-marble algorithm as described above. That is, walk from (p-1)*n^(2/3) to p*n^(2/3) in increments of root(n^2/3) or, n^(1/3). This will take at most n^(1/3) steps. Once the second marble breaks, do a linear search over at most n^(1/3) floors. So our run time is 3*n^(1/3) or O(n^1/3).

In general, for k marbles, you can get a run time of k*n^(1/k).

If you have log(n) marbles, you can do a binary search for log(n) run-time.

I don't know if that will always be the best policy for all cases, but it is a sub-linear policy for an arbitrary number of floors and marbles (assuming more than one marble, anyways).

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Marble Dropping

Postby WarDaft » Sun Nov 08, 2009 10:58 pm UTC

Soljer wrote:This is a pretty easy problem, and you can even generalize it to an arbitrary number of marbles.

Spoiler:
For 1 marble, you can't do better than a linear search.

For 2 marbles, and n floors, drop the first marble at increments of root(n) - you'll make at most root(n) drops. Once the first one breaks (let's call it floor p*root(n)), go to floor (p-1)*root(n), where you know the first marble was unbroken, and linearly search upwards till the second one breaks, you know the highest floor is one less than where it broke. This step will also take at most root(n), for a final run time of 2*root(n) or O(root(n)).

For three marbles, drop the first marble in increments of n^(2/3). This will take be at most n^(1/3) drops. Once that breaks (at floor p*n^(2/3)), go to floor (p-1)*n^(2/3) and use the two-marble algorithm as described above. That is, walk from (p-1)*n^(2/3) to p*n^(2/3) in increments of root(n^2/3) or, n^(1/3). This will take at most n^(1/3) steps. Once the second marble breaks, do a linear search over at most n^(1/3) floors. So our run time is 3*n^(1/3) or O(n^1/3).

In general, for k marbles, you can get a run time of k*n^(1/k).

If you have log(n) marbles, you can do a binary search for log(n) run-time.

I don't know if that will always be the best policy for all cases, but it is a sub-linear policy for an arbitrary number of floors and marbles (assuming more than one marble, anyways).
That isn't the solution for worst case.
Spoiler:
You can improve your worst worst case scenario by decreasing the effectiveness of your slightly better worst case scenario. Drop it from the 14th floor, if it breaks, you have up to 13 more drops for worst case 14 total to find the floor. If it doesn't break at 14 drop it from the 27th floor, if it breaks, you have up 12 more drops for... worst case 14. The floors (or at least solution) for your first marble are 14, 27, 39, 50, 60, 69, 77, 84, 89, 94, 97,98,99,100.

Furthermore, k*n^(1/k) is not even the run time for a radix style searching. If you have 10 marbles and 100 floors, then you don't need 15 drops, that's worse than worst case for 2 marbles.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3058
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Marble Dropping

Postby Qaanol » Mon Nov 09, 2009 4:31 am UTC

If you have m marbles and an s-story building,
Spoiler:
Find the least n such that
[math]{n \choose m} \geq s[/math]
The maximum number of drops can be bounded by n-1 if m>1, or by n if m=1.

Drop the first marble from floor [imath]\large{{n-1}\choose{m-1}}[/imath]. If it doesn't break, increment the floor by [imath]\large{{n-2}\choose{m-1}}[/imath]. Continue this until the first marble breaks, say after incrementing by [imath]\large{{n-k_1}\choose{m-1}}[/imath]. Starting from the last floor where the first marble didn't break, increment by [imath]\large{{n-k_1-1}\choose{m-2}}[/imath] for the second marble. Keep decreasing the value in the top of the choose function by one each time, and adding that to the floor from which you drop the second marble. Keep doing this until the second marble breaks, say after incrementing by [imath]\large{{n-k_2}\choose{m-2}}[/imath]. Then start the increments for the third marble at [imath]\large{{n-k_2-1}\choose{m-3}}[/imath]. What we're doing is using the columns of Pascal's triangles as increment values, moving upwards. The column of Pascal's triangle (the number in the bottom of the choose function) is the number of marbles we still have left not counting the one currently being dropped. Note that the columns are indexed from 0, as are the rows.

Here's the beginning of Pascal's triangle (left-aligned).
[math]\begin{eqnarray}1\\
1 & 1\\
1 & 2 & 1\\
1 & 3 & 3 & 1\\
1 & 4 & 6 & 4 & 1\\
1 & 5 & 10 & 10 & 5 & 1\\
1 & 6 & 15 & 20 & 15 & 6 & 1\\
1 & 7 & 21 & 35 & 35 & 21 & 7 & 1\\
1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1\\
1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1\\
1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1\\
1 & 11 & 55 & 165 & 330 & 462 & 462 & 330 & 165 & 55 & 11 & 1\\
1 & 12 & 66 & 220 & 495 & 792 & 924 & 792 & 495 & 220 & 66 & 12 & 1\\
1 & 13 & 78 & 286 & 715 & 1287 & 1716 & 1716 & 1287 & 715 & 286 & 78 & 13 & 1\\
1 & 14 & 91 & 364 & 1001 & 2002 & 3003 & 3432 & 3003 & 2002 & 1001 & 364 & 91 & 14 & 1\\
1 & 15 & 105 & 455 & 1365 & 3003 & 5005 & 6435 & 6435 & 5005 & 3003 & 1365 & 455 & 105 & 15 & 1
\end{eqnarray}[/math]
Say we have 6 marbles and a 5000-floor building. Just for kicks let's say the marbles will first break when dropped from the 3600th floor. Since we have 6 marbles, we look in column 6 for the first number over 5000. That's [imath]\large{15\choose 6} = 5005[/imath]. We locate that in Pascal's triangle (on the left half). Then we move one place to the left and one place up. That column will be our increments for the first marble.

First marble:
floor 2002 does not break
floor 2002 + 1287 = 3289 does not break
floor 2002 + 1287 + 792 = 4081 breaks

Second marble:
floor 3289 + 330 = 3619 breaks

Third marble:
floor 3289 + 120 = 3409 does not break
floor 3289 + 120 + 84 = 3493 does not break
floor 3289 + 120 + 84 + 56 = 3549 does not break
floor 3289 + 120 + 84 + 56 + 35 = 3584 does not break
floor 3289 + 120 + 84 + 56 + 35 + 20 = 3604 breaks

Fourth marble:
floor 3584 + 10 = 3594 does not break
floor 3584 + 10 + 6 = 3600 breaks

Fifth marble:
floor 3594 + 3 = 3597 does not break
floor 3594 + 3 + 2 = 3599 does not break

And we are done. In this particular case we didn't need to use all 6 marbles. The point is, since at every drop we rise up one row in Pascal's triangle for our increment value, the maximum number of drops equals the row in which we began. In this case we began on row 14, so we had an upper bound of 14 drops.

For the classic case of 2 marbles and 100 floors, clearly 105 is the first value in the 2-marble column that's at least 100, so we begin there and move diagonally up and to the left to find 14 as the place to start. Since that's on row 14, that's also the upper bound on number of drops.
wee free kings


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests