

A180975


Array of the "eggdrop" 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 eggdrop 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 worstcase 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(k1, g1), WC(k, fg) }
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(n1,k1)+1 = fT(k1,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 commonlyused 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 jth order polynomial in n, and so this heuristic may be generalized: drop from multiples of f^((j1)/j) until the jth egg breaks.


REFERENCES

J. Kleinberg and E. Tardos, "Algorithm Design", AddisonWesley 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 EggDrop Experiment" pages 53 and 204205.


LINKS

G. C. Greubel, Antidiagonals n = 1..100 of array, flattened
Michael Boardman, The EggDrop Numbers, Mathematics Magazine, 77 (2004), 368372.


FORMULA

Recursive formula: T(n,k) = T(n1,k1) + 1 + T(n1,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) / (1x).
G.f.: x*y/((1y)*(1x)*(1xx*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^n1 for n <= k. Note that one cannot test 2^n floors in this case. For example, suppose one had 2 drops and a 4story 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(n1, k1) + 1 + T(n1, k)
fi
end proc:
seq(seq(T(i, mi), i=1..m1), m=1..20); # Robert Israel, Jan 20 2015


MATHEMATICA

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


PROG

(PARI) for(n=2, 15, for(k=1, n1, print1(sum(j=1, nk, binomial(k, j)), ", "))) \\ G. C. Greubel, Oct 09 2018
(MAGMA) [[(&+[Binomial(k, j): j in [1..nk]]): k in [1..n1]]: 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



