A building has n floors and we hold k identical glass balls. We want the lowest floor from which a ball breaks, and we ask for the least number m of throws that finds it in the worst case. For k = 2 the answer is well known. For general k the puzzle was first posed in FOCS 1980, and in 2004 we gave a dynamic-programming solution (arXiv cs/0405110). The slides below are from our talk on it at the Joint Mathematics Meetings.
Let P(m, k) be the largest number of floors that m throws and k balls can resolve. A first throw either breaks the ball, leaving m − 1 throws and k − 1 balls for the floors below, or does not, leaving m − 1 throws and k balls for the floors above. Hence
P(m, k) = 1 + P(m−1, k) + P(m−1, k−1),
with P(0, k) = P(m, 0) = 0, and the solution is P(m, k) = Σj=1..k C(m, j). The least m for n floors is therefore the one with P(m−1, k) < n ≤ P(m, k). There is no closed form for general k. For k = 2 the bound reduces to m = ⌈(√(8n+1) − 1)/2⌉, and for k ≥ m to m = log2(n+1), i.e. binary search.
The talk also covers which floors to try, a look at the polynomial Σ C(m, j) = n, variations of the puzzle, and four applications: measuring an event horizon, finding the start of a run of zeros in a data stream, locating a node that swallows web crawlers in a Byzantine network, and minimum search in convex models. The same count located the hidden step budget in our Busy Beaver 6 search.
Download the slides (PDF, 4.2 MB)
The signature
The PDF is digitally signed by KnotTheory.ai Inc. and carries a timestamp from FreeTSA. Any change to the file after signing invalidates the signature. The certificate is our own rather than one issued by a public authority, so a PDF reader reports the signer as unknown until the certificate is trusted. To check it, download our signing certificate, confirm that its SHA-256 fingerprint is
1E:4C:26:93:30:B9:8D:E3:B5:A4:A0:64:DC:CC:13:92:CF:99:D5:F9:BC:8C:B5:23:C7:25:C8:B7:06:FB:C1:B0,
and add it as a trusted certificate in your reader.