need a help 2 sove a nice riddle

[dudi1976]

Hi 2 everybody,

The riddle goes by steps

1) You have ladder (with 100 steps)
and
1 ball (which can be broken if fall from some finite height)

(a) What is the minimum trails (throw the ball from the ladder) you have to do in order to know which step of the ladder the ball will be broken.

well the answer to this que. is simple:
the algorithm is to go step by step from 1 to 99 and to throw from each one the ball until it brakes . so the minimum trails at the worst case is 99 (100 - 1 )

Now the Problem became more difficult:

2) Now you have 2 balls

(a) What is the minimum number of trails at the worst case you have to do in order to know which step of the ladder the ball will be broken.

(b) give a solution as a formula (to calculate the max trails by given fact that the the ladder has 100 steps)

(c) give a solution as a formula (to calculate the max trails by given fact that the the ladder has N steps)


I solve the (a) (see file attached) by intuition but don't know how to solve (b) and (c)

Please help me ! ! !

[cmiskow]

First of all, is it guaranteed that the breaking height for the ball exists on the ladder? If so, then you could start at 2 and go to 99, so the worst case is 98. This is because if the height is definitely along the range of the ladder, then if the ball breaks on 2, you know it is 1; and if it has not broken on 99, you know it is 100.

With 2 balls, you could start at step 50 and throw the first one. Worst case, the ball breaks and you go from 1 to 49 with the second ball, giving 50 throws (or using rules defined above, go from 2 to 48, giving 48 throws). In the best case, the ball does not break and you can progess up the ladder each time by half of the remaining height.

The worst case for 2 balls with 100 stairs is then generalized to N stairs giving the formula N/2 tries (or N/2 - 2 using the idea presented in paragraph 1).

[dudi1976]

first thanks


Sorry I forgot to tell that the balls must be broken somwhere at the ladder

(the problem with 2 balls)

In your solution you got worse case 48 tralis

I got to a solution that I need no more then 14 trails to know which step from 1 to 100 the ball will be broken (see the file attached)

What I need is a formula for the general case (ladder with N steps)

Best Regards,
Dudi

[Yves M]

It's not so hard, really and your solution for the 2 ball problem is pretty good. It's mostly what the general solution would look like too.

We want to minimize the number of trials. So with the first ball, we want to split the ladder steps into intervals of decreasing length. Each sucessive interval is 1 smaller than the previous one, because we have used one more trial at that point. So the intervals for the first ball are:
X + (X - 1) + (X - 2) + ... + (X - n)
Where n is the number of intervals - 1. Ideally, the number of trials are constant, which would entail that X is equal to n. So the previous sum is:
X + (X - 1) + ... + (X - X)
This is nothing else than X * (X - 1) / 2. Now, we can always discard always the first trial in each interval, so the number of trials we need is only X - 1. We can calculate X as the smallest integer bigger or equal to the solution of X * (X - 1) / 2 = 100. The solution to this equation is 1/2 * (1 + 3 sqrt(89)) which is approximately 14.65, so X is 15. Hence X - 1 is 14 and we need at most 14 trials.

Here is a small C program that implements this algorithm:

#include <math.h>

int calculateX(int steps)
// The equation is:
// 0.5 X^2 - 0.5 X - steps = 0
{
double det = 0.25 + 4.0 * 0.5 * double(steps);
double result = 0.5 + sqrt(det);
int ires = floor(result);

// Check whether the result is exact:
if ((ires * (ires - 1) / 2) == steps) {
return ires;
} else {
return ires + 1;
}
}

// The external solution
int current_solution = 0;
int nTrials = 0;

bool test_solution(int n)
// Returns true if the ball breaks
{
++nTrials;
return (n >= current_solution);
}

int find_sol(int steps, int X)
// Tries to find the solution by going through the intervals
{
// The first range goes from 1 to X - 1 (this contains X - 1 elements)
// In C notation this is 0 to X - 2
// We test the last element of this range,
// since testing 0 would not yield much information
int min = 0;
int max = X - 2;
// First try with the first ball:
bool bBroken = false;
int currX = X - 1;
while (!bBroken && (max < steps)) {
bBroken = test_solution(max);
if (!bBroken) {
min = max + 1;
max += currX - 1;
currX--;
}
}
// Now the range [min, max) contains the solution
int i = min;
while ((i < max) && !test_solution(i)) {
++i;
}
return i;
}

int calc_max(int steps)
{
int X = calculateX(steps);
int currTrials, maxTrials = 0;
for (int i = 0; i < steps; ++i) {
current_solution = i;
nTrials = 0;
int res = find_sol(steps, X);
if (nTrials > maxTrials) {
maxTrials = nTrials;
}
}
return maxTrials;
}

int main()
{
calc_max(11);
for (int i = 10; i < 200; ++i) {
int X = calculateX(i);
int solX = calc_max(i);
}
return 0;
}

[DeepButi]

Assuming your algorithm is the best one (wich I'm not sure about) ... the formula you need is n=(1+SQR(8*N+1))/2.

Is that what you are looking for? :ehh:

oooppssss :mad: Yves was faster and better

[dudi1976]

Thanks for you all :)

[RoboTact]

Now, we can always discard always the first trial in each interval, so the number of trials we need is only X - 1.It is wrong. You have at least one hight step, but not at least one hight step for every trial ball and of cause not at least one step precisely at each track selected by Yves M for every ball.
But actually what is the point of this thread? Where is the problem?

[Yves M]

Yeah, it should be the last trial in each interval that is not needed, since we have already done that with the first ball. So it's still X - 1, but it's the last, not the first of each interval that is not tested again.

As for the problem, it's in dudi1976's first post.

[nanu2010]

instead of 100 steps what if we change the problem to N steps. what would then be the minimum number of trials?

[Firewireguy]

My maths isn't as good as the previous posters, but isn't this a perfect time to use a binary tree search?

Start at step 50, if it breaks move to step 25 (50/2). If it breaks move to step 18 (ceil(25/2)) etc. Or move up to 75 if it doesn't break etc?

[amit_arora27980@yahoo.com]

No that would not work since if it breaks at 5o u move to 25 and if it still break u donot know the minimum height at which ball breaks since there can be the case that ball breaks at step 5 so definately it is going to braek at 50 and 25 both and in the process u r left with no balls to move down the ladder.