Untitled attachment

Notices where this attachment appears

1. Embed this notice
   mist (ai@cawfee.club)'s status on Thursday, 21-Sep-2023 07:03:07 JST mist

   in reply to
   @ExtraSpecialK @mia @p @shibao @meso
   Here's the answer to the originally-posted question (see pic), with N floors and E eggs.
   
   For any M, define S(M, E) to be the number of ways to choose at most E elements from a set of size M. In other words, it's the sum of the first (E+1) numbers in the (M+1)-st row of Pascal's Triangle.
   
   The answer is the smallest M such that S(M, E) > N.
   
   To see why S(M, E) shows up, consider the possible outcomes of performing M drops. Each outcome can be summarized by saying, for each drop, whether a crack happened at that drop. Since we only have E eggs, there can be at most E cracks, so the set of possible outcomes has size at most S(M, E).
   
   Since there are N+1 possible answers, we certainly need M to be big enough such that S(M, E) >= N+1. This shows that the claimed answer is a lower bound.
   
   To show that it's an upper bound, we have to construct a strategy. The key is to observe that S(M-1, E-1) + S(M-1, E) = S(M, E) + 1, essentially by Pascal's Identity. Do the first drop from floor S(M-1, E-1). If the egg survives, then we have E eggs left and at most S(M-1, E) - 1 floors to rule out. If the egg cracks, then we have E-1 eggs left and exactly S(M-1, E-1) - 1 floors to rule out. In either case, we can proceed inductively.
   
   cc @ceo_of_monoeye_dating @MercurialBlack @scenesbycolleen @roboneko