More Puzzles

   Log inLog in 
 
 RegisterRegister Immediately 

Very Difficult Logic Problems
Falling Orbs
Goto page Previous  1, 2, 3  Next
 
Fri Dec 13, 2013 3:25 pm  by simon155

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...
 
   
Sat Oct 11, 2014 5:24 am  by Decius

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:

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<x>~13.651, showing that 14 drops are required.

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.
 
   
Sat Nov 28, 2015 3:17 pm  by CAS

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

[b]As I say its all probably rubbish but don't see why ?[/b]
 
   
Sat Nov 28, 2015 3:42 pm  by CAS

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 ?
 
   
Sun Nov 29, 2015 10:16 am  by CAS

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 ?
 
   
Wed Dec 16, 2015 6:21 am  by usernamenotused

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)
 
   
Sat Dec 19, 2015 3:47 pm  by CAS

[b]Its 14 [/b] 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 ?
 
   
Fri Feb 19, 2016 8:25 pm  by ArmyMP84

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 [max] 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.
 
   
Fri May 06, 2016 1:16 am  by Anubhab

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 :)
 
   
Fri May 06, 2016 1:22 am  by Anubhab

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.
 
   
Tue Jun 07, 2016 2:02 pm  by Gaunt

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!!)
 
   
Wed Jul 13, 2016 5:07 am  by Dzallen

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...)
 
   
Tue Jul 19, 2016 3:07 pm  by bathfilms

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.
 
   
Tue Jul 19, 2016 4:26 pm  by bathfilms

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.
 
   
Thu Jul 21, 2016 5:35 am  by Dzallen

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.
 
   
Reply to topic
      All times are GMT
Goto page Previous  1, 2, 3  Next
Page 2 of 3

 
 



Discussion Board Forum Index