1,2

Imagine that you are in a building with floors starting at floor 1, the lowest floor, and you have a large number of eggs. For each floor in the building, you want to know whether or not an egg dropped from that floor will break.

If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j > i. Likewise, if an egg doesn't break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j <= i.

a(n,k) is the maximum number of floors where you can determine whether or not an egg will break when dropped from any floor, with the following restrictions: you may drop a maximum of n eggs (one at a time, from any floors of your choosing), and you may break a maximum of k eggs.

Each row of the triangle is the running sum of the corresponding row with the first 1 omitted of Pascal's triangle (A007318).

Google code.jam

Triangular array by rows: a(n,1)=n ; a(n,n)=2^n-1; a(n+1,k+1) = 1 + a(n,k) + a(n,k-1) (0 < k < n )

Triangle begins:

1,

2,3,

3,6,7,

4,10,14,15,

5,15,25,30,31,

6,21,41,56,62,63,

...

Sequence in context: A101437 A039856 A143715 this_sequence A025499 A022474 A028249

Adjacent sequences: A117667 A117668 A117669 this_sequence A117671 A117672 A117673

nonn,tabl

Arie Bos (arie.0.bos(AT)gmail.com), Jul 06 2008, Jul 08 2008