You are given two identical crystal orbs and access to a 100-story building. An orb dropped from some floors may survive the fall, while from higher floors it will shatter. There is a highest "safe" floor F (0 ≤ F ≤ 100) such that the orb does not break if dropped from any floor ≤ F and does break from any floor > F.
Hint: Try making the first orb jumps of decreasing size so that, no matter where it breaks, the total number of drops (first orb so far + second-orb search) is the same.
Solution:
The fewest drops required in the worst case is 14.
Let the first orb be dropped successively from floors spaced 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 floors apart. Concretely, drop it from floors:
14, 27 (14+13), 39 (+12), 50 (+11), 60 (+10), 69 (+9), 77 (+8), 84 (+7), 90 (+6), 95 (+5), 99 (+4), 102 (+3) – but we only need up to floor 100, so stop there. (The final two theoretical steps of +2 and +1 are automatically covered.)
There are two cases:
- If the first orb never breaks, F = 100 and you have used 14 drops.
- If it breaks on some floor, suppose it broke on the k-th drop. At that moment you have used k drops, and you know the highest safe floor lies between the previous safe floor and the current one – an interval whose length is at most 14 − k. Now use the second orb to test each floor within that interval sequentially from the bottom up. In the worst case this costs another 14 − k drops, bringing the total to k + (14 − k) = 14.
Thus, no matter where the critical floor lies, you will never exceed 14 drops.
Why 14 is optimal
The sum 14 + 13 + ⋯ + 1 = 105 ≥ 100 guarantees every floor is reachable in at most 14 drops. If you tried to finish in only 13 drops, the maximum number of distinct outcomes (the 13 triangular number) would cover at most 91 floors, insufficient for 100. Therefore 14 is the minimum possible.
Comments (30)
It may be less but I think I could do it in at most 14 drops.
The answer is 7 drops.
The solution I am submitting below is encrypted so as not to take the fun out of your efforts! To decrypt use: www.rot-n.com
The cipher used is ROT18-ROT5 & ROT13.
Guvax bs vg nf n ovanel ceboyrz, naq pbaireg vg vagb ovanel. Fgneg sebz bayl 65 fgbel uvtu ohvyqvat. Guhf lbh unir 6655 sbe 65. Rnpu cbfvgvba bs gur qvtvgf va 6655 qrfpevorf gur fgbel sebz juvpu gur beo vf gb or qebccrq, va gur qbjajneq snfuvba. Fb sbe rknzcyr bs 65, vg fubhyq or qebccrq sebz fgbel ahzore =, 9, 7 naq 6 erfcrpgviryl.
Abgr - O zrnaf Oernx, AO zrnaf Ab Oernx.
Guhf sbe 65:
Q=-AO-Q65-AO-65 vf gur znk sybbe
Q=-AO-Q65-O-Q>-AO-> vf gur znk
Q=-AO-Q65-O-Q>-O-= vf gur znk sybbe
Q=-O-Q9-AO-Q;-AO-Q<-O-; vf gur znk sybbe
Q=-O-Q9-AO-Q;-AO-Q<-AO-< vf gur znk sybbe
Q=-O-Q9-AO-Q;-O-Q:-AO-: vf gur znk sybbe
Q=-O-Q9-AO-Q;-O-Q:-O-9 vf gur znk sybbe
Q=-O-Q9-O-Q7-AO-Q8-AO-8 vf gur znk sybbe
Q=-O-Q9-O-Q7-AO-Q8-O-7 vf gur znk sybbe
Q=-O-Q9-O-Q7-O-Q6-AO-6 vf gur znk sybbe
Q=-O-Q9-O-Q7-O-Q6-O-5 vf gur znk sybbe
Nf h pna frr sebz nobir, abar bs gurz gnxr zber guna 9 qebcf! Fvzvyneyl vg pna or jbexrq bhg sbe 655, juvpu va ovanel vf 6655655, univat < qvtvgf naq urapr < qebcf!!
My solution holds true if infinite number of Orbs are available, for minimum number of drops.
The correct answer to the problem is 14.
yeah, radically different math for the two solutions as well ;)
i think the anwser is 7 (minimum no.).
Correct answer is 10
I guess only 18 drops would be sufficient to test the orb being dropped from 1 through 100 floors. Please let us know the answer.
largest number of drop = 18.
suppose you start from 10 and then 20 and then 30........ 100
now consider the situation...
first orb cracked at 10: then you have to come from 1 to 9 as well = 10
first orb cracked at 20: then you have to come from 11 to 19 as well = 11
first orb cracked at 30: then you have to come from 21 to 29 as well = 12
...
...
first orb cracked at 90: then you have to come from 81 to 89 as well = 18
but if orb is not cracked at 90, here you can change the strategy to come in 13 drop.
10,20,30,40,50,60,70,80,90,94,97,99, 100
if 94: 91,92,93 = 13
if 97: 95,96 = 13
if 99: 98 = 13
Sorry, asheeshg, but your 13 solution misses the mark at 80. If the first one breaks at 80, you might need 9 more drops to get to 90.
The key is to balance the number of drops left with the number gained.
So, first you drop at X, and if it breaks, you need X-1 drops to fill from 1
Then at X + (X-1), you have X-2 drops to fill from X.
Then at X + (X-1) + (X-2), you have X-3 drops to fill from 2X-1.
Then at X + (X-1) + (X-2) + (X-3), etc.
Until you top out at X + (X-1) + (X-2) + ... + (X-(X-1)) + (X-X), which, when reversed is Sum( 0: X ), or X/2*(X+1).
Then we just need to find out the smallest integral value of X where X/2*(X+1) > 100.
It turns out that 13/2*14 = 91, and 14/2*15 = 105, so we need at least 14 drops in the worst case.
First orb drops are at 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100.
Whenever the first bulb breaks, you start at the next lower number and count up by one. It is impossible to do with a worst case of 13 drops.
i think the answer is 14. Those claiming 7 shall justify.
The answer is 7.
Drop from 50
If it breaks drop from 25, if it doesn't drop from 75
If it breaks from 25 drop from 13 if it doesn't drop from 38
(Similarly, if it breaks from 75 drop from 63, if it doesn't drop from 88)
Assuming each time we cut in half how many floors it could be (rounding up due to no half-levels) we get:
after 1 drop - 50 possibilities
after 2 drops - 25 possibilities
after 3 drops - 13 possibilities
after 4 drops - 7 possibilities
after 5 drops - 4 possibilities
after 6 drops - 2 possibilities
after 7 drops - 1 possibility AKA our correct floor
Daleman21,
Sorry, but your solution doesn't work:
You only have 2 orbs. If the first one breaks at floor 50, and the second at floor 25, then you can't progress.
I have a definite method for an answer of 14.
:)
I'm thinking 19. You have two orbs, so you have to divide the floors into two subsets. If you graphed the ideal way to break it up, the square root of the total number of floors would be at the apex of a quadratic curve. That means we group it into ten sets of ten.
First we go up ten floors at a time, and the most tests we need to get the first break will be 10 if it breaks at floor 100. This means that the break point is anywhere from 91-100. Next we test floors 91-99. If the breaking point is floor 100, then the second orb will not break on any of these tests, meaning we have to test nine times.
So in a worst-case scenario, the first orb gets tested ten times, the second gets tested nine times, for a total of 19.
I must respectfully disagree with those who have suggested the halving method, or whatever it's called. Say you break orbs on the first two drops. Now you're stuck at 25 and only know that the correct floor is 25 or lower.
Edit: My method also gives a lowest number of trials of two. That happens if the first breaks at 10 and the second breaks at 1.
49
The approach where you drop a ball every 10 then work up from the last safe point is viable, and a typical response when you work primarily in base 10. However, it has very evident efficiency issues. These become clear the higher up the scale you go:
Floor / Tries
1-10/2-10
11-20/3-11
21-30/4-12
31-40/5-13
41-50/6-14
51-60/7-15
61-70/8-16
71-80/9-17
81-90/10-18
91-100/11-18
The fact the maximum number of tries keeps increasing shows it's main failing. Rather than going up in 10s, the maximum number of tries for each banding should remain consistent. Try changing your cutoff points so the maximum in the first banding equals the maximum in the rest...
The first ball sets a floor and a ceiling on the value; the second ball must advance the floor by single digits. With that restriction in mind:
~13.651, showing that 14 drops are required.
Consider the following pattern: Drop the first ball from X floors; if it breaks, drop the second ball from 1 to x-1 floors until it breaks. If it doesn't break, drop it from 2x-1 floors; if it breaks, drop the second ball from x+1 to 2x-2.
From this pattern is is easy to see that the largest number of floors that you can test with X drops is (x)(x+1)/2 (with 1 drop you test it from floor 1; if you have two drops you test from floor 2, then 3; if you have three drops you test from 3,5,6; with four try 4,7,9,10 (in each case, if the first crystal breaks, try the second crystal from one over the floor and up to one below the ceiling)
Solving for 100
Knowing the number of drops required, it's easy to find the methodolgy:
Drop the first crystal from 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 until it breaks. Use the second one to figure out where in the interval the exact position is.
Probably wrong but didn't seem to hard - so probably wrong
Once you lose the first orb the 2nd must only go up one at a time from the last floor that the first one did not break on (so there is a formulae there)
So the key is to look at ORB one jumping each time by say N floors eventually it breaks and from there you have to go back to the previous success and come up in ones ( the worst scenario is it might be the last foor i.e. the one the first orb failed where the second also fails on) and we must cope with the worst scenario
N = Number of floors to start for ORB 1
So I think the formulae is the lowest number for N where
100 / N + N (ignore remainder as this if for the next jump of ORB 1) (N.B. + N for going up one floor at a time from where ORB one was obliterated)
E.G. Try 8
100/8+ 8 = 12 + 8 = 20
100/9 + 9 = 11 + 9 = 20
100/10 + 10 = 10 + 10 = 20
100/11 + 11 = 9 + 11 = 20
100/12 + 12 = 8 + 12 = 20
100/13 + 13 = 7 + 13 = Guess what
As I say its all probably rubbish but don't see why ?
Sorry that should have red N/100 + (N - 1)
so the answer to the above is 19
If you keep increasing G soon N will be too big and the + N will take it above 20
100/6 + 5 = 16 + 5 = 21
100/7 + 6 = 15 + 6 = 21
If N is too small the 100/N is too large
100/1 + 0 = 100
Am I right ?
Sorry AGAIN ! that should have red N/100 + Remaineder of Divide + (N - 1)
so the answer to the above is 19
If you keep increasing N soon N will be too big and the + N will take it above 19
100/6 = 16 + (Remainder) 4 + (N-1) 5 = 26
100/7 = 14 + (Remainder) 2 + (N-1) 6 = 22
If N is too small the 100/N is too large
100/1 + 0 = 100
So 19 is the lowest achieved by going up in ten floors at a time
100/10 = 10 + (Remainder) 0 + (N-1) 9 = 19
Am I right ?
The first thing you need to do is divide the floors into groups. The smallest group you could pick would be 1 (start at the beginning and go up one floor each time). The largest group you could pick would be 100 (drop it at the top floor, if it breaks start at floor 1 and go up one floor at a time).
Neither is very effective, so we need a new "Group Number", it can be any number from 1 to 100 so let's call it "X" since we don't know which number is the best one.
For example, let's say X=10 (I saw a few people use this one).
You drop the first orb at the 10, 20, 30, etc. floor until it breaks on one.
Say it broke on floor 30, then you would take the second orb and drop it at floor 21, then 22, then 23 etc. until it broke at lets say floor 29. you would have then dropped the orbs a total of 12 times. three for the first one, and nine for the second one.
The way you find the highest possible number of drops for a group is to imagine that the first ball drops on your last drop before 100. If the group number were 10 the first ball would break at 100. if the group number was 8 then the first ball would have to break at 96 because 96 is the greatest multiple of eight under one hundred. This lets the first orb drop the maximum number of times it can drop, and the second orb would have to drop the maximum number of times before shattering which would be 9 times for a group number of 10 (the 99th floor) and 7 times for a group number of 8 (95th floor) (a worst case scenario).
Here is where the math comes in. the maximum number of times the first orb can drop is equal to 100 (the number of floors) divided by X (the size of the group). This number doesn't always come out evenly so you need to round down. The way we notate that in a function is called the least integer function (denoted by ]A[ ) which means to round A down the the closest whole number.
The maximum number of times the first orb can drop would be (]100/X[). the maximum number of time the second orb can drop would be one less than the group size (X-1).
To find the maximum number of times the orbs need to be dropped to find the correct floor is the sum of those two values: (]100/X[)+(X-1)
This tells us the maximum number of times the orbs need to be dropped for any group size in order to find the correct floor. The question asks for what is the smallest number of drops. If you graph all of these points for group sizes 1 to 100 you get something that looks like a "funky parabola" or a steep slide followed by the ugliest flight of stairs :P the minimum of this graph is 19 for group sizes of 8,9,10,11,12, and 13.
In summation if you use any of those group sizes your maximum number of drops will be 19, which is the lowest number of drops you can possibly have if you assume the same group size is used every time you drop the orbs. (will test non-static groups later)
Its 14 honest
Drops + floors since last drop
Drop 1st at 14 if breaks start at 1 and go up in ones = 1 + 13 = 14
No Break then
Drop 1st at 27 (14 + 13) if breaks start at 15 and go up in ones 2 + 12=14
No Break then
Drop 1st at 39 (27 + 12) if breaks start at 28 and go up in ones 3 + 11=14
No Break then
Drop 1st at 50 (39 + 11) if breaks start at 40 and go up in ones 4 + 10=14
No Break then
Drop 1st at 60 (50 + 10) if breaks start at 51 and go up in ones 5+ 9=14
No Break then
Drop 1st at 69 (60 + 9) if breaks start at 61 and go up in ones 6 + 8=14
No Break then
Drop 1st at 77 (69 + 8) if breaks start at 70 and go up in ones 7+ 7=14
No Break then
Drop 1st at 84 (77 + 7) if breaks start at 78 and go up in ones 8+ 6=14
No Break then
Drop 1st at 90 (84 + 6) if breaks start at 78 and go up in ones 9+ 5=14
No Break then
Drop 1st at 95 (90 + 5) if breaks start at 91 and go up in ones 10+ 4=14
No Break then
Drop 1st at 99 (95 + 4) if breaks start at 96 and go up in ones 11+ 3=14
no break drop at 100 11 + 1 = 12
so the worst case is always 14 so it is 14 drops you need the 12 is just a luck and can't be taken as the answer
Am I correct ?
14 drops is the maxmum, as others have pointed out. It's easy to see the math. Start at the top floor, then subtract in increasing numbers going down:
100
99 (-1)
97 (-2)
94 (-3)
90 (-4)
85 (-5)
79 (-6)
72 (-7)
64 (-8)
55 (-9)
45 (-10)
34 (-11)
22 (-12)
9 (-13)
These are the floors you can drop at. If the first crystal breaks at 9, you have a max of 9 drops to solve the problem. If it breaks on any floor beyond 9, you will have a maximum of 14 (i.e. Breaks on 22, you'll have to try 10 - 21 (12 floors), plus the tries at 9 and 22).
The reason for the the groupings getting 1 smaller with each iteration (9 to 22 is a jump of 13, while 22 to 34 is a jump of only 12) is to account for the drops used for previous iterations as well.
The answer is 14. you drop an orb every 10 floors, so that is 10 drops. then when it breaks (it can break at any tenth floor, but the maximum is 10 drops for 100 floors) you go to the last 10th drop, suppose 90, and drop the ball every 2nd floor. if it breaks at the first second, or 92nd floor, then the last floor survived is 90, and it broke at 92, so the minimum is 91. Then, if its 94th, you already dropped at 92, and you broke it at 94, so the floor has to be 93. you do this for 4 times (92,94,96,98, and you already did it at 100 and 90 because of the first orb.)
So, maximum 10 every tenth floor and 4 2nd floors so 14 drops :)
ArmyMP actually that doesnt work. you should NEVER start at the top floor. Suppose you drop it at 100, and it breaks. One orb left. Then you drop it at 99 and it breaks. none left and 98 solutions left. :(
Same for usernamenotused. Instead of going one floor after the 10 floor drop stage, go up two floors. then you get 14.
Based on the 7 tries answer, i made a mathematical solution to this...
You need to do some drops and reduce the number of drops on each one, so...
If you start at 7, you then have 6 remaining drops, so, the next number is 6+7 =13, the next number is 13+5, you see it now?
1+2+3+4+5+6+7+8+9+10+11+12+13 = 91(not enough)
but
1+2+3+4+5+6+7+8+9+10+11+12+13+14 = 105 (cover all levels!!)
Anubhab, if the orb breaks at 92 and survived at 90, then the highest surviving floor could be 90 or 91. You have only narrowed it down to the last 2 floors.
ArmyMP84's strategy is correct for getting 14 drops as the maximum. Interestingly however, the strategy is less efficient than those which drop the first orb at floors 14, 27, 39 etc., as the average number of drops required per floor is greater (by exactly 0.13), most likely due to the larger number of drops for the first ball at higher floors.
There are a range of solutions that yield the lowest maximum no. drops 14, all of which following the same increments between orb drops, with the first orb drop ranging from 9-14 (i.e. 9 22 34..., 10 23 35...,...14 27 39...)
Using my solution for the generic problem (as explained in "Falling Orbs Revamped"), the answer is:
M = log2 (N + 1) ROUNDED UP to the closest integer
Where N = the maximum number of floors
and M = the minimum number of crystal balls drops required
So M = log2 (100 + 1) = Log2 (101) = 6.66 = 7 (rounded up)
In fact, only 7 balls could determine up to 127 floors!
JUSTIFICATION: It is a binary splitting solution:
Drop the 1st ball at the 64th floor (half of 128)
Let C = Change = 64/2 = 32
If it breaks, SUBTRACT C to get 64 - 32 = 32nd floor (to test next)
If it does not break, then ADD C to get 64 + 32 = 96th floor (to test next)
After each iteration, either add or subtract half of the previous C-value
So C = 64, 32, 16, 8, 4, 2, 1 in turn (including the first drop)
This gives 7 ball dropping opportunities AND guarantees all possible answers up to 127 floors.
Ah... now I see that after 2 balls had broken, then many of my intended drops would be invalid.
Therefore only the following WAYS would be valid:
(Using 13 ball drops)
0 breakages x 1 way
1 breakage x 13 ways
2 breakages x 90 ways (= (13+1)X13/2 - 1)
TOTAL = 104 FLOORS
However, 0 breakages would not determine how many floors (in excess of 103).
Therefore 103 FLOORS can be determined with 13 ball drops (using no more than 2 balls).
Drop the 1st ball at floor 52 (half of 104)
Let C = Change = 52/2 = 26
If it breaks, SUBTRACT C to get 52 - 26 = Floor 26 (to test next)
If it does not break, then ADD C to get 52 + 26 = Floor 78 (to test next)
After each iteration, either add or subtract half of the previous C-value
So C = 104, 52, 26, 13 in turn (including the first drop) to start with
If this point is reached, there will be a lesser number, X, of (non-eliminated) floors remaining to test.
If these are renumbered A1 to AX,
then we begin again at floor (X+1)/2
Now C will be (X+1)/2, (X+1)/4, (X+1)/8, etc. in turn
I will make a table to cover all scenarios to check.
Therefore, I believe that with binary division, only 13 drops are required.
bathfilms, I'm not sure I understand your strategy, because if the balls break on the first two drops (52, 26), then you won't have any left.
Hi Dzallen,
Yes, I see your point..
After reconsidering the problem, I have worked out that the optimum pseudo-binary splitting would yield a new answer of 21 drops:
We start on floor 5 and then move to floor 10 or floor 1 (depending on ball survival or breakage respectively)... see the flow chart below:
..............................25..etc...
..........................20
........................./...16...etc...
......................../
.....................15....
..................../....\...12
.................10......11
................/....\.......10
............../.......\..7
............5......4..6
..............\...3......5
...............\./..2
................1
..................0
This allows a maximum of 2 breakages.
If the flow chart is extended, it shows that 21 drops are required to determine 1 to 100 floors inclusively.
However, to my surprise this pseudo-binary splitting has not produced the minimum.
Therefore I agree with the answer of 14 as described by others.
Add a Comment or Suggest an Answer