The Two Egg Problem (İki Yumurta Problemi)
The Two Egg Problem (İki Yumurta Problemi)
We are in an n-story building and we have two eggs. Eggs do not break when dropped from the xth floor of the building, but they break when thrown from the xth floor and above. As long as the egg does not break, it can be used repeatedly. What is the minimum number of throws needed to find out which floor the eggs start to break at?
Solution Methods
Solution Method 1
We start from the 1st floor and whichever floor it breaks on first, that is x.
In the best case, if it breaks on the first floor, it is found in a single throw; in the worst case, if it is on the highest floor, it is found in n-1 throws.
Solution Method 2
We throw the first egg from the middle floor; if it breaks, we throw the 2nd egg starting from the 1st floor upwards until it breaks.
If the egg does not break, it means it breaks on the floors between n/2 and n. We throw from the middle of these floors (3* n / 4) and continue in this way. (This logic is called Binary Search.)
The worst case of this method is if the egg breaks on the n/2-1 floor.
Ideal Solution Method
Although with the above methods we may have the chance to find the answer in very few moves, there may also be a possibility to find it after a very long process with many attempts. However, in a 100-story building, it is possible to find where the egg breaks in 14 moves (throws).
Let's explain how this is done.
Let's throw our egg from the 14th floor, we've used the first try. (13 moves left)
If it breaks, we try one by one from the 1st floor up to the 13th floor.
If it doesn't break, add 14 + 13 and throw our egg from the 27th floor. (12 moves left)
If it breaks, we try one by one from the 15th to the 26th floor.
If it doesn't break, add 14+13+12 and throw our egg from the 39th floor. (11 moves left)
If it breaks, we try one by one from the 28th to the 38th floor.
If it doesn't break, we keep making tests by following the number of moves.
14+13+12+11+...+4 = 99,
If it breaks, we try one by one from the 96th to the 98th floor.
If it does not break, since it did not break in the first 99 floors, when we drop it from the 100th floor, it will break.
If we need to show this mathematically with a formula
n: Number of floors in the building
q: Number of possible throws
q + (q-1) + (q-2) + (q-3) + ... + 1 >= norq*(q+1)/2 >= n
Yorum Gönder