Two-Ball Average Drops 20 - Quant Problems

Approach

Let E(e,n) be the minimum expected drops with e balls and n unresolved floors, with the threshold uniformly distributed over the n+1 possible positions. If one ball remains, the best method is linear search. With two balls, try each first drop x and combine the break branch E(1,x-1) with probability x/(n+1) and the survive branch E(2,n-x) with probability (n-x+1)/(n+1), adding one current drop. The recurrence minimizes over x. For n = 20, the minimum is exactly 5.

Approach

Let E(e,n) be the minimum expected drops with e balls and n unresolved floors, with the threshold uniformly distributed over the n+1 possible positions. If one ball remains, the best method is linear search. With two balls, try each first drop x and combine the break branch E(1,x-1) with probability x/(n+1) and the survive branch E(2,n-x) with probability (n-x+1)/(n+1), adding one current drop. The recurrence minimizes over x. For n = 20, the minimum is exactly 5.