More Puzzles

   Log inLog in 
 
 RegisterRegister Immediately 

Very Difficult Logic Problems
Falling Orbs revamped

 
Fri Jun 24, 2016 7:43 am  by HariKrishnan

You have m crystal balls to test.You must determine the highest floor of a n-story building from where if a crystal ball were dropped, it would not break. What will your strategy be?
Assumptions:
All crystal balls are uniform.
The result of a ball drop is binary, either it doesn't break, or it shatters into fine dust.
The number of floors is greater than the number of crystal balls.


Last edited by HariKrishnan on Sun Aug 14, 2016 10:45 pm; edited 1 time in total
 
   
Mon Jul 18, 2016 10:04 am  by Dzallen

This strategy is following on from the solution for 2 crystal balls, and aims to minimize the maximum (i.e. worst case scenario) no. of orbs dropped.

Starting form the first ball, each ball is dropped at intervals from the bottom until it breaks - when it breaks, the second ball is then dropped at intervals within the previous interval, and so on.

In order to minimize the maximum no. drops required, the worst case scenario for each interval must be 1 less than the worst case needed in the previous interval. This must be true for all intervals of all balls.

Part 1)
Strategy with 2 balls and n floors:

Let the worst case no. balls needed for the first interval from the first ball be a,
the worst case for each interval is therefore: a, a-1, a-2..etc..a-a

The number of floors n is therefore:
n=a+a-1+a-2+...+1 (using sum of arithmetic series)
n=a(a+1)/2

Solving this for a (with a rounded up) gives the maximum number of drops needed, and also the size of each interval to drop from.

Part 2)
strategy with 3 balls and n floors:

Now the intervals from the first ball are spit again into intervals by the second ball. Again let the worst case for a first ball interval be a.

The size of the first interval, from part 1), is therefore: a(a+1)/2

Since the worst case must decrease by 1 each time, the successive interval sizes are therefore: a(a+1)/2, (a-1)a/2, (a-2)(a-1)/2....etc.

The number of floors, n, is therefore:
n=a(a+1)/2+(a-1)a/2+(a-2)(a-1)/2+...+(a-a)(a-a+1)/2

This is actually the sum of the triangle numbers, each having the formula (r)C(2), where (x)C(y)=x!/y!(x-y)!

Therefore, the sum can be written as:
n=sum of (r+1)C(2) from r=1 to r=a

Using pascal's triangle, where each number represents
(row number-1)C(position in row-1), one can show that this is equal to (a+2)C(3) by looking at the relationship between the 3rd and 4th diagonal columns.

n=(a+2)C(3)

The strategy for 3 balls therefore requires solving for a (rounding up), and dropping the first ball at interval sizes a(a+1)/2, (a-1)a/2, (a-2)(a-1)/2....etc.

For example with 100 floors, a=8, the interval sizes are therefore: 36, 28, 21, 15, and 1st ball is dropped at floors: 36, 64, 85, 100.
The secondary intervals for the second ball are calculated like in part 1).

Part 3)
Strategy with m balls and n floors:

From part 1) and 2), one can deduce the general equation:
n=(a+m-1)C(m) (where a is the worst case of the smallest interval)

This equation can be proved by induction, using part 1)&2) as a base case:
Assume that n=(a+k-1)C(k) is true, where k is the number of balls

For k+1 balls, the number of floors, n, is the sum of all the interval sizes.

The worst case of each interval is determined with k balls, so the size of each interval is (a+k-1)C(k).

Since the sum of (x+y-2)C(y-1)=(x+y-1)C(y), as given by pascal's triangle, the number of floors covered by k+1 balls is:
(a+k+1-1)C(k+1)

Since this is true for k=2, the equation n=(a+m-1)C(m) holds true for all cases.

Therefore, one need to solve the equation for a, and drop the first ball at intervals: (a+m-2)C(m-1), (a+m-3)C(m-1)...etc.
The subsequent ball intervals are calculated in a similar method.

However, it should be noted that the first interval should never be dropped past the halfway point, so if a first interval calculation gives a value larger than n/2, then drop at n/2.

This method would give the maximum no. drops as a+m-2, however, this does not work for large m, where the first interval would become greater than n/2.
 
   
Tue Jul 19, 2016 12:18 pm  by bathfilms

Here's a simple strategy:

The minimum number of required ball drops, M, for N floors is

M = log2 (N + 1), rounded up to the closest integer


EXPLANATION:

We will use 15 floors as our starting example. (it would probably be unreasonable to expect a crystal ball to survive from this height, but the mathematical formula at the end should be valid for any number of floors).

The fastest approach is to use binary splitting, thereby minimising the number of balls required. (This is akin to Bubblesort in computer programming).

15 is one less than 16.
Half of 16 is 8, so that is the first drop height.
If the first ball does not break, then go to 8 + 4 = 12th floor
If the ball does break, then go to 8 - 4 = 4th floor
Etc...

This diagram illustrates the order of floor heights to drop from, starting from N = 8:

..............................................15
............................................../
...........................................14
.........................................../..\
........................................./....13
.......................................12
....................................../...\....11
...................................../.....\../
..................................../.......10
.................................../...........\
................................../.............9
................................./
...............................8
.................................\..............7
..................................\.........../
...................................\.........6
....................................\....../..\
.....................................\..../....5
........................................4
..........................................\....3
...........................................\../
.............................................2
..............................................\
...............................................1

This shows that for N = 15 floors, M = 4 ball drops are required (maximum).
Similarly, N = 7 requires M = 3 ball drops
and N = 3 requires M = 2
and N = 1 requires M = 1

The relationship is simple:

2^M = N + 1

In other words, the minimum number of required ball drops is

M = log2 (N + 1), rounded up to the closest integer :D


If we have insufficient N, then applying the same strategy will help us eliminate the most floors, until balls are depleted.

And that's it.



Fri Jun 24, 2016 7:43 am by HariKrishnan
You have m crystal balls to test.You must determine the highest floor of a n-story building from where if a crystal ball were dropped, it would not break. What will your strategy be?
Assumptions:
All crystal balls are uniform.
The result of a ball drop is binary, either it doesn't break, or it shatters into fine dust.
 
   
Tue Jul 19, 2016 2:42 pm  by bathfilms

Or, to address the question more accurately (based on the logic given above):

N = 2^M - 1

Where N = the maximum number of floors
and M = the number of crystal balls
 
   
Thu Jul 21, 2016 5:35 am  by Dzallen

bathfilms, your strategy would be correct if we were trying to minimize the number of ball drops needed given an infinite amount of balls.

However, the question is asking for the best general strategy given a finite amount of balls m. When M > log2 (N + 1), binary splitting is indeed most efficient, but when M < log2 (N + 1), it is not.

For example, one cannot use binary splitting for 2 balls and 100 floors. (I have replied to your post on that also).
 
   
Thu Jul 21, 2016 9:59 am  by bathfilms

Thank you Dzallen. I agree.
Please see my response on other posting.
:)
 
   
Thu Sep 08, 2016 2:07 am  by Zyxion

I want to break as few crystal balls as possible - those things are expensive! just start on floor one and go up one at a time until it breaks
 
   
Reply to topic
      All times are GMT
Page 1 of 1

 
 



Discussion Board Forum Index