네 말을 듣고 나니 답을 알겠어

올리버 “내가 방금 이며 인 두 정수 를 잡았어. 샘에게는 합을, 피터에게는 곱을 알려줄테니 맞춰봐.”

샘 “피터는 답을 모를거야.”

피터 “네 말을 듣고나니 답을 알겠어.”

샘 “나도 이제 답을 알겠어.”

이 때 의 값은 무엇인가? 단, 샘과 피터는 논리적으로 완벽하게 논증해낸 결과들만을 이야기했다.

논리학자들이 나와 대화를 하면서 “네 말을 듣고 알았다”란 식의 정보를 주고 받는 유형의 문제들의 시초가 되는 문제. (실제 논리학자들이 다루는 학문은 이런게 아니지만) 1969년 Hans Freudenthal이 네덜란드 수학 저널 Nieuw Archief voor Wiskunde에 낸 퍼즐로, 1979년 마틴 가드너가 “The impossible problem”이란 이름으로 소개해서 유명해졌다. 굉장히 적은 정보가 주어진 것 같지만 위 대화를 토대로 반드시 두 수를 구할 수 있다는 것이 포인트.

편의상 두 수의 합을 , 곱을 라 한다. 먼저, 피터가 곱만으로 의 값을 알 수 없다는 사실을 주목한다. 이는 를 2 이상의 서로 다른 자연수의 곱으로 표현하는 방법이 유일하지 않음을 뜻한다. 즉 는

• 서로 다른 두 소수의 곱 꼴도 아니어야 하고
• 한 소수의 세제곱 꼴도 아니어야 함

을 뜻한다. 편의상 이런 수를 ‘애매모호한’ 수라고 부르도록 한다.

샘은 피터가 답을 모른다고 했으므로, 로 나타냈을 때 () 가 전부 애매모호함을 뜻합니다. (예를 들면 11의 경우 2*9=18, 3*8=24, 4*7=28, 5*6=30 전부 애매모호하다) 이런 경우 샘은 아직 두 수 가 몇인지는 모르지만 반드시 곱이 애매모호하기 때문에 피터가 곱만으로 답을 얻어낼 수 없다는 결론을 도출할 수 있게 된다. 이런 조건을 만족하는 는 100 이하에서 11,17,23,27,29,35,37,41,47,53임을 계산을 통해 확인할 수 있다.

이제 피터는 샘의 방금 전의 말을 듣고, 앞에서와 같은 논리를 똑같이 거친 후 가 위 리스트 중에 있다는 사실을 알게 된다. 피터는 이미 알고 있는 의 값과 방금 샘의 말을 듣고 알아낸 의 후보들을 이용해 를 구하는데 성공한다. 이는 즉 올바른 답을 이끌어낼 수 있는 가 유일함을 뜻한다. 예컨대, 그가 가진 의 값이 30이었다면 위 리스트 안에 있는 의 값으로 도 가능하고() 도 가능해서() 피터는 답을 확정할 수 없게 된다. 따라서 의 후보들로 얻을 수 있는 모든의 후보들 중에서 는 다른데 가 같은 경우들을 전부다 배제할 수 있다. (앞의 예는 (5,6)과 (2,15)를 둘 다 배제할 수 있음을 뜻한다) 이 과정을 거쳐 남은 후보 쌍들은 다음과 같다.

마지막 샘의 턴. 샘은 피터의 말을 듣고 역시 똑같은 논리에 의해 위와 같은 후보 쌍의 표를 얻게 된다. 그리고 답을 알았다고 하는데, 이는 그가 이미 알고 있는 의 값과 위의 표를 이용해서 유일한 결과를 얻어내었음을 의미한다. 즉 이 표에서 를 고정했을 때 경우의 수가 1개여야 하며, 그런 경우는 (4,13)일 때밖에 없다. 따라서 주어진 두 수는 4와 13.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/09/25)

39. 올리버 "내가 방금 2≤x＜y이며 x+y≤100인 두 정수 x,y를 잡았어. 샘에게는 합을, 피터에게는 곱을 알려줄테니 맞춰봐."
샘 "피터는 답을 모를거야."
피터 "네 말을 듣고나니 답을 알겠어."
샘 "나도 이제 답을 알겠어."

— Elegant Math (@elegant_math) September 25, 2017