They say that when a great fortune teller, when building his new crystal ball, he wanted to know its resistance to falls. So he made three equal balls, kept one for him and handed the other two to his apprentice to whom he entrusted the mission of checking their resistance. For this he ordered him to go to the tallest building in the city with 117 stories high and said: you must go up to the first floor of the building and throw the ball through the window. If the ball does not break, go down to pick it up and repeat the test on the second floor. Do the same for each of the floors of the building until you find out how high the ball is capable of resisting without breaking. Be careful that you only have two balls and when you break the second one you will not be able to do any more tests.

The magician's apprentice who was not too hard-working thought about the way the check was made by the magician with as few tests as possible, since it seemed a very arduous task to go up and down stairs as many times and in the worst of cases would have to do 117 tests!

**Can you think of any more efficient way to find the floor where the balls would break without having to try all the floors one by one?**

Extracted from the Zurditorium.com page

#### Solution

**It is possible to check by throwing the ball up to 15 times**.

The strategy will be to make a test on a specific floor so that in case of breakage of the first ball the number of attempts with the second ball can be bounded on the lower floors. We will call X the maximum number of checks we want to perform. So we know that if we throw the first ball from the X floor and it breaks, we will have to test all the lower floors from 1 to X-1 which will make a maximum of X tests.

If on the X floor the ball does not break, we will have X-1 checks so we can test on the X + floor (X-1). If the first ball is broken we will have to test all the floors one by one from X + 1 to X + (X-1) - 1 until the second ball is broken which will again make a maximum of X tests.

Following the same procedure, the next floor to be tested would be the X + (X-1) + (X-2). Again, if the first ball breaks on that floor, we will have to test all the floors one by one from X + (X-1) + 1 to X + (X-1) + (X-2) - 1 with the second ball until it breaks.

If you look we are creating an equation X + (X-1) + (X-2) + (X-3) +… + (X- (X-1)) whose sum must be greater than or equal to the total number of floors .

Thus, for example if we take X = 14 we would have 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 105 so in the worst case we would not arrive at the total height of the building and if we take X = 15 we would have 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 120 so we would have enough to test all necessary floors following the system described.

Thus, the strategy would be as follows:

We do the first test on the 15th floor. If the ball breaks, we then test with the second ball one by one all the floors that go from 1 to 14 until the second ball is broken and that will be the maximum height that resists the ball.

If the first ball does not break on the 15th floor, in the second attempt we will throw it from the 15th floor + 14 = 29.

If the first ball is broken, we will test with the second ball one by one all the floors from the 16th to the 28th (13 floors) until it is broken.

If the first ball did not break on the 29th floor, we now test on the 15 + 14 + 13 = 42 floor, if it breaks, we would have to test all the floors one by one from 30 to 41 until we found the floor in the That the second ball is broken.

And we would continue with this procedure until we reach the 117th floor. It is clear that in this way we would find the highest floor from which we can throw the ball without breaking at most in 15 attempts.

You will find a more detailed solution on the Zurditorium.com page