Author |
Topic: 2 marbles and 100 floors (Read 2220 times) |
|
hoferman
Newbie
Posts: 10
|
 |
2 marbles and 100 floors
« on: Aug 16th, 2005, 6:16am » |
 Quote  Modify
|
You have 2 identical marbles, that will break if you drop them from a certain hight, from one of the floors, of a building with a 100 floors. It could be that the marbles will break if you drop them from the 1st floor, but it could also be that they will break from the 100th floor (or any floor in between). If one breaks you have only one left so be carefull what strategy you choose in dropping them from specific floors.
It is your job to find out from what floor the marbles will break.
How many drops will you need as a maximum, and what is your strategy?
|
|
 IP Logged |
|
|
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
|
Re: 2 marbles and 100 floors
« Reply #1 on: Aug 16th, 2005, 10:40am » |
Quote Modify
|
on Aug 16th, 2005, 6:16am, hoferman wrote:| How many drops will you need as a maximum, and what is your strategy? |
|
100... start at the first floor and increase the floor level by one each time the marble 'survives'...
The riddle would have been more interesting if you would have asked us to minimise the maximum number of drops needed... 
|
| « Last Edit: Aug 16th, 2005, 10:40am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: 2 marbles and 100 floors
« Reply #2 on: Aug 16th, 2005, 10:48am » |
Quote Modify
|
Ok.. so let's make an attempt to minimise the maximum number of drops needed...
Intuitively, I would say that a logatihmic splitting of the dynamic range should bring us close to optimality:
so, throw the first marble from the 10th floor.
> If it breaks, you use the second marble to work your way up the floors from 1 till 9.
> If it survives: throw it from 10 floors higher
. . . > If it breaks, use your second marble to test floors 11 till 19
... etc.
Maximum number of droppings needed will be 19 (in case the marbles survive a drop from floor 99, but crash when dropped from floor 100).
|
| « Last Edit: Aug 16th, 2005, 10:51am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: 2 marbles and 100 floors
« Reply #3 on: Aug 16th, 2005, 10:51am » |
Quote Modify
|
Ok, I can get it down to 51 drops, maximum!!!
Definition: floor 0: street level
Can I assume dropping from floor 0 will not break a marble?
Algorithm?
| hidden: | floor = 0;
while ( !broken || floor == 102 ) { // Put a limit!!!
broken = drop(0, floor); // Drop first marble.
if ( !broken )
floor += 2;
}
floor -= 1;
if ( !drop(1,floor) )
echo "Marble breaks on floor ", floor;
else
echo "Marble breaks on floor ", floor+1; |
Other algoritm?
drop on floor 10.
If broken
drop on floor 1 through 10. Floor it breaks at, is the floor in question.
if not broken, repeat (add 10 to values).
Wait... this gives us a maximum of 20 drops! (18 actually) case floor = 100;
9 Drops: from floor 10, 20, 30, 40, 50, 60, 70, 80 and 90
9 Drops: from floor 91,92,93,94,95,96,97,98,99
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: 2 marbles and 100 floors
« Reply #4 on: Aug 16th, 2005, 11:07am » |
Quote Modify
|
Hmmm... what works even better is the following:
throw the first marble from level 14, and - as long as it continuous to survive - increase the floorlevel one less than the last increase:
14, 27, 39, 50, 50, 69, 77, 84, 90, 95, 99
and then use the second marble to work up one floor at a time from the one but last floor tested (i.e. the last floor for which the first marble survived).
Maximum number of drops needed: 14
|
| « Last Edit: Aug 16th, 2005, 11:10am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: 2 marbles and 100 floors
« Reply #5 on: Aug 16th, 2005, 11:09am » |
Quote Modify
|
So, if floor = 14, it'll take another 13 drops to double-check your answer, totaling to 14. and-so-on.
Worst-case = 14 drops!
Great job, JocK!
EDIT: Altough dropping from floor 50 twice is useless  ... j/k
|
| « Last Edit: Aug 16th, 2005, 11:10am by Sjoerd Job Postmus » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: 2 marbles and 100 floors
« Reply #6 on: Aug 16th, 2005, 3:38pm » |
Quote Modify
|
OK... let's add a small bonus question:
So according to the above, with two identical marbles you can test n(n+1)/2 floors in no more than n drops (which - I guess - would have made the riddle slightly nicer if it was posed for 300 floors rather than 100...).
How many floors can you test in no more than n drops with k identical marbles?
|
| « Last Edit: Aug 16th, 2005, 3:46pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: 2 marbles and 100 floors
« Reply #7 on: Aug 16th, 2005, 4:02pm » |
Quote Modify
|
Seeing as you -by your formula- can test it for 13 drops up to 91 floors... Why not make it a worst-case thingie for 91+?
13, 25, 36, 46, 55, 63, 70, 76, 81, 85, 88, 90, 91
Pretty save, and only in the worst case, it fails to reach 13 drops... Still... I think it's a save gamble, although the worst-case would be like, 13 + 100 - 91 drops... 22? Wow, bad!
Better go for the save 14 
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 2 marbles and 100 floors
« Reply #8 on: Aug 16th, 2005, 10:38pm » |
Quote Modify
|
There are at least four threads for a similar riddle, some under the title "Egg Dropping":
1 2 3 4
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: 2 marbles and 100 floors
« Reply #9 on: Aug 18th, 2005, 5:09am » |
Quote Modify
|
on Aug 16th, 2005, 10:38pm, SWF wrote:There are at least four threads for a similar riddle, some under the title "Egg Dropping":
1 2 3 4 |
|
Hmmm well...
... although apparently an exercise in re-inventing the wheel, solving this little problem was still fun...
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: 2 marbles and 100 floors
« Reply #10 on: Aug 18th, 2005, 10:22am » |
Quote Modify
|
I think I know an answer to the
floors(m,d)-question
floors(m,d) {
if ( m == 1 )
return d;
int floors = 0;
int i = 0;
for ( i=0; i < d; i++ )
floors += floors(m-1, i);
return floors;
}
 ...
Now, from here on, you could have a method to create equations...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print