|
| |
|
|
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
|
|
|
|
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).
|
|
|
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
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def T(n, k): return 0 if n*k == 0 else T(n-1, k-1) + 1 + T(n-1, k)
print([T(k, n-k) for n in range(1, 12) for k in range(1, n)]) # Michael S. Branicky, Apr 04 2021
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
Francis Carr (fcarr(AT)alum.mit.edu), Sep 30 2010
|
|
|
STATUS
|
approved
|
| |
|
|
