아인슈타인의 알고리즘 문제 : 금붕어 찾기

오늘은 책을 보다가 매우 재밌는 알고리즘 문제를 발견해서 공유하고자 한다.

아인슈타인이 고안했다고 알려진 문제이다.

마치 내가 짠 문제를 풀어보라고 우리를 놀리는 듯한 그의 표정

아래는 번뜩이는 아이디어가 필요한 알고리즘은 아니지만

그렇다고 해서 IQ 200의 천재가 아니고서야 한방에 절대 풀 수 없는 문제이다.

한 단계 한 단계 실타래를 풀듯이 풀어야한다.

그 과정에서 퍼즐의 조각이 맞춰지는 듯한 쾌감을 느낄 수 있을 것이다.

핵심 포인트는 '교집합' 이다.

[문제]

5명의 각각 다른 집에 모두 다른 국적의 사람이 다른 동물을 키우며 다른 담배와 음료수를 즐기며 살아가고 있다.

다음 중 금붕어를 키우는 사람은 누구인가?

이 문제를 어떻게 풀어야 가장 효율적으로 풀 수 있을까?

우선은 15개의 명제 중에서 확실한 사실들을 골라내야 한다.

명제의 퍼즐을 하나씩 풀어나가기 위해서 우선 아래와 같은 표를 만들어보았다.

집	A	B	C	D	E
국적
색깔
음료수
담배
동물

가장 확실한 명제는 9번이다. 노르웨이 사람은 첫번째 집에 산다.

하나의 답이 나왔다.

집	A	B	C	D	E
국적	노르웨이
색깔
음료수
담배
동물

두번째 확실한 명제는 14번이다.

노르웨이 사람은 파란집의 이웃이므로 B 집은 파란색이 된다.

집	A	B	C	D	E
국적	노르웨이
색깔		파란색
음료수
담배
동물

세번째도 확실한 명제가 있다.

정중앙의 사람은 우유를 마신다.

집	A	B	C	D	E
국적	노르웨이
색깔		파란색
음료수			우유
담배
동물

이제부터 슬슬 어려워진다.

그러나 겁먹을 것 없다. 한단계씩 넘어가면 된다.

4번 명제를 보자.

초록-하얀색은 세트이다.

따라서 (초록,하얀)은 (C,D) 또는 (D,E)가 될 수 있다.

집	A	B	C	D	E
국적	노르웨이
색깔		파란색	초록	초록/하얀	하얀
음료수			우유
담배
동물

그런데 5번 명제에서 초록색 집주인은 커피를 마신다고 했다.

따라서 (C,D)는 위 5번 명제에 위배되므로

(초록,하얀)은 (D,E)가 된다.

집	A	B	C	D	E
국적	노르웨이
색깔		파란색		초록	하얀
음료수			우유	커피
담배
동물

자 이제 슬슬 퍼즐의 조각들이 맞춰져지고 있다.

1번 명제를 보자.

영국 사람은 빨간 집에서 산다.

이 명제가 부합될 수 있는 유일한 장소는 C이다.

A일경우 노르웨이 사람이라서 어긋나고

나머지 B,D,E는 색이 빨강이 아니기 때문에다.

집	A	B	C	D	E
국적	노르웨이		영국
색깔		파란색	빨강	초록	하얀
음료수			우유	커피
담배
동물

이제 남은 색깔은 한개

7번을 보자.

노란색 집이 있단다. 

그럼 자연스럽게 노란색 집은 A가 될 것이고 여기에 사는 노르웨이 사람은 던힐을 피운다 까지 알게된다.

집	A	B	C	D	E
국적	노르웨이		영국
색깔	노란색	파란색	빨강	초록	하얀
음료수			우유	커피
담배	던힐
동물

노란색과 던힐이 나왔으니 그 다음 힌트를 추적해보자.

11번

던힐을 피우는 사람 옆집은 말을 키운다.

집	A	B	C	D	E
국적	노르웨이		영국
색깔	노란색	파란색	빨강	초록	하얀
음료수			우유	커피
담배	던힐
동물		말

자 여기부터가 이 알고리즘 문제의 핵심이다.

이제부턴 명제로 1:1 추론이 불가능하고 교집합간의 비교를 해야한다.

이럴 땐 경우의 수가 가장 적은 명제부터 찾아야 된다.

2번을 보자.

스웨덴 사람과 강아지의 조합은 D 또는 E가 된다.

집	A	B	C	D	E
국적	노르웨이		영국	스웨덴	스웨덴
색깔	노란색	파란색	빨강	초록	하얀
음료수			우유	커피
담배	던힐
동물		말		강아지	강아지

이 가능성을 남겨둔 채 또 다른 명제를 보자.

3번, 덴마크 사람은 차를 마신다.

이 또한 B 또는 E의 조합이 될 수 있다.

집	A	B	C	D	E
국적	노르웨이	덴마크	영국	스웨덴	스웨덴/덴마크
색깔	노란색	파란색	빨강	초록	하얀
음료수		차	우유	커피	차
담배	던힐
동물		말		강아지	강아지

마지막 두가지 경우의 수를 갖는 명제가 있다.

바로 12번

블루매스터와 맥주는 B와 E의 조합이 가능하다.

집	A	B	C	D	E
국적	노르웨이	덴마크	영국	스웨덴	스웨덴/덴마크
색깔	노란색	파란색	빨강	초록	하얀
음료수		차/맥주	우유	커피	차/맥주
담배	던힐	블루매스터			블루매스터
동물		말		강아지	강아지

한가지만 더해보자.

13번. 독일 사람은 프린스를 피운다.

이는 (B,D,E)의 조합이 가능하다.

집	A	B	C	D	E
국적	노르웨이	덴마크 독일	영국	스웨덴 독일	스웨덴/덴마크　 독일
색깔	노란색	파란색	빨강	초록	하얀
음료수		차/맥주	우유	커피	차/맥주
담배	던힐	블루매스터 프린스		프린스	블루매스터 프린스
동물		말		강아지	강아지

자 이제 답이 보이는가?

B가 독일이라고 가정해보자.

그럼 (D,E)는 스웨덴과 덴마크이다.

그러나 이 가정에서는 (맥주,블루매스터)가 들어갈 자리가 사라져서 불가능.

이 하나의 반증으로 모든 실마리가 해결되었다..!

따라서 B는 덴마크가 확정된 것이다.

집	A	B	C	D	E
국적	노르웨이	덴마크	영국	스웨덴 독일	스웨덴 독일
색깔	노란색	파란색	빨강	초록	하얀
음료수		차	우유	커피	맥주
담배	던힐			프린스	블루매스터 프린스
동물		말		강아지	강아지

자 이제 바로 답이 보이기 시작한다.

D가 스웨덴이면 E가 독일이 되면서 (맥주,블루매스터)가 들어갈 자리가 또 없어진다.

따라서 D는 독일이고 E는 스웨덴이면서 (맥주,블루매스터)는 E의 자리에 들어가게 된다.

집	A	B	C	D	E
국적	노르웨이	덴마크	영국	독일	스웨덴
색깔	노란색	파란색	빨강	초록	하얀
음료수		차	우유	커피	맥주
담배	던힐			프린스	블루매스터
동물		말			강아지

나는 위 순간이 이 알고리즘 문제에서 가장 짜릿한 부분이 아닐까 싶다.

여러가지 2가지 경우의 수들을 조합해서

하나의 반증으로 모든 퍼즐의 조각이 맞춰지는 바로 그 순간인 것이다.

자 이제 6번, 10번, 15번 3개의 명제만이 남았다.

6번은 이제 아주 쉽게 풀린다. C밖에 자리가 없기 때문이다.

집	A	B	C	D	E
국적	노르웨이	덴마크	영국	독일	스웨덴
색깔	노란색	파란색	빨강	초록	하얀
음료수		차	우유	커피	맥주
담배	던힐		팔 몰	프린스	블루매스터
동물		말	새		강아지

10번에서 나머지 하나의 담배는 블렌드이므로 B 당첨

그리고 이웃이 고양이를 키우므로 고양이는 A 당첨

마지막 15번에서 블렌드의 이웃이 물을 마시므로 물 또한 A 당첨

집	A	B	C	D	E
국적	노르웨이	덴마크	영국	독일	스웨덴
색깔	노란색	파란색	빨강	초록	하얀
음료수	물	차	우유	커피	맥주
담배	던힐	블렌드	팔 몰	프린스	블루매스터
동물	고양이	말	새		강아지

자, 이제 금붕어가 어디에 들어갈지 보이는가?