The following is a description of the instance of this famous puzzle involving n=2 eggs and a building with k=36 floors.Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions:…..An egg that survives a fall can be used again.…..A broken egg must be discarded.…..The effect of a fall is the same for all eggs.…..If an egg breaks when dropped, then it would break if dropped from a higher floor.…..If an egg survives a fall then it would survive a shorter fall.…..It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor does not cause an egg to break.If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings that are guaranteed to work in all cases?The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.INPUT:k, Number of floorsn, Number of EggsOUTPUT:The minimum number of trials.
Question
The following is a description of the instance of this famous puzzle involving n=2 eggs and a building with k=36 floors.Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions:…..An egg that survives a fall can be used again.…..A broken egg must be discarded.…..The effect of a fall is the same for all eggs.…..If an egg breaks when dropped, then it would break if dropped from a higher floor.…..If an egg survives a fall then it would survive a shorter fall.…..It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor does not cause an egg to break.If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings that are guaranteed to work in all cases?The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.INPUT:k, Number of floorsn, Number of EggsOUTPUT:The minimum number of trials.
Solution
The problem you're describing is a classic example of a dynamic programming problem. The solution involves finding the minimum number of trials in the worst case for n eggs and k floors.
Here's a step-by-step solution:
-
We first create a table eggFloor of size n x k where entry eggFloor[i][j] will represent the minimum number of trials needed for i eggs and j floors.
-
We initialize the first row (one egg) with sequential numbers, because with one egg we have to try dropping it from every floor one by one.
-
For the rest of the cells, we use the following formula to fill them: eggFloor[i][j] = 1 + min{max(eggFloor[i-1][x-1], eggFloor[i][j-x]): x in range(1, j+1)}
This formula is based on the idea that we drop an egg from the xth floor. If it breaks, we only have i-1 eggs left and we need to check the floors below x, which is eggFloor[i-1][x-1]. If it doesn't break, we still have i eggs and we need to check the floors above x, which is eggFloor[i][j-x]. We want to minimize the number of trials, so we take the minimum of these two scenarios. However, we also want to prepare for the worst case, so within the min function, we take the maximum of the two scenarios.
-
We continue this process until we've filled up the entire table.
-
The value eggFloor[n][k] will be our result, representing the minimum number of trials in the worst case for n eggs and k floors.
For the given problem where n=2 eggs and k=36 floors, the minimum number of trials in the worst case is 8.
Similar Questions
An egg in a special container together have a mass of 148.0 g. The container is designed such that when dropped it will bring the egg to a stop in 0.200 s when it hits the ground. A force of 4.91 N will break the egg. What is the maximum height from which the egg in its container can be dropped and not break the egg?
A moderate force will break an egg. However, an egg dropped on the road usually breaks, while one dropped on the grass usually doesn’t break. This is because the egg dropped on the grass _______.*1 pointthe time interval for stopping is lessthe change in momentum is greaterthe time interval for stopping is greaterthe change in momentum is less
A chicken's egg of mass 58 g is dropped onto grass from a height of 1.1 m. Assume that air resistance is negligible and that the egg does not bounce orbreak.a. Define impulse.[1]b.i. Show that the kinetic energy of the egg just before impact is about 0.6 J.[1]b.ii.The egg comes to rest in a time of 55 ms. Determine the magnitude of the average decelerating force that the ground exerts on the egg.[4]b.ii Explain why the egg is likely to break when dropped onto concrete from the same height.
Select each correct answer. More than one answer may be correct.Marcy and her classmates are designing devices to keep eggs from breaking when the eggs are dropped on the floor. Which of the following factors could play a role in the effectiveness of their final egg-protecting devices? opportunity to test the design availability and properties of construction materials time limits on design and production
Greenville has a town-wide hunt for plastic dinosaur eggs every spring. Tanner and his sister, Tess, participate every year. Tanner found 25 eggs this year, but Tess found more.Let e represent the number of eggs that Tess could have found. Which inequality models the story?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.