[SebC]

Originally Posted by psyang

I had another good number theory type problem, but I'll do that later. People seem to enjoy the more "practical" ones. So try this one.

You have two balls made of some new substance, and you want to determine the highest floor of a 100 storey building from which you can drop a ball and have it not break. Once a ball breaks, it can't be used again.

The brute force method would be to start at the first floor, and keep dropping a ball until it breaks. Then the previous floor would be the answer. This could take up to 100 drops, however (assuming the first floor starts above the main floor).

What's the minimum number of drops you must make to figure this out?

Spoiler!

1, if it happens to break on the first drop

But I assume what you're actually asking about is the minimum maximum (i.e. the minimum assuming the worst possible outcome for your algorithm).

Trial and error musings:

Spoiler!

First instinct was drop in the middle, reduce requirement in half. But then, if survives, you still have two balls. Next, considered dropping at 1/3rd... but the size of the group needed to brute force was decreasing too fast. Guesstimate 1/4?

Drop it from 25 ... if it breaks, brute force from 1 to 24 (25 total)

If it does not break, you still have two balls. Drop it from 44. If it breaks, brute force from 26 to 44 (drop at 25, drop at 44, 26 to 44= 21 total).

If it does not break, drop from 58. If it breaks, brute force from 45-57 (drops at 25,44,58 + 45 to 57 = 16 total).

If it does not break, drop from 69. If it breaks, brute force from 59-68 (drops at 25,44,58,69 + 59 to 68 = 14 total).

If it does not break, drop from 77. If it breaks, brute force from 70-78 (drops at 25,44,58,69,77 + 70 to 78 = 14 total).

If it does not break, drop from 85. If it breaks, brute force from 78-84 (drops at 25,44,58,69,77,85 + 78 to 84 = 13 total).

If it does not break, drop from 90 . If it breaks, brute force from 86-89 (drops at 25,44,58,69,77,85,90 + 86 to 89 = 11 total).

If it does not break, drop from 93...

Pattern: for the the total number of drops to be maintained the size of the brute force group decreases by 1 each time.

Working backwards, brute force groups:

If it breaks when you drop at 100, brute force 99.
If it breaks when you drop at 98, brute force 96 to 97.
If it breaks when you drop at 95, brute force 94 to 92.
If it breaks when you drop at 91, brute force 87 to 90.
If it breaks when you drop at 86, brute force 81 to 85.
If it breaks when you drop at 80, brute force 74 to 79.
If it breaks when you drop at 73, brute force 66 to 72.
If it breaks when you drop at 65, brute force 55 to 64.
If it breaks when you drop at 54, brute force 45 to 53.
If it breaks when you drop at 44, brute force 34 to 43.
If it breaks when you drop at 33, brute force 22 to 32.
If it breaks when you drop at 21, brute force 9 to 20.
If it breaks when you drop at 8, brute force 1 to 7.

I.e. in the sequence

Drop at 8 (1)
If it breaks when you drop at 8, brute force 1 to 7. (8 total)

Otherwise, drop at 21. (2)
If it breaks when you drop at 21, brute force 9 to 20. (14 total)

Otherwise, drop at 33. (3)
If it breaks when you drop at 33, brute force 22 to 32. (14 total).

...

So yeah, 14.

Will wait for psyang's answer to me before looking at the rest of your spoilers.