I am in a 100-story building. I have with me two glass balls. I know that if I throw the ball out of the window it will never brakes if the floor number is less than X and it will always brakes is the floor number is equal or greater than X. Assuming that I can reuse the balls which didn't brake, find X in a minimum number of throws.

The simplest way is throwing one ball from every third floor, i.e. 3rd, 6th, 9th, etc. That'll give a max of 33 throws. Not very efficient, I guess, but, perhaps, it is the shortest walk... Shura

Is this just a binary search, where you always throw from the middle floor of your range. 2**7 is 128, so it should take 7 throws? An example to find the case where the floor = 1: 1 -> 100. Throw from 50. 49 possible left 1 -> 49. Throw from 25. 24 possible left. 1 -> 24. Throw from 13. 12 possible left. 1 -> 12. Throw from 7. 6 possible left. 1 -> 6. Throw from 4. 3 possible left. 1 -> 3. Throw from 2. 1 possible left. Throw from 1. Or have I got this totally wrong?

[ July 25, 2002: Message edited by: Neil Laurance ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

Neil - what you're missing is that if the ball breaks at some point, you no longer can perform a binary search through the remaining possibilities. If at step 1 you drop from floor 50 and it breaks, the only way you can then test all the remaining floors and guarantee that you will get an answer is if you test each remaining floor one at a time, starting at 1. You've only got one ball left at this point, and once it breaks you can't test anything more. So you've got to test lower floors before upper floors, or risk losing the chance to test any more at all.

Neil Laurance
Ranch Hand

Joined: Jul 18, 2002
Posts: 183

posted

0

Aha. A tougher puzzle. I was hoping for an inexhaustible supply of balls

Neil Laurance
Ranch Hand

Joined: Jul 18, 2002
Posts: 183

posted

0

14 as well. Based on square roots.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

So, how many drops would be required if there were three glass balls? I get 9.

I assumed so. From Sameer's original problem statement, it doesn't really seem to matter, does it? You throw a ball out the window, and it either breaks or doesn't break, depending on how X compares to your current floor. The reason for breakage is unspecified. However "it broke because it was traveling too fast when it hit the ground" seems like a reasonable default assumtion. Why do you ask? (And why is this conversation "hidden"?)

Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065

posted

0

Well, in case it's a part of your solution, I did not want to give a clue if nobody explicitely asked for it. "From Sameer's original problem statement, it doesn't really seem to matter, does it?" - it depends. We could put an intermediate surface, say, on the third floor with a small slope toward the ground and throw a ball out of 5th. So it goes 2 floors, perhaps breaks, if not, it goes 3 more floors - and again either breaks or not. I can solve the whole problem with only one throw then. Of course, it will be very well prepared throw... Back to your less-than-optimal solution. On average each your throw defines 7 floors. It is a constant factor, or you somehow reuse information from previous attempts? The former doesn't look feasible, but I would be happy to mistake... [ July 25, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

Cute. But of course the problem statement does not specify exactly when the balls break. Perhaps the city is testing a new missile defense system which vaporizes unidentified objects falling down on the city starting above a certain altitude. In which case the ball might be destroyed the moment it's thrown outside the building above floor X. Which would make your alleged one-throw solution rather difficult. Seriously, no such hypercreative distortions of reality are necessary for this problem. At least, not to solve the problem within 14 throws. On average each your throw defines 7 floors. It is a constant factor, No. or you somehow reuse information from previous attempts? Yes. (What, you think I would ignore perfectly good data from previous efforts? :roll: ) The former doesn't look feasible, but I would be happy to mistake... See, now we can both be happy.

Sameer Jamal
Ranch Hand

Joined: Feb 16, 2001
Posts: 1870

posted

0

Here is the solution Suppose we have a strategy with N throws. Then the floor is defined by two numbers: the throw, when the first ball brakes, and the throw, when the second ball brakes. The sum of those two numbers should be less or equal to N. Hence the number of floors we can distinguish is the number of different pairs of such numbers, which is equal to N(N+1)/2. This number should be more than 99. Hence, we need at least 14 throws(Jim u got it). Now we would like to build a strategy. To decide the floor for our first throw we observe that if the ball brakes we need to decide between the leftover floors in 13 steps. Which means to maximize our choices for the case when it doesn't brake we need to use all the opportunities. That is we should throw the ball from the 14th floor first. If it brakes we use the second ball starting from the first floor up. Second throw should be from the 14 + 13 = 27th floor. And so on.

Neil Laurance
Ranch Hand

Joined: Jul 18, 2002
Posts: 183

posted

0

Please stop posting these puzzles. I didn't sleep a wink last night

living in 100 story building and doing all this ??? tooo baaad.......

- Varun

Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065

posted

0

Hey, Sameer, do not post solution so fast! We lost only one night sleep! (Kidding. I *was* sleeping, but when woke up couldn't go sleep again. ) Couldn't figure how Jim came to his flawed 14-steps solution: Perhaps the city is testing a new missile defense system which vaporizes unidentified objects falling down on the city starting above a certain altitude. In which case the ball might be destroyed the moment it's thrown outside the building above floor X. In this case it's one-throw solution also. You just throw the ball up, no down, and watch near which floor it gets vaporizes. Seriously, it's a good puzzle. It takes to think what is *really* being asked, to abstract from floors and balls falling down. Of course now I am at both Sameer and Jim, and I suspect not only I... Hm... [ July 26, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

In this case it's one-throw solution also. You just throw the ball up, no down, and watch near which floor it gets vaporizes. Note that the way I phrased it, the missile defense system only targets unidentified objects falling down on the city. So your one-throw solution won't work, as the ball can pass all floors on the way up, only to be vaporized when it reverses direction. If you're disappointed that Sameer posted his solution too quickly, you can always try answering the followup question I posed: how many drops would be required if there were three glass balls, rather than two?

Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065

posted

0

Note that the way I phrased it, the missile defense system only targets unidentified objects falling down on the city. So your one-throw solution won't work, as the ball can pass all floors on the way up, only to be vaporized when it reverses direction. Well, you did not leave me any chance but to resort to methodical balls throwing... If you're disappointed that Sameer posted his solution too quickly, you can always try answering the followup question I posed: how many drops would be required if there were three glass balls, rather than two? The most difficult part was to abandon monotonically creeping solutions as it wouldn't move us anywhere besides 3 floors per throw. A jump from 2 glass balls to 3 glass balls isn't as mentally radical, or so I believe... Pick any floor, and if the glass ball is broken we have the previous problem with floor number substituted for 100... How about 8?

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

How about 8? Well, if you have a working solution for 8 drops then that's better than my solution. (See inviso-text at the end of my original 3-ball question above.) But I'm skeptical that such a solution really exists. [ July 29, 2002: Message edited by: Jim Yingst ]

Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065

posted

0

Like if I care what the right answer + 1 is! :roll: By the way, where this crazy n(n+1)/2 formula came from? Doing reverse engineering, there are a lot of possible combinations, like checking every 5th floor with the first ball (20 times in worst case) and then in case of positive result checking 3 more... As I understand, the trick is to keep the sum of actual (already made) and potential (possible needed) throws constant. Since actual attempts are incremented on each step, potential should be decremented - number of floors should be reduced by 1 on every next step. So if the floor where we started is n, then it would be n + (n-1) + (n-2) + ... + 2 + 1 >= 100 And sum of this series is n(n+1)/2 from where Yingst got his 14 (unless he simply went to the nearest skyscraper with a bunch of glass balls...) Now if we want to apply the same technique to the 3 balls case (this part is "invisible" for this unlikely occasion someone is still throwing balls...)

We want to decrement number of floors on each attempts also, but now when we have two balls left, we do not have to test each floor, we can reuse the formula from previous case. Instead of 1, 2, 3 ... we use its result on 1, 2, 3 etc. summing up until we get more than 100: 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = 120 So we first go to the 36th floor, where in the worst case we will have to make 8 throws (and Jim thoughtfully added one already made attempt - which, of course, only proves that he is arrogant, ignorant and didn't read all/his own posts in this thread ) , then if it doesn't work, we go to the 36+28=64th floor etc.

I am waiting in full trepidation for James Yingst's denunciation of this algorithm... :roll: [ July 30, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

So, your first drop is from the 36th floor, right? Let's say it breaks. You now have 2 balls and 7 drops left. How do you proceed?

Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065

posted

0

I would go on the 8th floor, then on the 15th etc. and if I run out of attempts, I'll borrow one from you Um, now I re-read my post and it looks like I disagree with your final "9" verdict. This is untrue, I wrote all my philippics assuming you are right, otherwise I wouldn't write them. Sorry for confusion (if there is such). Is 36th floor Ok now or you are going to drive me crazy some more? [ July 30, 2002: Message edited by: Mapraputa Is ]

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

Is 36th floor Ok now or you are going to drive me crazy some more? Yes. I'm not entirely convinced you're calculating this correctly, so: what's the largest number of floors a building could have such that the problem can be solved with 3 balls and 8 drops? And what if you get 9 drops? See what happens when you complain you didn't get enough time to work on a problem - you just get assigned more problems.

Sameer Jamal
Ranch Hand

Joined: Feb 16, 2001
Posts: 1870

posted

0

Originally posted by Jim Yingst: How about 8? [ July 29, 2002: Message edited by: Jim Yingst ]

General problem: Suppose you have N different objects, one of them is special. By performing some operation you need to find a special object in a minimum amount of steps. General solution: Count the maximum amount of different outcomes of your operation in K steps. Denote this amount by f(K). It is clear that to distinguish all objects you need to have the number of steps such that f(K) ≥ N. Your strategy should be the following: make the first step in such a way that it divides all the objects into groups depending on outcome and each group requires the smallest amount of steps.