login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180975 Array of the "egg-drop" numbers, read by downwards antidiagonals. 2
1, 1, 2, 1, 3, 3, 1, 3, 6, 4, 1, 3, 7, 10, 5, 1, 3, 7, 14, 15, 6, 1, 3, 7, 15, 25, 21, 7, 1, 3, 7, 15, 30, 41, 28, 8, 1, 3, 7, 15, 31, 56, 63, 36, 9, 1, 3, 7, 15, 31, 62, 98, 92, 45, 10 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

The egg-drop problem is as follows. We wish to determine the highest floor in a building such that an egg dropped from that floor will not shatter. We have a set of k identical eggs for dropping; note that an egg that does not shatter can be reused to test higher floors. Then T(n,k) is the largest number of floors that can be tested using at most n drops and k eggs.

Suppose one is given k eggs and a building of f floors. Then the worst-case number of drops WC(k,f) to test all the floors satisfies the dynamic programming equation

. WC(k,f) = 1 + max_{g in 1..f} { WC(k-1, g-1), WC(k, f-g) }

with boundary conditions

. WC(1,f) = f and WC(k,0) = 0

where g is the floor chosen for the next drop. One can substitute f -> T(n,k) and g -> T(n-1,k-1)+1 = f-T(k-1,j). Then by an inductive argument, it is verified that WC(j,T(n,j)) = n as expected.

T(n,2) = n(n+1)/2. This leads to the commonly-used heuristic solution for 2 eggs of dropping from the sqrt(f), 2*sqrt(f), 3*sqrt(f) etc. floors until the first egg breaks. T(n,j) is a j-th order polynomial in n, and so this heuristic may be generalized: drop from multiples of f^((j-1)/j) until the j-th egg breaks.

REFERENCES

J. Kleinberg and E. Tardos, "Algorithm Design", Addison-Wesley Longman Publishing Co. Inc., 2005. Problem 2.8.

D. Velleman, "Which Way Did The Bicycle Go? And Other Intriguing Mathematical Mysteries (Dolciani Mathematical Expositions)", The Mathematical Association of America, 1996, "166. An Egg-Drop Experiment" pages 53 and 204-205.

LINKS

G. C. Greubel, Antidiagonals n = 1..100 of array, flattened

Michael Boardman, The Egg-Drop Numbers, Mathematics Magazine, 77 (2004), 368-372.

FORMULA

Recursive formula: T(n,k) = T(n-1,k-1) + 1 + T(n-1,k) with boundary conditions T(0,k) = T(n,0) = 0.

T(n,k) = Sum_{j=1..k} binomial(n,j).

From the journal article by Boardman, the generating function for a fixed value of n is g_n(x) = ((1+x)^n - 1) / (1-x).

G.f.: x*y/((1-y)*(1-x)*(1-x-x*y)). - Vladimir Kruchinin, Oect 09 2018

EXAMPLE

T(n,1) = n. With only a single egg, one must drop the egg from the first floor, then the second, and so on until it finally breaks. At most n floors may be tested this way.

If one is allowed fewer drops than eggs, a simple binary search is optimal. Hence T(n,k) = 2^n-1 for n <= k. Note that one cannot test 2^n floors in this case. For example, suppose one had 2 drops and a 4-story building; dropping from either the second or third floor could leave another two floors to test, but only one drop remaining.

The square array starts in row n=1 with columns k >= 1:

  1:  1  1  1  1  1  1  1  1  1

  2:  2  3  3  3  3  3  3  3  3

  3:  3  6  7  7  7  7  7  7  7

  4:  4 10 14 15 15 15 15 15 15

  5:  5 15 25 30 31 31 31 31 31

  6:  6 21 41 56 62 63 63 63 63

MAPLE

T:= proc(n, k) option remember;

if n = 0 or k = 0 then 0

else T(n-1, k-1) + 1 + T(n-1, k)

fi

end proc:

seq(seq(T(i, m-i), i=1..m-1), m=1..20); # Robert Israel, Jan 20 2015

MATHEMATICA

T[n, k] = Sum[Binomial[n, j], {j, 1, k}]; Table[T[k, n-k], {n, 2, 15}, {k, 1, n-1}]//Flatten (* modified by G. C. Greubel, Oct 09 2018 *)

PROG

(PARI) for(n=2, 15, for(k=1, n-1, print1(sum(j=1, n-k, binomial(k, j)), ", "))) \\ G. C. Greubel, Oct 09 2018

(MAGMA) [[(&+[Binomial(k, j): j in [1..n-k]]): k in [1..n-1]]: n in [2..15]]; // G. C. Greubel, Oct 09 2018

(GAP) nmax:=11;; T:=List([1..nmax], n->List([1..nmax], k->Sum([1..k], j->Binomial(n, j))));;

b:=List([2..nmax], n->OrderedPartitions(n, 2));;

a:=Flat(List([1..Length(b)], i->List([1..Length(b[i])], j->T[b[i][j][1]][b[i][j][2]]))); # Muniru A Asiru, Oct 09 2018

CROSSREFS

Cf. A004070, A117670.

Cf. A131251 (transpose).

Sequence in context: A234951 A291302 A278493 * A210216 A195915 A219158

Adjacent sequences:  A180972 A180973 A180974 * A180976 A180977 A180978

KEYWORD

easy,nice,nonn,tabl

AUTHOR

Francis Carr (fcarr(AT)alum.mit.edu), Sep 30 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 15:04 EST 2020. Contains 332019 sequences. (Running on oeis4.)