계란 낙하

 

특수 제조한 계란이 2개 있는데, 100층 높이 빌딩의 몇 층에서 떨어뜨려야 깨지는지 알아내려 합니다.
단 2개의 계란만 사용해서 몇 층에서 깨지는지 확실하게 알아내려면 계란을 최소 몇 번 떨어뜨려 봐야 할까요?

답은 14번입니다.
1층부터 차례로 계란을 떨어뜨려 보면 몇 층에서 깨지는지 확실히 알 수 있지만, 100층까지 최대 100번을 던져봐야 합니다.
50층에서 실험한 뒤 깨지면 1층부터, 안 깨지면 51층부터 실험하면 실험 횟수를 절반으로 줄일 수 있죠.
같은 식으로 최초에 시작하는 층을 계산해 보면 14층이 가장 효율적입니다.
14층에서 깨지면 1층부터 실험합니다(최대 14회 실험). 안 깨지면 13층 위인 27층에서 다시 실험합니다.
깨지면 15층부터 26층까지 던져보고(이 경우도 최대 14회 실험), 안 깨지면 12층 위인 39층에서 실험을 반복합니다.
계속 같은 실험을 50 · 60 · 69 · 77 · 80 · 86 · 91 · 95 · 98층에서 차례로 실시합니다.
98층에서 안 깨지면 99 · 100층에서 최종 투척 실험을 합니다.
이 모든 경우 최대 실험 횟수는 14번입니다.
이것이 계란이 몇 층에서 깨지는지를 아는 가장 효율적인 방법입니다.