[Brainteaser, repost] 2 crystal balls?

Question

There is an infinitely long staircase. It has stairs numbered 1, 2, 3, ..., n, n+1, ..... You are standing at the bottom of it.

There are two identical crystall balls in your hand.

Its known that if either of the balls is rolled down from any stair that's N or lower, it will not break. If it is however rolled down from N+1 stair, or any stair higher than that, it will break.

Design a way to find the number N in smallest possible number of steps.

For the sake of argument, assume N is large

Hallam: the problem is indeed similar, but none of the answers on the website you quoted actually provides any solid reasoning beinhd the answer; they;d have a much harder time with N=10000... so think about it :)

Chance: your solution yields N/2 steps in bad case, N/4 in average case.

Answer 1

We seek to find the most 'efficient' increasing sequence of positive integers s(0), s(1), s(2), s(3), ... to use in the following way:

Let s(0) = 1 and begin the process following with stair s(1). Take the first sphere to stair number s(1) and roll it down. If it does not break, take it to stair number s(2) and roll it down. Continue this process until when rolling the sphere from stair number s(j) it breaks. Once that occurs we have narrowed the range for N to be:

s(j-1) <= N < s(j)

Now with the second sphere, start rolling on every stair from [s(j-1) +1] up until N is discovered (by the breaking of the second sphere naturally).

How many 'steps' (process steps not stairs) did it take to get to the answer? We rolled the first sphere j times and the second spehere an expected (s(j) - (s(j-1) +1))/2 times. Our total would be

j + (s(j) - (s(j-1) +1))/2

Now getting back to the problem of selecting the sequence s(1), s(2), ..., most efficiently (recall we fixed s(0)=1). First note that if the sequence was {2,3,4...} or even any general arithmetic sequence {a, a+d,a+2d,...} we would have an efficient time with our second sphere, but since we are told that N is large we would expect a less efficient use of the first sphere. A quicker way to get the first sphere up to higher staris would be to use a geometric, exponential or other series for our sequence. There is of course some trade off with having to do many more rolls with the second shere once the first has narrowed the range.

I am not certain how to conclude what type of series yields the best efficiency, but since we are told N is large my intuition would be to use an exponential series or a series such as
s(0) =1, s(1) =2, s(2) =2^2, s(3)=s^2^2^2,..., s(k)=s(k-1)^2 for k>0.

Answer 2

Your riddle reminds me of one I read a while back on iBankingOasis.com:

You are standing outside a 100-story building holding two identical glass spheres. You are told that either sphere, if dropped from the roof, would shatter upon hitting the earth, but that it would not necessarily break if dropped from the 1st story. Your task is to identify the lowest possible floor that you can drop a ball from and break it. QUESTION: In the general case, what is the smallest number of drops required to guarantee that you have identified the lowest story?

Notes:
- Both balls have the same minimum breakage story.
- You only have two balls to use. If one breaks, it cannot be used for the rest of the experiment.

The answer to this was 14 drops, and the reasoning behind this was given by aachimp:

http://www.ibankingoasis.com/node/4956

Since you've specified the stairs as being infinite rather than finite, I can't quite wrap my mind around whether or not you can apply the same logic here. Are there any additional details you could add to help me out?

I'm dead curious to know how this works.

Answer 3

I have two crystal balls and they're not in my hands.

Answer 4

if it is infinitely long then how is there a bottom
i'm serious infinitely means it doesnt stop

Answer 5

i don't kno.