강 건너기 퍼즐

3. 퍼즐의 예시

강 건너기 퍼즐의 대표적인 예시는 다음과 같다.

• 여우, 거위, 콩자루 문제: 농부가 여우, 거위, 콩자루를 가지고 강을 건너는 문제이다. 농부가 없을 때 여우와 거위가 같이 있으면 여우가 거위를 잡아먹고, 거위와 콩자루가 같이 있으면 거위가 콩자루를 먹는다. 농부만이 노를 저을 수 있으며, 한 번에 한 품목만 옮길 수 있다는 조건에서 세 품목을 모두 안전하게 옮겨야 한다.^[7]

• 선교사와 식인종 문제: 선교사 3명과 식인종 3명이 강을 건너는 문제이다. 강 양쪽에서 선교사보다 식인종의 수가 많아지면 안 된다. 보트에는 한 번에 두 사람만 탈 수 있다는 조건에서 여섯 명 모두 안전하게 강을 건너야 한다.^[1]

• 늑대와 양과 양배추: 늑대, 염소, 양배추를 가진 농부가 강을 건너는 문제이다. 농부가 없으면 늑대가 염소를 먹고, 염소가 양배추를 먹는다. 보트에는 농부 외에 동물 한 마리 또는 양배추 하나만 실을 수 있고, 농부만이 보트를 저을 수 있다는 조건에서 모든 것을 안전하게 옮겨야 한다.^[4]

3. 1. 여우, 거위, 콩자루 문제

3. 2. 선교사와 식인종 문제

3. 3. 늑대와 양과 양배추

• 보트를 저을 수 있는 것은 농부뿐이다.
• 보트에는 농부 외에 동물 1마리 또는 양배추 1개만 실을 수 있다.
• 농부가 없을 때 늑대와 염소를 둔 채로 두면 늑대가 염소를 먹는다.
• 농부가 없을 때 염소와 양배추를 둔 채로 두면 염소가 양배추를 먹는다.

3. 4. 간단한 예

• 여우, 거위, 콩자루 문제: 농부가 여우, 거위, 콩자루를 가지고 강을 건너려고 한다. 농부가 없을 때, 여우와 거위가 같이 있으면 여우는 거위를 잡아먹고, 거위와 콩자루가 같이 있으면 거위는 콩자루를 먹어 치운다. 노를 저을 수 있는 것은 농부뿐이며, 한 번에 한 품목만 옮길 수 있다고 할 때, 아무 피해 없이 세 품목을 모두 강 건너로 옮겨야 한다.

• 선교사와 식인종 문제: 선교사 세 명과 식인종 세 명이 강을 건너려고 한다. 강의 어느 쪽이든 선교사보다 식인종의 수가 많게 되면 식인종은 선교사를 해친다. 그러나 선교사와 식인종의 수가 같거나 선교사가 많으면 아무도 해치지 않는다. 한 번에 두 사람만 보트에 탈 수 있다고 할 때, 여섯 사람이 무사히 강을 건너도록 해야 한다.^[1]

• 어른 1명과 아이 2명이 강가에 있고, 배 한 척이 있다. 배에는 어른은 1명만 탈 수 있고, 아이는 1명 또는 2명이 탈 수 있다(배를 젓는 것은 모두 가능하다). 모두가 강을 건너려면 어떻게 해야 할까? 이 문제는 8세기에 캔터베리 대주교가 제시한 문제라고 한다.^[2][3]

• 늑대와 염소를 데리고 양배추를 가진 농부가 강가에 있다. 강에는 보트 한 척이 있고, 다음의 제약 조건이 있다.^[4]
• 보트를 저을 수 있는 것은 농부뿐이다.^[5]
• 보트에는 농부 외에 동물 1마리 또는 양배추 1개만 실을 수 있다.^[6]
• 농부가 없을 때 늑대와 염소를 둔 채로 두면 늑대가 염소를 먹어버린다.^[7]
• 농부가 없을 때 염소와 양배추를 둔 채로 두면 염소가 양배추를 먹어버린다.^[8]

4. 문제 해결 전략

금지된 상태가 되지 않도록 이동시키면 거의 외길로 풀리는 경우도 있다.

다음 사항을 고려하면 잘 풀리는 경우가 많다.^[1]

• 보트를 젓는 사람을 확보한다.
• 반대편으로 건너간 사람(물건)을 나중에 다시 데려온다.
• 처음에는 2명 이상(또는 1명과 무엇인가)으로 건너야 한다.
• 만약 1명만 건너면 그 1명이 돌아올 수밖에 없으므로 처음 상태로 돌아가기 때문이다.

5. 수학적 분석

초르버(Csorba), 휘르컨스(Hurkens), 보에깅어(Woeginger)는 2008년에 $Alcuin(G)\; =\; \backslash tau(G)$ 또는 $Alcuin(G)\; =\; \backslash tau(G)\; +\; 1$ 중 어느 것이 성립하는지 결정하는 것은 NP-난해함을 증명했다.^[4] 최소 정점 덮개 문제는 NP-완전이므로, 그래프 $G$의 알쿠인 수를 계산하는 것 또한 NP-난해하다. 그러나 특정 클래스의 그래프에서는 더 강력한 결과가 적용된다. 예를 들어, 평면 그래프의 경우 두 관계 중 어느 것이 성립하는지 다항 시간 내에 결정할 수 있다(하지만 $Alcuin(G)$ 또는 $\backslash tau(G)$를 결정하는 것은 여전히 NP-hard). 이분 그래프의 경우 $Alcuin(G)$와 $\backslash tau(G)$는 모두 다항 시간 내에 정확하게 계산할 수 있다.^[4]

5. 1. 그래프 이론적 접근

6. 다양한 변형

조건을 조금 바꾸면 새로운 문제를 만들 수 있다. 질투심 많은 (자신이 없는 곳에서 아내가 다른 남자와 있는 것을 싫어하는) 부부들의 문제 등이 유명하다.^[1]

또한, 다음과 같은 방법으로 새로운 문제를 만들 수 있다.

• 강 중간에 중주(사람이나 짐을 놓을 수 있는 곳)를 설치한다.
• 보트의 정원 및 대수를 변경한다.^[1]

7. 문제의 성질

$G=(V,\; E)$를 농부가 옮겨야 하는 물품을 나타내는 정점 집합 $V$와 갈등을 일으키는 물품 쌍으로 구성된 간선 집합 $E$를 갖는 무방향 그래프라고 하자. 예를 들어 정점 $v\_1$이 거위를 나타내고 $v\_2$가 콩 자루를 나타낸다면, 거위는 콩 자루와 같은 강가에 남겨질 수 없으므로 두 정점은 연결된다. 두 물품 간의 갈등의 성격은 그들이 같은 강가에 남겨질 수 없다는 사실에 영향을 미치지 않으므로 간선은 무방향이다. 문제의 목표는 여행이 가능한 보트의 최소 크기를 결정하는 것이며, 이를 $G$의 '''알쿠인 수'''라고 한다.

농부가 먼저 물품의 부분 집합 $V\text{'}$을 강 건너편으로 옮기고, 나머지 $V\; \backslash setminus\; V\text{'}$의 물품을 강가에 남겨두는 성공적인 강 건너기를 생각해 보자. 여행이 성공적이므로 강가에 남겨진 물품에는 갈등이 없어야 한다. 즉, $G$에서 $V\; \backslash setminus\; V\text{'}$의 두 요소 사이에 $E$에 있는 간선이 없다. 이는 모든 간선 $E$가 $V\text{'}$에 하나 또는 두 개의 정점을 갖는다는 것을 의미한다. 즉, $V\text{'}$는 $G$의 정점 덮개이다. 따라서 보트의 크기는 $G$의 최소 정점 덮개의 크기 $\backslash tau(G)$보다 커야 하며, 이는 $G$의 알쿠인 수에 대한 하한을 형성한다. $Alcuin(G)\; \backslash ge\; \backslash tau(G)$.

반면에 보트 크기가 $\backslash tau(G)\; +1$과 같은 성공적인 여행을 완료하는 것이 가능하다. 이는 최소 정점 덮개의 구성원 $V\text{'}$이 항상 보트에 남아 있도록 요구함으로써 달성할 수 있다. 이 물품의 수는 $\backslash tau(G)$이며, 따라서 보트에 공간이 하나 더 남는다. 나머지 $V\backslash setminus\; V\text{'}$ 물품 사이에는 갈등이 없으므로, 보트의 남은 공간 하나를 차지하면서 어떤 순서로든 한 번에 하나씩 강 건너편으로 옮길 수 있다. 따라서, $Alcuin(G)\; \backslash le\; \backslash tau(G)\; +\; 1$이므로 $Alcuin(G)$의 상한을 형성한다. 이것들을 함께 결합하면, $\backslash tau(G)\; \backslash le\; Alcuin(G)\; \backslash le\; \backslash tau(G)\; +\; 1$을 얻는다. 즉, $Alcuin(G)\; =\; \backslash tau(G)$ 또는 $Alcuin(G)\; =\; \backslash tau(G)\; +\; 1$이다.^[7]

Csorba, Hurkens 및 Woeginger는 2008년에 $Alcuin(G)\; =\; \backslash tau(G)$ 또는 $Alcuin(G)\; =\; \backslash tau(G)\; +\; 1$ 중 어느 것이 성립하는지 결정하는 것은 NP-난해임을 증명했다.^[4] 최소 정점 덮개 문제는 NP-완전이므로, 그래프 $G$의 알쿠인 수를 계산하는 것은 NP-난해하다. 그러나 특정 클래스의 그래프에서는 더 강력한 결과가 적용된다. 예를 들어, 평면 그래프의 경우 두 관계 중 어느 것이 성립하는지 결정하는 것은 다항 시간 내에 수행할 수 있다(하지만 $Alcuin(G)$ 또는 $\backslash tau(G)$를 결정하는 것은 여전히 NP-hard). 이분 그래프의 경우 $Alcuin(G)$와 $\backslash tau(G)$는 모두 다항 시간 내에 정확하게 계산할 수 있다.^[4]

풀어보지 않아도 다음 사항을 알 수 있다.

• 해결 횟수(보트 이동 횟수)는 홀수이다.
• 보트는 처음에 이쪽 강둑에 있고, 마지막에는 저쪽 강둑으로 간다. 처음부터 몇 번 왕복하든, 왕복하여 보트가 이쪽 강둑으로 돌아왔을 때 보트의 이동은 항상 짝수 회이다. 마지막으로 저쪽 강둑으로 건너가기 위해서는 한 번 더 이동해야 하므로, 총 이동 횟수는 홀수 회가 된다.
• 반수가 건너는 지점을 중심으로 (최소 횟수로 유일한) 해는 대칭이 된다.
• 다 건너간 최종 상태에서 해를 역순으로 따라가면, 최초의 상태로 돌아갈 수 있다. 그 절차는 저쪽 강둑에서 이쪽 강둑으로의 강 건너기 문제의 해가 된다. 저쪽 강둑과 이쪽 강둑을 바꿔 생각하면 원래 해와 일치하므로, 해는 대칭이 된다.

참조

_[1] 간행물 Tricky crossings http://www.sciencene[...] 2008-02-07
_[2] 간행물 "The Jealous Husbands" and "The Missionaries and Cannibals" The Mathematical Association
_[3] 간행물 An analytic method for the "difficult crossing" puzzles
_[4] 서적 Algorithms: ESA 2008 Springer-Verlag
_[5] 간행물 Dynamic programming and "difficult crossing" puzzles Mathematical Association of America
_[6] 간행물 Alcuin's Transportation Problems and Integer Programming http://www.zib.de/Pu[...] Konrad-Zuse-Zentrum für Informationstechnik Berlin
_[7] AV media River Crossings (and Alcuin Numbers) - Numberphile https://www.youtube.[...] 2018-01-05
_[8] 문서 一例として、ナイーブにコードを書くと宣教師の問題で「宣教師が0人」という状態を「宣教師の方が人数が少ない」として誤って不正解としてしまう、といったものがある。