The egg drop problem where the aim is to minimise the time taken
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
In the standard egg drop problem you are in front of a 100-storey building and by dropping eggs from $k$ different floors you plan to find the lowest floor from which you can drop an egg without breaking it. Your task is to find the smallest $k$ that will ensure you are successful. The answer is 14, or if we replace 100 with $n$ it is $ leftlceil sqrt2n - frac12 rightrceil$.
Let us now change the problem so that it takes 1 minute to travel up or down a storey. Nothing else takes any time. You start outside the building. Your task is not to minimise $k$ but to minimise $t$, the time you need to allow, measured in minutes.
A further problem is to find a floor-choosing method that will minimise the mean $t$ required.
problem-solving
asked Aug 13 at 10:03
ruffle
1033
add a comment |Â
up vote
0
down vote
favorite
In the standard egg drop problem you are in front of a 100-storey building and by dropping eggs from $k$ different floors you plan to find the lowest floor from which you can drop an egg without breaking it. Your task is to find the smallest $k$ that will ensure you are successful. The answer is 14, or if we replace 100 with $n$ it is $ leftlceil sqrt2n - frac12 rightrceil$.
Let us now change the problem so that it takes 1 minute to travel up or down a storey. Nothing else takes any time. You start outside the building. Your task is not to minimise $k$ but to minimise $t$, the time you need to allow, measured in minutes.
A further problem is to find a floor-choosing method that will minimise the mean $t$ required.
problem-solving
asked Aug 13 at 10:03
ruffle
1033
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
In the standard egg drop problem you are in front of a 100-storey building and by dropping eggs from $k$ different floors you plan to find the lowest floor from which you can drop an egg without breaking it. Your task is to find the smallest $k$ that will ensure you are successful. The answer is 14, or if we replace 100 with $n$ it is $ leftlceil sqrt2n - frac12 rightrceil$.
Let us now change the problem so that it takes 1 minute to travel up or down a storey. Nothing else takes any time. You start outside the building. Your task is not to minimise $k$ but to minimise $t$, the time you need to allow, measured in minutes.
A further problem is to find a floor-choosing method that will minimise the mean $t$ required.
problem-solving
asked Aug 13 at 10:03
ruffle
1033
In the standard egg drop problem you are in front of a 100-storey building and by dropping eggs from $k$ different floors you plan to find the lowest floor from which you can drop an egg without breaking it. Your task is to find the smallest $k$ that will ensure you are successful. The answer is 14, or if we replace 100 with $n$ it is $ leftlceil sqrt2n - frac12 rightrceil$.
Let us now change the problem so that it takes 1 minute to travel up or down a storey. Nothing else takes any time. You start outside the building. Your task is not to minimise $k$ but to minimise $t$, the time you need to allow, measured in minutes.
A further problem is to find a floor-choosing method that will minimise the mean $t$ required.
problem-solving
asked Aug 13 at 10:03
ruffle
1033
asked Aug 13 at 10:03
ruffle
1033
asked Aug 13 at 10:03
ruffle
1033
asked Aug 13 at 10:03
ruffle
1033
1033
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Then there is no faster algorithm than just dropping an egg from each floor as you ascend; if you wanted to start from floor $x$, it would take $x$ minutes to reach that floor to begin, in which time you could have tested every floor up to $x$ anyway.
Thus: drop an egg from each floor. The worst case time would be $n$, which would always require at least $n$ minutes to find out simply because you must travel to that floor to distinguish between a solution of $n$ and $n-1$.
answered Aug 13 at 10:08
Phil H
9531513
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Then there is no faster algorithm than just dropping an egg from each floor as you ascend; if you wanted to start from floor $x$, it would take $x$ minutes to reach that floor to begin, in which time you could have tested every floor up to $x$ anyway.
Thus: drop an egg from each floor. The worst case time would be $n$, which would always require at least $n$ minutes to find out simply because you must travel to that floor to distinguish between a solution of $n$ and $n-1$.
answered Aug 13 at 10:08
Phil H
9531513
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
add a comment |Â
up vote
1
down vote
accepted
Then there is no faster algorithm than just dropping an egg from each floor as you ascend; if you wanted to start from floor $x$, it would take $x$ minutes to reach that floor to begin, in which time you could have tested every floor up to $x$ anyway.
Thus: drop an egg from each floor. The worst case time would be $n$, which would always require at least $n$ minutes to find out simply because you must travel to that floor to distinguish between a solution of $n$ and $n-1$.
answered Aug 13 at 10:08
Phil H
9531513
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Then there is no faster algorithm than just dropping an egg from each floor as you ascend; if you wanted to start from floor $x$, it would take $x$ minutes to reach that floor to begin, in which time you could have tested every floor up to $x$ anyway.
Thus: drop an egg from each floor. The worst case time would be $n$, which would always require at least $n$ minutes to find out simply because you must travel to that floor to distinguish between a solution of $n$ and $n-1$.
answered Aug 13 at 10:08
Phil H
9531513
Then there is no faster algorithm than just dropping an egg from each floor as you ascend; if you wanted to start from floor $x$, it would take $x$ minutes to reach that floor to begin, in which time you could have tested every floor up to $x$ anyway.
Thus: drop an egg from each floor. The worst case time would be $n$, which would always require at least $n$ minutes to find out simply because you must travel to that floor to distinguish between a solution of $n$ and $n-1$.
answered Aug 13 at 10:08
Phil H
9531513
answered Aug 13 at 10:08
Phil H
9531513
answered Aug 13 at 10:08
Phil H
9531513
answered Aug 13 at 10:08
Phil H
9531513
9531513
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
add a comment |Â
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
Thanks. So this wasn't such a good question after all. I will try to craft another where one has to minimise some function of the amount of walking about inside the building and the number of eggs.
– ruffle
Aug 15 at 13:30
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
You could modify it to introduce some nonlinearity or to model the problem better. The original problem addresses the issue of finding which element of an array is the first to fail a predicate via the fewest evaluations of that predicate. The assumption is that values are cheap to access, and that the predicate is expensive to evaluate. Your question changed that to address the problem where the cost is linear in the traversal distance. An alternative (and gnarlier) version might be if evaluations were to be done in batches of $m$, and each batch had a constant cost; i.e. cache friendliness
– Phil H
Aug 16 at 9:09
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
Unfortunately I don't understand most of that. What if dropping an egg and learning whether or not it has broken takes time? Perhaps an increasing amount as time goes on? So 1 minute for the first egg, 2 for the second, etc.?
– ruffle
Aug 16 at 14:26
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2881206%2fthe-egg-drop-problem-where-the-aim-is-to-minimise-the-time-taken%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
