Math Puzzle [num 20]

I would assume that since you don't want to run out of eggs you would start at floor 2. If it doesn't break, go to floor 4. When you finally get a break, you go down a floor. If that egg doesn't break you are at the floor that is highest without breaking. Otherwise it's the floor underneath you.

Of course, this takes 50 drops, so it's probably suboptimal.

1. Drop egg on Floor 3. If it doesn't break, jump to 4.
2. If it breaks, drop on floor 2. If no break - done.
3. If it broke on floor 2, done... it's floor 1.
4. Repeat step #1 on floor X + 2 where X is the floor from step #1.

**edit** I guess it is possible that the egg breaks even from floor 1, so this wouldn't work

I'd do the first drop on 33 (1/3). If it breaks, go up from 2. If it doesn't break, go to 55 (1/3). If it breaks, go up from 34. If it doesn't break, go up to 70. If it breaks, go up from 56. If it doesn't break, go up to 80. Etc. No idea if it's ideal but I think it's decent XD

Let us define a process A that averages the value of the highest known failure level, and lowest known success value. In the case of non-integer values, round up. We initially start with the assumption an egg dropped from floor 0 will not crack.

Start at the highest level, 100. Drop Egg. If success, end test. If failure, run process A. Return 50 and repeat test at 50.

If failure or success at 50, run Process A again. So if 50 was a success, you go to 75. If it was a failure you go to 25. Repeat this continuously until Process A returns the same value as the floor you are currently on. This is your maximum floor.

This should only require around 8 tries maximum. Too lazy to calculate the expected value and variance of the number of tries for a scenario where each floor has a equal probability of being the successful level. Also, if you consider the probability of success as the floor level increases to be a decreasing function (as common sense would dictate), other methodologies would be more efficient at solving this problem as the expected value would be lower. However, this methodology returns the lowest number of maximum attempts necessary.

If you don't want the assumption an egg at level 0 does not crack, then run at test there first. If it cracks, then no floor exists where the egg will not crack. This brings the maximum number of tests to run to 9, but not a big deal. Still less than 10.

If you drop at 50 and it breaks and then at 25 and it breaks then you start dropping scrambled eggs.

I think this is the right idea, but there has to be some way to pick what the correct ratio is to minimize the number of drops needed (I'm assuming you picked 1/3 relatively arbitrarily)

Think about it this way: let h be the highest floor you know it won't break at. Let b be the floor for which the first egg breaks. You will need to then start at h+1 and work up to (b-1) with the second egg.

So, you want to minimize the # of drops of the first egg + b-1-(h+1). Assume you employ a strategy where you pick an increment i and drop the first egg at floors I, 2i, 3i, etc. When the first egg breaks, you will then need I-1 drops (at most) for the second egg. The first egg would have to be dropped 100/I times. So, we wish to minimize 100/I + (I-1). A quick check for reasonable values (you could use calculus as well) will show 10 is the ideal increment. Drop the first egg at floors 10,20,30. First egg will be dropped at most 10 times, and second egg dropped at most 9. Notice that if the increment is 7,8,9,11,12,13, the total number of drops necessary in worst case is also 19 (I think).

Sorry, wrote this on my phone so hard to double check this math. I think 19 is the best you can do

you drop from 10 if it doesnt break you move up 10 (10-100max 10 drops) then once that egg breaks say at like 20 then you drop from 11 and increment by 1 (11-19, max 9) so you're max number of drops is 19

Drop from 9th floor. If breaks, start at floor 1, if not go to floor 18. If it breaks, restart at floor 10, if not go to floor 27. Then the worst case scenario is it takes you getting to the 99th floor on testing which is 18 drops, as opposed to the potential 34 from Micronesia.

Also, going to the 10th provides a worst case of 19, and dropping from the 8th is a worst case of 19 as well, so I'm pretty sure the 9 floor steps is optimal. But there may be another method that's more optimal than this.

EDIT** Un-even dropping intervals may be more optimal but I'm not sure how to calculate this (i.e., we start at 20, then move up to say like 37, then 53, etc.).

drop your first egg at the following floors, in order. if it breaks at 1 go down to the previous one and start incrementing by 1
15
29
42
54
65
75
84
92
100
your max drops are 16. i don't think this is optimal... i tried starting at floor 14 but then you peter out at 95. i'm probably doing math wrong somewhere.
e: flamewheel is better at addition than i

Guess and check since I'm too dumb to prove stuff!

I'm a fan of square roots. Go with every 10 floors. Start from floor 10, and if the egg breaks check linearly up from floor 1 with egg 2. Barring a break on floor 10, go up by 10 at a time. So 10, 20, 30, 40... If egg 1 breaks, go down 9 floors from the multiple of ten you're on, and check upward with egg 2.

Maximum number of steps is 10 + 9 = 19 if the breaking floor is 99.

I dont't this is optimal. Let's see...

15 floors at a time?

15 30 45 60 75 90 100
If egg breaks on 89 then that's 6 + 14 = 20.

Hmm somewhere in between that.
What about 13?

13 26 39 52 65 78 91 100
Breaking at floor 90... 7 + 12 = 19

14 28 42 56 70 84 98 100
Breaking at floor 97 means 6 + 13 = 19 as well

I still don't think this is right. Hmm... maybe a decreasing jump size?

So 10 floors, 9 floors, 8 floors, 7 floors...

Trying with jump size initial equal to 10 is too many 'jumps'.

Maybe 15?

15 29 42 54 65 75 84 92 99 100
Breaking at floor 15 means 1 + 14 = 15
Breaking at floor 29 means 2 + 13 = 15
...
Breaking at floor 99 means 9 + 6 = 15
Breaking at floor 100 means 10

So perhaps initial jump size is max number of tries needed?

Try jump size initial equal to 14 then

14 27 39 50 60 69 77 84 90 95 99 100
@floor 14: 1 + 13 = 14
@floor 27: 2 + 12 = 14
...
@floor 99: 11+3 = 14
@floor 100: 12

Hmm so perhaps it is better to have jump size decrease to close to one when we near floor 100

13 25 36 46 55 63 70 76 81 85 88 90 91
So initial jump size of 13 fails

Seems like 14 looks nice.

We will be jumping floors. The first jump is from ground level to floor 14, so a jump size of 14 floors. Decrease jump size by 1 floor after each jump. Therefore, from 14, jump by 13 floors to 27. From there, jump by 12 to 39... So forth and so on. When the egg breaks, start from the floor higher than the last pre-jump floor (so if egg 1 breaks on floor 39, start dropping egg 2 from floor 28). It should take a maximum number of 14 tries.

Using the decreasing jump size method, we find it should only take as many tries as the initial jump size, but only if we can reach 100 before jump size becomes zero. An initial jump size of 13 fails since you only reach 91 floors, and a jump size of 15 takes 15 tries maximum.