파우스트의 논리

63빌딩에 도착한 파우스트 박사는 빌딩 옆으로 흐르는 한강 물을 들여다보다가 문득 자살하고 싶은 충동을 느꼈다. "메피스토, 내가 이 빌딩에서 떨어지면 죽을까?" 그러자 메피스토펠레스가 대답했다. "글쎄요. 어느 특정한 층보다 높은 곳에서 떨어지면 죽지만 그보다 아래에서 떨어지면 죽지 않습니다."

"전부 몇 층이지?" 파우스트 박사가 물었다. "옥상까지 합해서 64층입니다."

"내가 몇 번 만에 그 층을 맞출 수 있을까?" 파우스트 박사가 말했다.

"재미있는 질문입니다. 그럼 이렇게 하지요. 박사님이 떨어져서 죽거든 제가 다시 살려드리겠습니다. 단, 죽음과 삶을 가르고 있는 층을 5번 내에 맞추십시오. 만약 맞추신다면 온 세상을 드리겠습니다. 하지만 맞추지 못하면 박사님의 영혼을 제게 주어야 합니다. 해 보시겠습니까?"

"딱 다섯 번만 떨어져 볼 수 있다는 말이지. 한 번 해볼까."

​

답을 확인하기 위해서 '임의의' 층이 문제의 층이라고 가정해보자. 예를 들어, 17층이 바로 문제의 층이라고 한다면 17층부터 그 위의 층에서는 떨어지면 죽게 되어 있고, 16층 아래로는 죽지 않도록 되어 있다. 64개의 층에서 루트에 해당하는 중앙은 64를 2로 나눈 32층이다. 여기에서부터 알고리즘을 시작해 본다.

1) 32층에서 떨어져 본다. 당연히 죽는다. (하지만, 메피스토펠레스가 다시 살려준다) 따라서 문제의 층은 32층보다 아래에 있다. 32를 다시 2로 나눈 값은 16이다.

2)16층에서 떨어져 본다.(답은 17층이므로) 죽지 않는다. 따라서 문제의 층은 16층보다 위에 있다. 32와 16 사이에 존재하는 중앙값은 24다.

3) 24층에서 떨어져 본다. 당연히 죽는다. (메피스토펠레스가 또 살려준다) 따라서 문제의 층은 24층보다 아래에 있다. 24층과 16층 사이에 존재하는 중앙은 20층이다.

4)20층에서 떨어져 본다. 또 죽는다. 따라서 문제의 층은 20층보다 아래에 있다. 20층과 16층 사이에 존재하는 중앙은 18층이다.

5)18층에서 떨어져 본다. 역시 죽는다. 따라서 문제의 층은 18층보다 아래에 있다.

​

옞덩의 논리 : 그런데 위의 가정을 전부 수용해서 순차적으로 진행한다고 해도 파우스트 박사의 승리가 보장된 것은 아니다. 이진트리로 좁혀갔으니 16층, 17층, 18층으로 후보가 좁혀졌다. 16층은 죽지 않았으니 답이 나왔고 18층은 죽었다. 문제는 17층부터 죽을 수도 있고, 18층부터 죽을 수도 있다는 점이다. 따라서 파우스트는 위의 5단계 시도만 가지고는 17층, 18층 중에서 찍는 수밖에 없다. (왜냐하면, 17층의 결과를 아직 파우스트가 모르기 때문이다. 죽지 않을 수도 있다.) Q.E.D.

​

ps 이 내용은 <누워서 읽는 알고리즘>에 나오는 논리적인 허점을 지적한 내용이다. 괴테의 파우스트와는 관련이 없다.