Research Notes

An analysis of a bounded resource search puzzle

September 28, 2026 · slides from a JMM talk

Consider a building with n floors, and suppose that we hold k identical glass balls and want to find the lowest floor from which a ball breaks, so that the question is the least number m of throws that finds this floor in the worst case. For k = 2 the answer is well known, whereas 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 this solution at the Joint Mathematics Meetings.

Let P(m, k) be the largest number of floors that m throws and k balls can resolve, and consider the first throw. Either the ball breaks, which leaves m − 1 throws and k − 1 balls for the floors below, or the ball survives, which leaves m − 1 throws and k balls for the floors above, and 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). Thus the least m for n floors is the one with P(m−1, k) < n ≤ P(m, k). It is worth noting that there is no closed form for general k, although for k = 2 the bound reduces to m = ⌈(√(8n+1) − 1)/2⌉, and for k ≥ m it reduces to m = log2(n+1), i.e. binary search.

The main-result slide: for any k, 1 plus the sum of C(m-1, i) is less than n, which is at most the sum of C(m, i)
The main result, which is slide 4 of 18. Click the image to open the full deck.

The talk also covers which floors to try, a look at the polynomial Σ C(m, j) = n, variations of the puzzle, and four applications, namely 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. Note that 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, so any change to the file after signing invalidates the signature. Since the certificate is our own and was issued by no public authority, 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.

← All posts