Shura

Any posted remarks that may or may not seem offensive, intrusive or politically incorrect are not truly so.

RusUSA.com - Russian America today - Guide To Russia

Sheriff

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 ]

Sheriff

*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.

"I'm not back." - Bill Harding, *Twister*

Sheriff

Sheriff

Sheriff

"I'm not back." - Bill Harding, *Twister*

Sheriff

"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 ]

Uncontrolled vocabularies

"I try my best to make *all* my posts nice, even when I feel upset" -- Philippe Maquet

Sheriff

*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.

"I'm not back." - Bill Harding, *Twister*

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.

Sheriff

**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 ]

Uncontrolled vocabularies

"I try my best to make *all* my posts nice, even when I feel upset" -- Philippe Maquet

Sheriff

**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?

"I'm not back." - Bill Harding, *Twister*

Sheriff

**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?

Sheriff

**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 ]

"I'm not back." - Bill Harding, *Twister*

Sheriff

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 ]

Uncontrolled vocabularies

"I try my best to make *all* my posts nice, even when I feel upset" -- Philippe Maquet

Sheriff

Sheriff

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 ]

"I try my best to make *all* my posts nice, even when I feel upset" -- Philippe Maquet

Sheriff

**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.

"I'm not back." - Bill Harding, *Twister*

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.