우리 마을 미친 개…어떻게 찾을 수 있을까?

창의적 문제 해결 연습

문제 우리 마을의 모든 집은 개를 한 마리씩 키운다. 어느날 마을 이장이 다음과 같이 방송하였다. “우리 마을에 미친 개가 있다는 정보가 들어왔습니다. 각 가정에서는 자신의 개가 미쳤다는 것을 알게 되면 그날 밤 자정에 총으로 쏴죽이십시오.” 그런데, 사람들은 자신의 개에 대한 감정 때문인지 자신의 개가 미쳤는지 미치지 않았는지 직접 판단을 할 수는 없고, 오로지 다른 집의 개가 미쳤는지의 여부만 알 수 있다. 하지만, 다른 집의 주민들과의 관계 때문에 미친 개를 보아도 그 집에 사는 사람들에게 당신네 집의 개가 미쳤다고 알려주지는 못한다. 다시 말하면 개가 미쳤는지의 여부에 대한 직접적인 정보 교류는 있을 수 없다. 마을 사람들은 고민에 빠졌으나 다들 똑똑한 사람들이라 금새 방법을 찾은 모양이다. 과연 이 방법은 무엇인지, 몇째 날 밤 자정에 총소리가 날지 생각해보자.

■ 첫 번째 생각

이장의 말에 의해 미친개는 한 마리 이상 존재한다. 다만 몇 마리인지 모른다. 주민들이 할 수 있는 것은 다른 모든 집의 개의 상태를 파악하는 것과 생각하는 것 뿐이다.

■ 두 번째 생각

왜 총으로 쏴죽이라고 했을까? 칼로 죽일 수도 있고, 다른 방법으로 죽일 수도 있는데 굳이 총으로 쏴죽이라고 한 이유는 뭘까? 총으로 쏘면 다른 집에서 총소리에 의해 어떤 미친 개가 죽었다는 것을 알 수 있다. 하지만 조용히 죽이면 다른 집에서 이런 사실들을 알 수가 없다. 즉, 이 상황에서 총으로 쏴죽이는 것의 의미는 소음으로 인해 다른 집에 미친 개를 죽인 것을 알린다는 것이다. 다시 말하면 이것이 곧 정보교류의 방법이 된다.

■ 세 번째 생각

이제 생각이 막혔다. 위의 생각들로 어떻게 미친개를 찾아낼 것인가? 머리가 복잡하다면 다음의 방법이 유용할 것이다.

미친 개가 한 마리였다면 어땠을까?

미친 개가 두 마리였다면 어땠을까?

미친 개가 세 마리였다면 어땠을까?

등의 가정을 통해 생각을 진행시켜본다.

사실 가장 중요한 부분이 바로 세 번째 생각이다. 세 번째 생각을 해냈다면 방법과 며칠 뒤에 총소리가 날지 등에 대해 알아낼 수 있다.

미친 개가 한 마리였다고 해보자.

미친 개의 주인은 자신의 개가 미친 것을 모르고 미친 개가 한 마리 이상이라는 것을 안다. 이 사람이 마을의 모든 개를 확인하면 자신의 눈에는 미친 개가 없다. 따라서 이 미친 개의 주인은 자신의 개가 미쳤다는 것을 알 수 있다. 그러면 첫째 날 밤에 총소리가 날 것이다.

미친 개가 두 마리였다고 해보자.

미친 개의 주인은 두 명이다. 이들의 눈에는 미친 개가 한 마리만 보일 것이다. 그러면 첫째 날 자신의 개가 미쳤다고 생각하지 않을 것이다. 따라서, 첫째 날 밤에는 총소리가 나지 않을 것이다. 하지만 첫째 날 밤 자정에 총소리가 나지 않으면 미친 개가 한 마리가 아니라는 것이다.(미친 개가 한 마리라면 위의 사실에서 총소리가 나야만 한다.) 따라서, 미친 개는 두 마리 이상이고, 미친 개의 주인은 동네에서 미친 개를 한 마리만 발견하였으므로 자신의 개가 미쳤다는 것을 알 수 있다. 따라서, 둘째 날 미친 개의 주인은 자신의 개가 미쳤다는 것을 알게 되고 그 날 밤 자정에 총소리가 날 것이다.

미친 개가 세 마리였다고 해보자.

미친 개의 주인은 세 명이다. 이들의 눈에는 미친 개가 두 마리만 보일 것이다. 그러면 첫째 날 자신의 개가 미쳤다는 것을 모른다. 따라서, 첫째 날 밤에는 총소리가 나지 않는다. 둘째 날이 되면, 위의 생각을 통해 미친 개가 두 마리 이상이라는 것을 안다. 여전히 미친 개의 주인은 자신의 개가 미쳤다고 생각하지 않는다. 둘째 날 밤도 총소리가 나지 않을 것이다. 하지만 이 때까지 총소리가 나지 않으면 미친 개는 두 마리가 아니라는 것이다. 즉 미친 개는 세 마리 이상이고, 미친 개의 주인은 자신의 눈에 미친 개를 두 마리만 발견하였으므로 자신의 개가 미쳤다는 것을 알게 된다. 따라서, 셋째 날 밤 자정에 총소리가 날 것이다.

이제 이를 정리하면,

마을 사람들이 자신의 개가 미쳤는지 알아내는 방법은 다음과 같다.

자신이 본 미친 개를 마리라 할 때, 번째 날 밤 자정까지 총소리가 나지 않으면 자신의 개가 미친 것이다.

몇째 날 밤 자정에 총소리가 날 지 알아내는 방법은 다음과 같다.

미친 개가 마리라면 번째 날 밤 자정에 총소리가 난다.

■ 위 문제를 참고해 아래 게임을 해보자

클래스온 수석연구원 박동훈

A가 1, 2, 3, 4 중에서 한 개의 숫자를 선택해서 마음 속으로 기억한다.

B는 A에게 “네가 선택한 숫자가 1, 2, 3 중에 있느냐?” 이런 방법으로 질문을 하고 A는 이에 대해 ○, ×로 대답을 하는데, 한 번까지는 거짓으로 대답할 수 있다. 그렇다면 B가 그 숫자를 알아내기 위해서 어떤 방식을 취할 것인지, 그리고 적어도 몇 번 질문을 해야 하는지 생각해보시오.

클래스온 수석연구원 박동훈

※ 매주 수요일 오후 6시40분에 클래스온 홈페이지(www.class-on.com)에서는 문제의 출제자가 직접 풀이과정을 실시간 동영상으로 해설한다. 동영상 강의는 쌍방향으로 이뤄지기 때문에 이 시간대에 접속하면 문제와 관련한 질문을 직접 할 수 있다. 또 클래스온 홈페이지에 답안을 올리면 매주 한 명을 선정해 클래스온 강의를 무료로 제공한다.

---

■ 창의력 문제풀이 답안

■ 첫 번째 생각

A의 대답이 거짓인지 아닌지 구분할 수 있는가?

똑같은 질문을 두 번 해보면 알 수 있겠다. 똑같은 질문에 대한 대답이 일치하면 거짓말을 최대 한 번까지만 할 수 있다는 조건에 의해 이 대답은 둘 다 거짓일 수 없으므로 둘 다 진실이다. 만약 똑같은 질문에 대한 대답이 불일치하면 둘 중 하나는 거짓이므로 한 번 거짓 답변을 하였으므로 이후에는 진실로만 대답하게 된다.

적어도 몇 번 질문을 해야 하는지 알아야 하므로 최악의 상황에도 알아낼 수 있는 최소의 질문 수를 구해야 한다.

그러면 다음과 같이 질문을 해보자.

“1, 2 중에 있는가?”를 두 번 질문해 얻은 결론이 모두 ○라면 1, 2 중에 있다.

이제, “1인가?”를 두 번 질문해 얻는 결론이 서로 다르다면 한 번 더 질문을 해야 한다. 그러면, A가 생각한 숫자를 알 수 있고, 이 때가 바로 최악의 상황임을 알 수 있다. 즉, 적어도 5번 질문을 하면 생각한 숫자를 알아낼 수 있다.

■ 두 번째 생각

위의 상황에서 보다 더 적은 질문 수로 생각한 숫자를 알아낼 방법이 있지 않을까?

다음과 같이 생각해보자.

현재의 상황은 1, 2, 3, 4 중 생각한 숫자가 있고, 질문을 n번 할 경우 거짓말을 안하거나 1, 2, 3, …, n번째 거짓말을 할 수 있다. 그러면 이는 전체 가능한 경우가 4(n+1)(가지)이고 이를 판별해 내려면 대답할 수 있는 가짓수가 4(n+1)가지 이상이어야 한다. 질문을 한 번 하면 답의 종류는 ○ 또는 ×로 두 가지이고, 질문을 두 번 하면 답의 종류는 (○, ○), (○, ×), (×, ○), (×, ×)로 네 가지이고, 이런 방법으로 질문을 n번 하면 답의 종류는 2ⁿ(가지)이다. 즉, 4(n+1)***(등호와 부등호 같이 쓰인 것) 2ⁿ이어야 한다. 이 때, n=4이면, 4×5***2⁴은 성립하지 않는다. n=5이면, 4×6*** (2의5제곱***이것도 집배신에서 찾지 못했음)은 성립한다. 따라서, 질문은 다섯 번 이상이어야 한다. 실제로 다섯 번에 가능토록 질문을 적당히 구성해보자.

첫 번째 질문 - 1, 2 중에 있는가?

두 번째 질문 - 1, 3 중에 있는가?

세 번째 질문 - 2, 3 중에 있는가?

네 번째 질문 - 2, 4 중에 있는가?

다섯 번째 질문 - 1, 4 중에 있는가?

이제, 다음 표에서 답변의 세트를 보자.

생각한 숫자가 1인 경우 <표1참조>

생각한 숫자가 2인 경우 <표2참조>

생각한 숫자가 3인 경우 <표3참조>

생각한 숫자가 4인 경우 <표4참조>

세로 방향 다섯 개의 답변을 하나의 세트로 할 때, 일치하는 부분이 한 쌍도 없으므로 판단이 가능하다. 예를 들어 생각한 숫자가 2이고, 세 번째 거짓말을 했다면 답변은 (○××○×)일 것이고, 실제로 위의 답변 세트에서 이와 동일한 세트는 어두운 부분으로 유일하다.

따라서, 최소 다섯 번이면 가능함을 알 수 있다.

부가적으로, 네 번 질문으로 불가능한 것은 위의 부등식 4(n+1)***2ⁿ을 만족하지 않아서인데, 이 부등식은 위와 같이 답변 세트를 만들 때 동일한 세트가 반드시 존재한다는 것을 의미한다.

마지막으로, 첫 번째 생각과 두 번째 생각은 상호 보완적임을 알려둔다. 첫 번째 생각은 다소 직관적이어서 두 번째 방법으로 해결할 수 있을 것처럼 생각되는데 실제로는 두 번째 방법에서 나타난 부등식을 만족하지만 실제로 잘 들어맞지 않는 경우도 있다. 이는 두 번째 방법이 완벽하지 않음을 보여주고, 또한 첫 번째 방법으로 잘 찾아지지 않을 때 최소값으로 가능한 n을 먼저 찾고자 하는 경우에는 두 번째 방법이 도움을 준다. 이는 첫 번째 방법을 잘 써먹기 힘든 경우도 있다는 것을 보여준다.