글
Askhow에 올라왔던 질문. 무려 2005년도 질문이다.
관련 URL http://www.askhow.co.kr/commonboard/ah_view_ru.asp?idx=1013&no=1451&page=1&keyword=미친개&searchitem=content
여러 논리 퍼즐 책에 소개된 퍼즐이군요. 쉽고 재미있는 예/풀이는 마틴 가드너의 책을 찾아보세요. ^^
마을에 사람도 한명 개도 한마리뿐이라면, 이장이 유일한 주민이고 당연히 자기 개가 미친개라는걸 알겠죠. 뭐, 이장을 제외하고 한명이 있다 하더라도 상황은 마찬가지입니다. 첫날 바로 압니다.
마을에 사람이 두명, 개가 두마리가 있다고 합시다. (앞으로 이장은 빼고 생각합니다) 두번째 날, 두 사람은 모두 웬만큼 똑똑하고, 또한 서로 똑똑한 걸 알기 때문에, 만약 상대방이 자기 개가 미친 개라는 사실을 알았다면 쏴 죽였을 거라는 사실을 알고 있습니다. 첫날은, 서로 개를 살펴볼 수 있겠죠. 이장의 말은 아무튼 사실로 간주되므로, 적어도 한마리의 개는 미친 개입니다.
두마리 중에 한마리는 자기 개, 나머지 한마리는 상대방의 개 입니다. 경우는 두가지로 나누어 집니다. 상대방의 개를 살펴보았더니 미친 개였다. 아니면, 정상인 개였다. 갑, 을의 두 사람이 있다고 하고, 갑견, 을견을 각각 갑과 을의 개 이름이라고 해 봅시다. 갑이 을견을 보고서 미친 개라는 사실을 알았다고 합시다. 그러나 여전히 자신의 개인 갑견이 미쳤는지 아닌지는 알 수 없습니다. 마찬가지로, 을이 갑견을 보고서 미친개라는 사실을 알았다고 합시다. 그러나 여전히 자신의 개인 을견이 미쳤는지 어떤지는 모릅니다. 그러므로 첫날은 그냥 지나갑니다. 그런데, 둘째날은 이제 갑과 을은 서로 "여전히 모르는군!"이라고 생각합니다. 둘 다 바보는 아니므로, 서로가 모른다는 사실을 알 수 있습니다. 그렇다면 남는 확신은 단 하나로, 자기 개가 미쳤다는 걸 알 수 있죠. 반대의 경우를 가정해 봅시다. 갑이 을견을 보고서 "미치지 않았다"는 사실을 알았다면? 그럼 적어도 한마리의 개는 미쳤기 때문에, 자기 개가 미쳤다는 사실을 바로 알게 됩니다. 그럼 첫날 자기 개를 쏴 죽일 것이고, 그 결과로 을은 자기 개는 미치지 않았다는 사실을 알게 되겠죠. (을이 갑견을 보고 미치지 않았다는 사실을 알더라도 마찬가지입니다)
이제, 갑, 을, 병의 세사람이 있고 각각 갑견, 을견, 병견의 세마리의 개가 있다고 합시다. 첫날, 갑은 을견과 병견을 볼 것이고, 을과 병 역시 다른 사람들의 개를 살펴볼 겁니다. 미친 개가 1마리, 2마리, 3마리인 경우로 나누어 생각해 봅시다. 미친 개가 1마리인 경우(이 개가 갑견이라 가정합시다. 다른 개더라도 상관 없습니다) 갑은 을과 병의 개를 보고 모두 미치지 않았다는 사실을 알게 되므로 자기 개를 쏴 죽이고, 을과 병은 갑견이 미쳤다는 걸 알고, 첫날 총성을 들었으므로 을견과 병견은 무사합니다. 물론 갑이 을과 병의 개 중에 한마리의 미친 개가 있다는 사실을 알게 된다면(만약 이 개가 을견이라면), 을은 갑과 병의 개가 미치지 않았다는 사실을 알게 되므로 자기 개를 쏴 죽이게 됩니다. 즉, 개가 한마리만 미쳤으면 첫날 총성이 울립니다. 미친 개가 2마리인 경우(갑견과 을견이라 합시다. 역시 다른 개더라도 상관 없습니다) 갑은 을과 병의 개를 보고, 을견은 미쳤고 병견은 미치지 않았다는 사실을 알게 됩니다. 을은 갑견이 미쳤고 병견이 미치지 않았다는 사실을 알게 됩니다. 병은 두마리 다 미쳤다는 사실을 알게 됩니다. 이런 상황에서, 자신의 개가 미쳤는지 여부는 모두 알 수 없기 때문에 첫날은 그냥 지나갑니다. 첫날이 무사히 지나간 후, 모두들 그날 아무 개도 죽지 않았다는 사실을 알게 됩니다. 그럼 만약 미친 개가 1마리였다면 첫날 적어도 한마리의 개가 죽어야만 한다는 사실을 위의 논리에 의해 알 수 있습니다. 그러므로, 미친 개는 적어도 두마리, 또는 세마리라는 사실을 갑, 을, 병 모두가 알게 됩니다. 그런데, 미친 개가 두마리 이상인데, 갑은 을견이 미쳤고 병견이 미치지 않았다는 사실을 이미 알고 있습니다. 그러므로 자신의 개는 확실히 미쳤다는 사실을 알 수 있습니다. (을도 마찬가지이고, 병은 두마리라는 사실을 알았으므로 병견이 미치지 않았다는 사실을 알 수 있습니다.)
이 논의를 확장하여, n명의 마을 사람들이 있고, n마리의 개 중에서 k마리(n>=k)의 개가 미쳐버린 경우, k일이 지나면 정확히 k마리의 개가, 그것도 정확히 미친 개만 죽는다는 사실을 알 수 있습니다. (일반적인 n,k에 관한 논리는 직접 생각해 보세요 ^^)
추가
일반적인 n마리의 개에 대해 k마리의 개가 미친 개인 경우를 생각해 봅시다. n마리의 개를 1번부터 n번째까지 번를 붙여놓고 i견이라고 칭해 봅시다. 물론 i견의 주인은 i이겠죠. 단, 아무도 k를 모릅니다. 또한 k는 양의 정수입니다. 그리고 n은 k와 같거나 보다 큰 정수입니다. 그리고 모든 사람이 k가 양의 정수라는 사실은 알고 있습니다. 그리고 모든 사람은 자신의 개가 미친개이거나 아니거나 무관하게 자신의 개를 제외한 모든 미친개를 발견할 수 있습니다.
따라서
만약 i견이 미친개라면 i는 k-1마리의 미친개를 발견합니다.
만약 i견이 미친개가 아니라면 i는 k마리의 미친개를 발견합니다.
k가 1이라고 합시다. 그럼 k-1=0이므로, 미친개의 주인은 주변에 미친개를 단 한마리도 발견하지 못합니다. 따라서 자신의 개가 미친개임을 알 수 있습니다.
k가 2라고 합시다. 그럼 미친개의 주인은 주변에 미친개를 딱 한마리 발견합니다. 그리고 미친개의 주인이 아닌 사람들은 주변에 미친개를 딱 두마리 발견합니다. 이때. "만약 미친개가 딱 1마리밖에 없었다면, 미친개의 주인은 자신의 개가 미친개라는 사실을 알 수 있다"는 사실을 모든 사람이 깨닫습니다. 따라서, 모든 사람은 최소한 미친개가 2마리 이상 있다는 사실을 알 수 있습니다. 그런데 미친개를 딱 1마리 발견한 사람이 있습니다. 따라서 그 사람은 자신의 개가 미친 개라는 사실을 알 수 있습니다.
k가 3이라고 합시다. 그럼 미친개의 주인은 주변에 미친개를 딱 2마리 발견하고, 미친개의 주인이 아닌 사람은 주변에 미친개를 딱 3마리 발견합니다. 그런데, 만약 미친개가 딱 1마리였다면, 첫번째 경우에서 미친개의 주인이 눈치를 챌 수 있고, 미친개가 딱 2마리였다면 두번째 경우에서 미친개의 주인이 눈치를 챌 수 있습니다. 따라서 모든 사람은 미친개가 3마리 이상 있다는 사실을 알 수 있습니다. 그런데 미친개를 딱 2마리 발견한 사람이 있죠. 따라서 그 사람은 자신의 개가 미친 개라는 사실을 알 수 있습니다.
k가 일반적인, 그냥 k라고 합시다. 그럼 미친개의 주인은 주변에 미친개를 딱 k-1마리 발견하고 미친개의 주인이 아닌 사람은 주변에 미친개를 딱 k마리 발견합니다. 그런데, 미친개가 딱 1마리였다면 첫번째 경우에서 미친개의 주인이 알아챌 수 있다는 사실을 모두 알 수 있고, 미친개가 딱 2마리였다면 두번째 경우에서 미친개의 주인이 알아챌 수 있다는 사실을 모두 알 수 있고, ..., 미친개가 딱 k-1마리였다면 k-1번째 경우에서 미친개의 주인이 알아챌 수 있다는 사실을 모두 알 수 있습니다. 따라서 모든 사람은 미친개가 k마리 이상 있다는 사실을 알 수 있습니다. 이 사실까지도 누구나 추정 가능합니다. 그런데 미친개의 주인은 미친개를 k-1마리만 발견합니다. 따라서 미친개의 주인은 자신의 개가 미친개라는 사실을 알 수 있습니다.
즉, 정확히 k단계가 지나면 미친개의 주인은 앞서의 논리를 모두 생각할 수 있기 때문에 자신의 개가 미쳤다는 것을 알 수 있습니다.
이 증명은 n=1인 경우에 자명하고, 일반적인 n마리의 개에 대해서 성립할 경우 n+1마리의 개가 있을 경우에도 성립함을 증명해야 합니다. 그건 위의 논리를 k=1부터 k=n까지 성립한다고 가정하면, n->n+1인 경우에도 k=1부터 k=n+1까지 성립함을 쉽게 증명할 수 있으므로 성립합니다.
대략 증명 끝입니다.
관련 URL http://www.askhow.co.kr/commonboard/ah_view_ru.asp?idx=1013&no=1451&page=1&keyword=미친개&searchitem=content
이 문제를 모르겠어서 그러는데 아시는 분 답변좀 달아 주시길 바래요.
(문제가 약간 특이해요^^)
어떤 마을 사람들은 모두 개를 한 마리씩 키웁니다. 어느 날 마을 이장이 동네에 미친개가 잇으니 자기 개가 미쳤다는 것을 안 사람은 자정에 총으로 자기 개를 쏘아 죽이라고 말했습니다. 그런데 개의 주인은 자기 개가 미쳤는지를 알 수 없고 다른 사람의 개가 미쳤는지만 알 수 잇습니다. 하루 동안에 모든 개를 둘러 본 사람들은 주민 모두의 개를 살펴볼 수 있지만 개 주인에게 말해서는 안됩니다. 첫날 밤 자정이 되었지만 총성은 들리지 않았습니다. 이틀째도, 사흘째도, 총성이 들리지 않았는데 오일 째 되는 날 일제히 총성이 들렸습니다. 이 마을의 미친개는 모두 멏 마리일까요?
"꼭 좀 부탁드려요~^^;;"
여러 논리 퍼즐 책에 소개된 퍼즐이군요. 쉽고 재미있는 예/풀이는 마틴 가드너의 책을 찾아보세요. ^^
마을에 사람도 한명 개도 한마리뿐이라면, 이장이 유일한 주민이고 당연히 자기 개가 미친개라는걸 알겠죠. 뭐, 이장을 제외하고 한명이 있다 하더라도 상황은 마찬가지입니다. 첫날 바로 압니다.
마을에 사람이 두명, 개가 두마리가 있다고 합시다. (앞으로 이장은 빼고 생각합니다) 두번째 날, 두 사람은 모두 웬만큼 똑똑하고, 또한 서로 똑똑한 걸 알기 때문에, 만약 상대방이 자기 개가 미친 개라는 사실을 알았다면 쏴 죽였을 거라는 사실을 알고 있습니다. 첫날은, 서로 개를 살펴볼 수 있겠죠. 이장의 말은 아무튼 사실로 간주되므로, 적어도 한마리의 개는 미친 개입니다.
두마리 중에 한마리는 자기 개, 나머지 한마리는 상대방의 개 입니다. 경우는 두가지로 나누어 집니다. 상대방의 개를 살펴보았더니 미친 개였다. 아니면, 정상인 개였다. 갑, 을의 두 사람이 있다고 하고, 갑견, 을견을 각각 갑과 을의 개 이름이라고 해 봅시다. 갑이 을견을 보고서 미친 개라는 사실을 알았다고 합시다. 그러나 여전히 자신의 개인 갑견이 미쳤는지 아닌지는 알 수 없습니다. 마찬가지로, 을이 갑견을 보고서 미친개라는 사실을 알았다고 합시다. 그러나 여전히 자신의 개인 을견이 미쳤는지 어떤지는 모릅니다. 그러므로 첫날은 그냥 지나갑니다. 그런데, 둘째날은 이제 갑과 을은 서로 "여전히 모르는군!"이라고 생각합니다. 둘 다 바보는 아니므로, 서로가 모른다는 사실을 알 수 있습니다. 그렇다면 남는 확신은 단 하나로, 자기 개가 미쳤다는 걸 알 수 있죠. 반대의 경우를 가정해 봅시다. 갑이 을견을 보고서 "미치지 않았다"는 사실을 알았다면? 그럼 적어도 한마리의 개는 미쳤기 때문에, 자기 개가 미쳤다는 사실을 바로 알게 됩니다. 그럼 첫날 자기 개를 쏴 죽일 것이고, 그 결과로 을은 자기 개는 미치지 않았다는 사실을 알게 되겠죠. (을이 갑견을 보고 미치지 않았다는 사실을 알더라도 마찬가지입니다)
이제, 갑, 을, 병의 세사람이 있고 각각 갑견, 을견, 병견의 세마리의 개가 있다고 합시다. 첫날, 갑은 을견과 병견을 볼 것이고, 을과 병 역시 다른 사람들의 개를 살펴볼 겁니다. 미친 개가 1마리, 2마리, 3마리인 경우로 나누어 생각해 봅시다. 미친 개가 1마리인 경우(이 개가 갑견이라 가정합시다. 다른 개더라도 상관 없습니다) 갑은 을과 병의 개를 보고 모두 미치지 않았다는 사실을 알게 되므로 자기 개를 쏴 죽이고, 을과 병은 갑견이 미쳤다는 걸 알고, 첫날 총성을 들었으므로 을견과 병견은 무사합니다. 물론 갑이 을과 병의 개 중에 한마리의 미친 개가 있다는 사실을 알게 된다면(만약 이 개가 을견이라면), 을은 갑과 병의 개가 미치지 않았다는 사실을 알게 되므로 자기 개를 쏴 죽이게 됩니다. 즉, 개가 한마리만 미쳤으면 첫날 총성이 울립니다. 미친 개가 2마리인 경우(갑견과 을견이라 합시다. 역시 다른 개더라도 상관 없습니다) 갑은 을과 병의 개를 보고, 을견은 미쳤고 병견은 미치지 않았다는 사실을 알게 됩니다. 을은 갑견이 미쳤고 병견이 미치지 않았다는 사실을 알게 됩니다. 병은 두마리 다 미쳤다는 사실을 알게 됩니다. 이런 상황에서, 자신의 개가 미쳤는지 여부는 모두 알 수 없기 때문에 첫날은 그냥 지나갑니다. 첫날이 무사히 지나간 후, 모두들 그날 아무 개도 죽지 않았다는 사실을 알게 됩니다. 그럼 만약 미친 개가 1마리였다면 첫날 적어도 한마리의 개가 죽어야만 한다는 사실을 위의 논리에 의해 알 수 있습니다. 그러므로, 미친 개는 적어도 두마리, 또는 세마리라는 사실을 갑, 을, 병 모두가 알게 됩니다. 그런데, 미친 개가 두마리 이상인데, 갑은 을견이 미쳤고 병견이 미치지 않았다는 사실을 이미 알고 있습니다. 그러므로 자신의 개는 확실히 미쳤다는 사실을 알 수 있습니다. (을도 마찬가지이고, 병은 두마리라는 사실을 알았으므로 병견이 미치지 않았다는 사실을 알 수 있습니다.)
이 논의를 확장하여, n명의 마을 사람들이 있고, n마리의 개 중에서 k마리(n>=k)의 개가 미쳐버린 경우, k일이 지나면 정확히 k마리의 개가, 그것도 정확히 미친 개만 죽는다는 사실을 알 수 있습니다. (일반적인 n,k에 관한 논리는 직접 생각해 보세요 ^^)
추가
일반적인 n마리의 개에 대해 k마리의 개가 미친 개인 경우를 생각해 봅시다. n마리의 개를 1번부터 n번째까지 번를 붙여놓고 i견이라고 칭해 봅시다. 물론 i견의 주인은 i이겠죠. 단, 아무도 k를 모릅니다. 또한 k는 양의 정수입니다. 그리고 n은 k와 같거나 보다 큰 정수입니다. 그리고 모든 사람이 k가 양의 정수라는 사실은 알고 있습니다. 그리고 모든 사람은 자신의 개가 미친개이거나 아니거나 무관하게 자신의 개를 제외한 모든 미친개를 발견할 수 있습니다.
따라서
만약 i견이 미친개라면 i는 k-1마리의 미친개를 발견합니다.
만약 i견이 미친개가 아니라면 i는 k마리의 미친개를 발견합니다.
k가 1이라고 합시다. 그럼 k-1=0이므로, 미친개의 주인은 주변에 미친개를 단 한마리도 발견하지 못합니다. 따라서 자신의 개가 미친개임을 알 수 있습니다.
k가 2라고 합시다. 그럼 미친개의 주인은 주변에 미친개를 딱 한마리 발견합니다. 그리고 미친개의 주인이 아닌 사람들은 주변에 미친개를 딱 두마리 발견합니다. 이때. "만약 미친개가 딱 1마리밖에 없었다면, 미친개의 주인은 자신의 개가 미친개라는 사실을 알 수 있다"는 사실을 모든 사람이 깨닫습니다. 따라서, 모든 사람은 최소한 미친개가 2마리 이상 있다는 사실을 알 수 있습니다. 그런데 미친개를 딱 1마리 발견한 사람이 있습니다. 따라서 그 사람은 자신의 개가 미친 개라는 사실을 알 수 있습니다.
k가 3이라고 합시다. 그럼 미친개의 주인은 주변에 미친개를 딱 2마리 발견하고, 미친개의 주인이 아닌 사람은 주변에 미친개를 딱 3마리 발견합니다. 그런데, 만약 미친개가 딱 1마리였다면, 첫번째 경우에서 미친개의 주인이 눈치를 챌 수 있고, 미친개가 딱 2마리였다면 두번째 경우에서 미친개의 주인이 눈치를 챌 수 있습니다. 따라서 모든 사람은 미친개가 3마리 이상 있다는 사실을 알 수 있습니다. 그런데 미친개를 딱 2마리 발견한 사람이 있죠. 따라서 그 사람은 자신의 개가 미친 개라는 사실을 알 수 있습니다.
k가 일반적인, 그냥 k라고 합시다. 그럼 미친개의 주인은 주변에 미친개를 딱 k-1마리 발견하고 미친개의 주인이 아닌 사람은 주변에 미친개를 딱 k마리 발견합니다. 그런데, 미친개가 딱 1마리였다면 첫번째 경우에서 미친개의 주인이 알아챌 수 있다는 사실을 모두 알 수 있고, 미친개가 딱 2마리였다면 두번째 경우에서 미친개의 주인이 알아챌 수 있다는 사실을 모두 알 수 있고, ..., 미친개가 딱 k-1마리였다면 k-1번째 경우에서 미친개의 주인이 알아챌 수 있다는 사실을 모두 알 수 있습니다. 따라서 모든 사람은 미친개가 k마리 이상 있다는 사실을 알 수 있습니다. 이 사실까지도 누구나 추정 가능합니다. 그런데 미친개의 주인은 미친개를 k-1마리만 발견합니다. 따라서 미친개의 주인은 자신의 개가 미친개라는 사실을 알 수 있습니다.
즉, 정확히 k단계가 지나면 미친개의 주인은 앞서의 논리를 모두 생각할 수 있기 때문에 자신의 개가 미쳤다는 것을 알 수 있습니다.
이 증명은 n=1인 경우에 자명하고, 일반적인 n마리의 개에 대해서 성립할 경우 n+1마리의 개가 있을 경우에도 성립함을 증명해야 합니다. 그건 위의 논리를 k=1부터 k=n까지 성립한다고 가정하면, n->n+1인 경우에도 k=1부터 k=n+1까지 성립함을 쉽게 증명할 수 있으므로 성립합니다.
대략 증명 끝입니다.
RECENT COMMENT