You can't make an omelette...
Can you devise the most efficient strategy for finding the highest floor from which you can drop an egg safely?
Problem
This resource is part of "Freedom and Constraints"
Imagine you work for a factory that makes egg-shaped ornaments. On the packaging, you need to tell customers how high the eggs can be safely dropped from, without them breaking!
Image
The factory manager gives you an egg to test from each floor of a 100 storey building.
You will need to drop it from the first floor, and if it doesn't break, go up to the second floor, and if it doesn't break, go up to the third floor...
In the worst case scenario, you might have to do 100 tests to find out where it breaks!
"This could take ages! Can I have an extra egg to make life a bit easier?"
"Yes, here you are."
How will you use the extra egg so that you don't need to do so many trials?
Perhaps drop the first egg from the 5th floor and if it breaks, use the second egg to test floors 1 to 4.
And if it doesn't break...
Can you come up with a strategy using both eggs to minimise the number of trials you'd have to do in the worst case scenario?
What other interesting mathematical questions can you think of to explore next?
We have thought of some possibilities:
And if it doesn't break...
Can you come up with a strategy using both eggs to minimise the number of trials you'd have to do in the worst case scenario?
What other interesting mathematical questions can you think of to explore next?
We have thought of some possibilities:
Can you devise the most efficient strategy for finding the highest floor from which you can drop the egg safely?
What if there were more floors?
What if you had more eggs?
What if there were more floors?
What if you had more eggs?
We'd love you to share the questions you've come up with. Tell us also how you got started and any conclusions you have arrived at.
Send us your thoughts; we'll be publishing a selection.
Send us your thoughts; we'll be publishing a selection.
Student Solutions
Thank you to everybody who submitted solutions for this problem. Here's how some of you thought about the initial problem, with two eggs:
Phil, from Our Lady of Lourdes school in Canada, and Aryan from Dumpton School, England, expanded on the method described in the problem.
First, I would drop the egg from the $5^{th}$ storey. If it breaks then I will
know that the highest storey must be between $1-4$, and I would test each
floor, starting from $1$. If it does not break when I drop the egg from the $5^{th}$ storey then I would move on to the $10^{th}$. Using the same method as I did above, if it breaks then I would test floors $6$ through $9$. If it does not break then I would move to floor $15$. This will
continue, going through the building at $5$ floor increments while using the
same method as above until the highest floor that the egg will not break is
found.
Martha from Sha Tin College in Hong Kong,Eleanor from Honeywell School, UK, and Isabella from Beaconsfield High School thought about using this strategy as well. Martha conducted an experiment of her own to demonstrate the method:
I used the method above to conduct the experiment. Here are the results:
Egg $1$:
$5^{th}$ floor drop - doesn't break
$10^{th}$ floor drop - doesn't break
$15^{th}$ floor drop - doesn't break
$20^{th}$ floor drop - breaks
Egg $2$:
$16^{th}$ floor drop - breaks
According to the data, the egg broke when dropped from $16^{th}$ floor and
didn't break when dropped from $15^{th}$ floor. Therefore, the egg will break
when dropped from $16$ floors up.
Isabella also thought of an interesting question:
What if the eggs were different strengths and you didn't know which was which?
Daksh from St. Kabir school in India and Ellie Costin from Hardwich Middle School thought about using the same method, but went up in steps of $10$ floors rather than $5$.
Angela Ng from Harrow International School Hong Kong, Mr Ryan from Gordano School, England, and Luke Dodd-Atkins from Holmfirth High School all correctly realised that the lowest worst-case number of drops would be $14$. Here is Angela's solution, where she goes on to think about buildings with a different number of floors as well.
Suppose we start at the middle floor. If the egg breaks, we know that the solution is between $1-49$. As only one egg is left, we have to start from the first floor and go up step by step. Therefore, the worst case is that we need to have $50$ trials for it. It does not seem like a good method, as we need to try $50$ trials.
Using a jump of $10$ for each trial: if the first egg breaks at $10$, then the worst case scenario is performing $10$ trials (the first egg which breaks at $10$, and throwing the second egg from each of the floors $1-9$ before it breaks). If it does not break at $10$ but breaks at $20$, the worst case scenario is performing $11$ trials (two with the first egg, and each of the floors $11-19$ with the second). The overall worst-case scenario is $19$ tries, if the first egg breaks at $100$ and the second egg breaks at $99$.
Using a jump of $11$ for each trial: if the first egg breaks at $11$, then the worst-case scenario is performing $11$ trials. The worst case happens when the first egg breaks at floor $99$ and the second breaks at $98$, when we need $19$ trials.
Using a jump of $12$ for each trial: if the first egg breaks at $12$, we need to try $12$ trials. The worst case happens when the first egg breaks at floor $96$ and the second egg does not break until floor $95$, when we need $19$ trials.
The method to reduce the worst case is to try to make all possible cases take the same number of drops. Let the minimum number of drops be $n$.
If the first egg does not break at floor $n$, we then need to jump to another floor to try. As we need to let all cases take the same number of drops, i.e. n, then after the first trial at floor $n$ is used, there are $(n-1)$ trials left for the next drop, and hence the next level we should try if the first egg does not break at floor $n$ is $n + (n-1)$. Continuing this sequence, if it does not break at this level, then the next trial for the first egg will be on floor $n + (n-1) + (n-2)$. When the first egg breaks, we use the second egg to test all the floors in between the floor the first egg broke on and the last floor we tested with the first egg, going upwards. Using this method, it will never take more than $n$ trials.
So we need to find the smallest $n$ such that $n+(n-1)+(n-2)+...\geq 100$. This is $14$, so we need never use more than $14$ trials.
To adapt it for a different number of buildings, the value of $n$ can change.
For example, for a $200$-storey building:
$n+(n-1)+(n-2)+...+1 \geq 200$
Answer = $20$
A $300$-storey building:
$n+(n-1)+(n-2)+...+1\geq 300$
Answer = $24$
Well done!
Lots of you thought about different ways of solving this problem if you had more than two eggs. Here is Marcus from Beechwood Park School's solution.
The obvious solution to this would be to use more eggs as it says in the
hidden texts. With a large number, such as $100$, it is always good to work in
halves. So firstly, drop one egg off the $50^{th}$ floor and see if it breaks.
If it does then go lower. If it doesn't then go higher. Now at this point,
with only one egg left, the halving method would not work and it would have
to be a lucky guess. However, with more eggs, if the egg breaks on the 50th
go to the $25^{th}$ floor. If it doesn't, go to the $75^{th}$ floor. As we halve
these numbers we are halving the number of possible solutions to this problem. Continue the halving strategy and
it won't be long until you have found the answer.
Thank you to everybody who submitted solutions to this problem!
Phil, from Our Lady of Lourdes school in Canada, and Aryan from Dumpton School, England, expanded on the method described in the problem.
First, I would drop the egg from the $5^{th}$ storey. If it breaks then I will
know that the highest storey must be between $1-4$, and I would test each
floor, starting from $1$. If it does not break when I drop the egg from the $5^{th}$ storey then I would move on to the $10^{th}$. Using the same method as I did above, if it breaks then I would test floors $6$ through $9$. If it does not break then I would move to floor $15$. This will
continue, going through the building at $5$ floor increments while using the
same method as above until the highest floor that the egg will not break is
found.
Martha from Sha Tin College in Hong Kong,Eleanor from Honeywell School, UK, and Isabella from Beaconsfield High School thought about using this strategy as well. Martha conducted an experiment of her own to demonstrate the method:
I used the method above to conduct the experiment. Here are the results:
Egg $1$:
$5^{th}$ floor drop - doesn't break
$10^{th}$ floor drop - doesn't break
$15^{th}$ floor drop - doesn't break
$20^{th}$ floor drop - breaks
Egg $2$:
$16^{th}$ floor drop - breaks
According to the data, the egg broke when dropped from $16^{th}$ floor and
didn't break when dropped from $15^{th}$ floor. Therefore, the egg will break
when dropped from $16$ floors up.
Isabella also thought of an interesting question:
What if the eggs were different strengths and you didn't know which was which?
Daksh from St. Kabir school in India and Ellie Costin from Hardwich Middle School thought about using the same method, but went up in steps of $10$ floors rather than $5$.
Angela Ng from Harrow International School Hong Kong, Mr Ryan from Gordano School, England, and Luke Dodd-Atkins from Holmfirth High School all correctly realised that the lowest worst-case number of drops would be $14$. Here is Angela's solution, where she goes on to think about buildings with a different number of floors as well.
Suppose we start at the middle floor. If the egg breaks, we know that the solution is between $1-49$. As only one egg is left, we have to start from the first floor and go up step by step. Therefore, the worst case is that we need to have $50$ trials for it. It does not seem like a good method, as we need to try $50$ trials.
Using a jump of $10$ for each trial: if the first egg breaks at $10$, then the worst case scenario is performing $10$ trials (the first egg which breaks at $10$, and throwing the second egg from each of the floors $1-9$ before it breaks). If it does not break at $10$ but breaks at $20$, the worst case scenario is performing $11$ trials (two with the first egg, and each of the floors $11-19$ with the second). The overall worst-case scenario is $19$ tries, if the first egg breaks at $100$ and the second egg breaks at $99$.
Using a jump of $11$ for each trial: if the first egg breaks at $11$, then the worst-case scenario is performing $11$ trials. The worst case happens when the first egg breaks at floor $99$ and the second breaks at $98$, when we need $19$ trials.
Using a jump of $12$ for each trial: if the first egg breaks at $12$, we need to try $12$ trials. The worst case happens when the first egg breaks at floor $96$ and the second egg does not break until floor $95$, when we need $19$ trials.
The method to reduce the worst case is to try to make all possible cases take the same number of drops. Let the minimum number of drops be $n$.
If the first egg does not break at floor $n$, we then need to jump to another floor to try. As we need to let all cases take the same number of drops, i.e. n, then after the first trial at floor $n$ is used, there are $(n-1)$ trials left for the next drop, and hence the next level we should try if the first egg does not break at floor $n$ is $n + (n-1)$. Continuing this sequence, if it does not break at this level, then the next trial for the first egg will be on floor $n + (n-1) + (n-2)$. When the first egg breaks, we use the second egg to test all the floors in between the floor the first egg broke on and the last floor we tested with the first egg, going upwards. Using this method, it will never take more than $n$ trials.
So we need to find the smallest $n$ such that $n+(n-1)+(n-2)+...\geq 100$. This is $14$, so we need never use more than $14$ trials.
To adapt it for a different number of buildings, the value of $n$ can change.
For example, for a $200$-storey building:
$n+(n-1)+(n-2)+...+1 \geq 200$
Answer = $20$
A $300$-storey building:
$n+(n-1)+(n-2)+...+1\geq 300$
Answer = $24$
Well done!
Lots of you thought about different ways of solving this problem if you had more than two eggs. Here is Marcus from Beechwood Park School's solution.
The obvious solution to this would be to use more eggs as it says in the
hidden texts. With a large number, such as $100$, it is always good to work in
halves. So firstly, drop one egg off the $50^{th}$ floor and see if it breaks.
If it does then go lower. If it doesn't then go higher. Now at this point,
with only one egg left, the halving method would not work and it would have
to be a lucky guess. However, with more eggs, if the egg breaks on the 50th
go to the $25^{th}$ floor. If it doesn't, go to the $75^{th}$ floor. As we halve
these numbers we are halving the number of possible solutions to this problem. Continue the halving strategy and
it won't be long until you have found the answer.
Thank you to everybody who submitted solutions to this problem!