Egg drop problem - minimize AVERAGE case
In the egg drop problem, you have two eggs and you want to determine from which floors in a $n$ - floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
Some assumptions :
- If the egg doesn't break at a certain floor, it will not break at any
floor below. - If the eggs breaks at a certain floor, it will break at any floor
above. - The egg may break at the first floor.
- The egg may not break at the last floor.
This problem is popular and there are many ways to solve it. I am wondering how to solve it with the following twist : instead of minimizing the worst case, how would one minimize the average case ? We consider that the egg has equal probability $1/n$ to break on a given floor (and above).
An attempt :
Let $f(2,n)$ denote the minimum number of drops needed to cover $n$ floors with the $2$ eggs.
For the worst case, the following recursive equation holds
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ max{f(1,x-1),f(2,n-x } bigr }
$$
Roughly speaking, when throwing the first egg from a given floor $x$, there are two scenarios :
- If the egg breaks, we are left with $1$ egg and have to check the $x-1$ floors below
- If the egg does not break, the $n-x$ floors above $x$ have to be checked with the $2$ eggs
Since the number of trials in worst case is minimized, we take the maximum of these two cases for every floor and choose the floor which yields minimum number of drops. The extra $1$ accounts for the drop before knowing if the egg broke or not. The base cases are trivially $f(1,0)=f(2,0)=0$ (no drops needed if there are no floors), $f(1,1)= f(2,1) = 1$ (one drop is sufficient if there is only one floor), and $f(1,x) = x$ ($x$ drops needed if only one egg is available - each floor must be tested one by one).
For the average case, I believe the recursive equation becomes
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ p(x)f(1,x-1)+(1-p(x))f(2,n-x) bigr },
$$
where $p(x)$ is the probability that the egg breaks on floor $x$, i.e., the probability that $x$ is above the critical floor. If this critical floor is represented by a discrete random variable $Y$ with uniform distribution on $[1,n]$ :
$$
p(x) = P(xge Y)
$$
I am not sure if this correct. And if so, how can this expression be simplified?
Also, the base cases remain $f(1,0)=f(2,0)=0$, $f(1,1)=f(2,1)=1$, but $f(1,x)$ no longer equals $x$, since we are interested in the average case.
Any help is welcome, any other approach is welcome. Thanks.
probability optimization recreational-mathematics puzzle
asked yesterday
Kuifje
7,1082725
add a comment |
In the egg drop problem, you have two eggs and you want to determine from which floors in a $n$ - floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
Some assumptions :
- If the egg doesn't break at a certain floor, it will not break at any
floor below. - If the eggs breaks at a certain floor, it will break at any floor
above. - The egg may break at the first floor.
- The egg may not break at the last floor.
This problem is popular and there are many ways to solve it. I am wondering how to solve it with the following twist : instead of minimizing the worst case, how would one minimize the average case ? We consider that the egg has equal probability $1/n$ to break on a given floor (and above).
An attempt :
Let $f(2,n)$ denote the minimum number of drops needed to cover $n$ floors with the $2$ eggs.
For the worst case, the following recursive equation holds
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ max{f(1,x-1),f(2,n-x } bigr }
$$
Roughly speaking, when throwing the first egg from a given floor $x$, there are two scenarios :
- If the egg breaks, we are left with $1$ egg and have to check the $x-1$ floors below
- If the egg does not break, the $n-x$ floors above $x$ have to be checked with the $2$ eggs
Since the number of trials in worst case is minimized, we take the maximum of these two cases for every floor and choose the floor which yields minimum number of drops. The extra $1$ accounts for the drop before knowing if the egg broke or not. The base cases are trivially $f(1,0)=f(2,0)=0$ (no drops needed if there are no floors), $f(1,1)= f(2,1) = 1$ (one drop is sufficient if there is only one floor), and $f(1,x) = x$ ($x$ drops needed if only one egg is available - each floor must be tested one by one).
For the average case, I believe the recursive equation becomes
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ p(x)f(1,x-1)+(1-p(x))f(2,n-x) bigr },
$$
where $p(x)$ is the probability that the egg breaks on floor $x$, i.e., the probability that $x$ is above the critical floor. If this critical floor is represented by a discrete random variable $Y$ with uniform distribution on $[1,n]$ :
$$
p(x) = P(xge Y)
$$
I am not sure if this correct. And if so, how can this expression be simplified?
Also, the base cases remain $f(1,0)=f(2,0)=0$, $f(1,1)=f(2,1)=1$, but $f(1,x)$ no longer equals $x$, since we are interested in the average case.
Any help is welcome, any other approach is welcome. Thanks.
probability optimization recreational-mathematics puzzle
asked yesterday
Kuifje
7,1082725
Perhaps you've already this, but I would recommend working out explicit values of your function for the first several values of $n$, to see, for one thing, if they make sense.
– Barry Cipra
yesterday
add a comment |
In the egg drop problem, you have two eggs and you want to determine from which floors in a $n$ - floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
Some assumptions :
- If the egg doesn't break at a certain floor, it will not break at any
floor below. - If the eggs breaks at a certain floor, it will break at any floor
above. - The egg may break at the first floor.
- The egg may not break at the last floor.
This problem is popular and there are many ways to solve it. I am wondering how to solve it with the following twist : instead of minimizing the worst case, how would one minimize the average case ? We consider that the egg has equal probability $1/n$ to break on a given floor (and above).
An attempt :
Let $f(2,n)$ denote the minimum number of drops needed to cover $n$ floors with the $2$ eggs.
For the worst case, the following recursive equation holds
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ max{f(1,x-1),f(2,n-x } bigr }
$$
Roughly speaking, when throwing the first egg from a given floor $x$, there are two scenarios :
- If the egg breaks, we are left with $1$ egg and have to check the $x-1$ floors below
- If the egg does not break, the $n-x$ floors above $x$ have to be checked with the $2$ eggs
Since the number of trials in worst case is minimized, we take the maximum of these two cases for every floor and choose the floor which yields minimum number of drops. The extra $1$ accounts for the drop before knowing if the egg broke or not. The base cases are trivially $f(1,0)=f(2,0)=0$ (no drops needed if there are no floors), $f(1,1)= f(2,1) = 1$ (one drop is sufficient if there is only one floor), and $f(1,x) = x$ ($x$ drops needed if only one egg is available - each floor must be tested one by one).
For the average case, I believe the recursive equation becomes
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ p(x)f(1,x-1)+(1-p(x))f(2,n-x) bigr },
$$
where $p(x)$ is the probability that the egg breaks on floor $x$, i.e., the probability that $x$ is above the critical floor. If this critical floor is represented by a discrete random variable $Y$ with uniform distribution on $[1,n]$ :
$$
p(x) = P(xge Y)
$$
I am not sure if this correct. And if so, how can this expression be simplified?
Also, the base cases remain $f(1,0)=f(2,0)=0$, $f(1,1)=f(2,1)=1$, but $f(1,x)$ no longer equals $x$, since we are interested in the average case.
Any help is welcome, any other approach is welcome. Thanks.
probability optimization recreational-mathematics puzzle
asked yesterday
Kuifje
7,1082725
In the egg drop problem, you have two eggs and you want to determine from which floors in a $n$ - floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
Some assumptions :
- If the egg doesn't break at a certain floor, it will not break at any
floor below. - If the eggs breaks at a certain floor, it will break at any floor
above. - The egg may break at the first floor.
- The egg may not break at the last floor.
This problem is popular and there are many ways to solve it. I am wondering how to solve it with the following twist : instead of minimizing the worst case, how would one minimize the average case ? We consider that the egg has equal probability $1/n$ to break on a given floor (and above).
An attempt :
Let $f(2,n)$ denote the minimum number of drops needed to cover $n$ floors with the $2$ eggs.
For the worst case, the following recursive equation holds
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ max{f(1,x-1),f(2,n-x } bigr }
$$
Roughly speaking, when throwing the first egg from a given floor $x$, there are two scenarios :
- If the egg breaks, we are left with $1$ egg and have to check the $x-1$ floors below
- If the egg does not break, the $n-x$ floors above $x$ have to be checked with the $2$ eggs
Since the number of trials in worst case is minimized, we take the maximum of these two cases for every floor and choose the floor which yields minimum number of drops. The extra $1$ accounts for the drop before knowing if the egg broke or not. The base cases are trivially $f(1,0)=f(2,0)=0$ (no drops needed if there are no floors), $f(1,1)= f(2,1) = 1$ (one drop is sufficient if there is only one floor), and $f(1,x) = x$ ($x$ drops needed if only one egg is available - each floor must be tested one by one).
For the average case, I believe the recursive equation becomes
$$
f(2,n) = 1 + min_{1 le x le n} bigl{ p(x)f(1,x-1)+(1-p(x))f(2,n-x) bigr },
$$
where $p(x)$ is the probability that the egg breaks on floor $x$, i.e., the probability that $x$ is above the critical floor. If this critical floor is represented by a discrete random variable $Y$ with uniform distribution on $[1,n]$ :
$$
p(x) = P(xge Y)
$$
I am not sure if this correct. And if so, how can this expression be simplified?
Also, the base cases remain $f(1,0)=f(2,0)=0$, $f(1,1)=f(2,1)=1$, but $f(1,x)$ no longer equals $x$, since we are interested in the average case.
Any help is welcome, any other approach is welcome. Thanks.
probability optimization recreational-mathematics puzzle
probability optimization recreational-mathematics puzzle
asked yesterday
Kuifje
7,1082725
asked yesterday
Kuifje
7,1082725
asked yesterday
Kuifje
7,1082725
asked yesterday
Kuifje
7,1082725
asked yesterday
Kuifje
7,1082725
7,1082725
Perhaps you've already this, but I would recommend working out explicit values of your function for the first several values of $n$, to see, for one thing, if they make sense.
– Barry Cipra
yesterday
add a comment |
Perhaps you've already this, but I would recommend working out explicit values of your function for the first several values of $n$, to see, for one thing, if they make sense.
– Barry Cipra
yesterday
Perhaps you've already this, but I would recommend working out explicit values of your function for the first several values of $n$, to see, for one thing, if they make sense.
– Barry Cipra
yesterday
Perhaps you've already this, but I would recommend working out explicit values of your function for the first several values of $n$, to see, for one thing, if they make sense.
– Barry Cipra
yesterday
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060542%2fegg-drop-problem-minimize-average-case%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060542%2fegg-drop-problem-minimize-average-case%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Perhaps you've already this, but I would recommend working out explicit values of your function for the first several values of $n$, to see, for one thing, if they make sense.
– Barry Cipra
yesterday