How to throw 2 eggs from a building and find the floor F with ~c*sqrt(F) throws?

Question

I am reading Robert Sedgewick's algorithms 4th edition book, and he has the following task:

Suppose that you have an N-story building and 2 eggs. Suppose also that an egg is broken if it is thrown off floor F or higher, and unbroken otherwise. Your cost model is the number of throws. Devise a strategy to determine F such that the number of throws ~c √ F for some constant c.

The first part of the task is to find F in 2 √ N steps, and here's a solution for that:

Solution to Part 1:

• To achieve 2 * sqrt(N), drop eggs at floors sqrt(N), 2 * sqrt(N), 3 * sqrt(N), ..., sqrt(N) * sqrt(N). (For simplicity, we assume here that sqrt(N) is an integer.)
• Let assume that the egg broke at level k * sqrt(N).
• With the second egg you should then perform a linear search in the interval (k-1) * sqrt(N) to k * sqrt(N).
• In total you will be able to find the floor F in at most 2 * sqrt(N) trials.

He also provides a hint for the ~c √ F part (part 2):

Hint for Part 2: 1 + 2 + 3 + ... k ~ 1/2 k^2.

So what is the algorithm to do it in ~c √ F steps?

Answer 1

Drop first egg from floors 1, 3, 6, ... (the partials sums of 1, 2, 3, ...). Then do linear search between last two floors.