콩가루 가족의 강 건너기

 이번 글에서 소개할 퍼즐은 여우-거위-밀알 강 건너기 퍼즐보다는 아마도 덜 오래 됐을 테지만 그럼에도 지금 기준으로 오래된 그런 고전 퍼즐이다. 먼 과거에 만들어진 퍼즐임을 감안하고 문제를 읽어보자.

 

 강 앞에 엄마와 아빠, 아들 둘, 딸 둘, 경찰, 그리고 죄수 이렇게 총 8명이 있다. 이들 앞에는 2인승 보트가 있는데, 오직 엄마, 아빠 그리고 경찰만이 보트의 노를 저을 수 있다.(아들딸은 어려서, 죄수는 묶여있어서 노를 못 젓는다고 가정하자.) 문제는 이들 중 일부가 특정 조건을 만족하면 문제를 일으킨다는 것이다.

- 엄마 없이 아빠와 딸이 같이 있으면 (두 딸 중 아무라도) 아빠가 딸을 혼낸다.

- 아빠 없이 엄마와 아들이 같이 있으면 (두 아들 중 아무라도) 엄마가 아들을 혼낸다.

- 경찰 없이 죄수가 가족 구성원 아무나 같이 있으면 죄수가 가족을 해한다.

 

트러블 없이 8명 모두가 강을 건너는 방법은 무엇인가?

 

 문제의 난이도가 '선교사와 식인종'퍼즐보다 조금 더 올라갔다. 인원이 많기도 하고 또 서로다른 제한을 필요로 하는 사람들이 있어 경우의 수가 더 많아졌기 때문이다. 하지만 덕분에 움직임의 경우의 수도 적어서 어쩌면 더 빨리 풀 수도 있을지도 모른다.

 

 문제의 설정에 놀랄 수도 있는데, 심지어 지금 적은 문장은 필자가 처음 들을 당시 문제 워딩을 조금 순화시킨 것이다. '재미있는 영재들의 수학퍼즐'(박부성 지음) 구판을 보면 경찰과 죄수 대신 하인과 개가 등장하는데, 엄마가 없으면 아빠가 딸을 잡아먹고(?!) 아빠가 없으면 엄마가 아들을 잡아먹으며 하인이 없으면 개가 가족을 잡아먹는 심히 비현실적인 설정이 잡혀있었다.

 

아래는 플래시 게임이 붐을 일으켰던 당시 이 퍼즐을 주제로 만든 게임인데 이를 보아도 상황은 비슷하다. (출처: beeks.eu/Puzzle3.htm)

역시 설정 자체는 변한 바 없지만 그나마 아기자기한 그림으로 표현되있는데 이게 다행인지 아닌지는 잘 모르겠다. 마찬가지로 예전에 만들어졌다는 점을 감안해주기를 바란다.

 

이러한 설정이 너무 과하거나 이상하게 느껴진다면 무생물 친구들(물, 불, 돌?)로 잘 바꿔서 문제를 표현하는 것도 하나의 방법이 될 수 있을 것 같다.

 

 

혹시나 불편해할 사람들을 위해 설명을 길게 달았는데, 이제 (원한다면 설정을 바꿔) 문제를 풀어보자.

 

풀이)

이전 강 건너기 퍼즐에서도 썼지만, 이런 퍼즐에서 필자가 주로 답을 찾는 방법은 바로 평형상태를 찾는 것이다. 평형상태란 강 이편과 저편에 사람들을 놓았을 때, 동일 역할을 가진 사람 수가 양 쪽으로 같으며 보트를 탄 인원이 어느쪽으로 움직여도 무방한 순간을 말한다.

가령 이번 문제의 경우 엄마와 아빠가 같은 역할, 아들들과 딸들이 같은 역할이 될 것이다. 경찰과 죄수는 이질적이므로 평형을 위해 둘은 보트에 탄 상태라 생각하고, 엄마를 강 이편, 아빠를 강 저편에 두어 평형을 만들자. 아이들이 혼나는 상황을 안 만들기 위해선 아들들은 아빠와 같이 강 저편에, 딸들은 엄마와 같이 강 이편에 두면 된다.

 

즉 엄마를 A, 딸을 a, 아빠를 B, 아들을 b, 경찰을 X, 죄수를 x라 두면

A a a :   <X x>   : B b b

가 평형상태이다.

 

평형상태가 편한 것은, 이 상태에서 모든 인원을 한 쪽으로 모으는 방법을 찾으면 곧 대칭성에 의해 문제가 바로 풀린다는 점이다. 달리 말하면 '강 이편' -> '평형상태' -> '강 저편' 순으로 흐르는 움직임의 한 쪽만 찾는 것으로 족하다는 뜻이다.

 

자 그럼 평형상태에서 B b b를 모두 왼편으로 모이보자.

b가 보트를 타려면 B나 X가 도와줘야하는데 X가 움직이면 곧 x가 다른 가족을 해할 수 있다. 따라서 x가 홀로 강 한 쪽에 있는 순간만 X가 b를 태워줄 수 있다. 그림으로 표현하면

A a a B b :   ←<X b>    : x

가 된다. 이 상태 이후는 X가 x를 데리러 왔다갔다하면 끝이므로, 이 상태가 되기 전을 역으로 추적해보자. 그러면,

A a a B b :              <>: X x b

A a a B b X x :<>         : b

A a a X x :               <>: B b b

A a a B X x :<>            : b b

a a X x :                  <>: A B b b

A a a X x:<>                : B b b

가 됨을 쉽게 찾을 수 있다.(이전의 행동을 반복하지 않으면서 트러블이 일어나지 않게 보트에 누군가 타는 경우를 찾으면 된다.) 마지막 상태에서 X x 가 보트를 타면 평형상태이므로 사실상 답을 찾은 것이 된다.