이쁜왕자 만쉐~~
Conway immobilizer 본문
간만에 퀴즈 타임.
감옥에 갇힌 50명의 수학자들이 석방을 놓고 간수와 게임을 합니다. 게임의 규칙은 다음과 같습니다.
1) 수학자들은 한 번에 한 명씩 테이블이 있는 방에 들어옵니다.
2) 테이블에는 A, K, Q 각 한장씩 세 장의 카드가 있고, 카드를 놓을 수 있는 자리가 3곳(1, 2, 3번) 있습니다.
3) 1~3번 자리에는 각각 카드가 없을 수도 있고, 카드가 1장 있거나, 2장 있거나, 3장의 카드가 전부 놓여 있을 수도 있습니다. 초기 상태는 간수 마음대로입니다.
4) 모든 카드들은 전부 앞면이 보이도록 놓여 있지만, 여러 장이 한 자리에 겹쳐 있을 경우 맨 위의 카드만 확인할 수 있으며, ***몇 장의 카드가 겹쳐 있는지는 알 수 없습니다.*** <-- {A, K, 빈자리} 이렇게 보이고 있다면 Q가 어느 카드의 밑에 깔려 있는지 수학자는 모릅니다.
5) 방에 들어온 수학자는 테이블의 상태를 보고 x번 자리에서 y번 자리로 카드를 한 장 옮길 수 있습니다. 그러면 간수는 x번 자리에서 맨 위의 카드를 들어다 y번 자리의 맨 위로 옮겨놓습니다.
6) 만약 카드를 옮겼더니 3번 자리에 위부터 A, K, Q 순서대로 카드들이 정렬돼서 쌓인 상태가 되면 수학자들이 게임에서 승리하고, 전원 석방됩니다.
7) 6번의 상태가 아니라면 간수는 그 수학자를 다른 곳에 가두고 다음 수학자를 테이블로 데려옵니다. 모든 수학자가 다 한 번씩 카드를 옮겼는데도 카드 정렬에 실패하면 수학자들은 석방되지 못합니다.
8) 수학자들은 게임이 시작되기 전에는 전략을 충분히 의논할 수 있지만, 게임이 시작되면 어떤 종류의 커뮤니케이션도 할 수 없습니다. 수학자들은 어떤 전략을 세워야 게임에서 반드시 이길 수 있을까요?
------
최근 인터넷에 뜬 Conway immobilizer 라는 이름이 붙은 문제를 (그 콘웨입니다) 죄수와 간수 버전으로 번안해봤습니다. 문제에 저런 이름이 붙은 이유는 어떤 사람이 저거 풀려고 여섯시간동안 책상에 못박혀서 끙끙거렸기 때문이라나...
좋아요좋아요 ·
나의 풀이
경우 0) 카드의 상태가 A - x - K 이다. (주: x 는 '카드없음'을 의미함.)
만약 A 에 한장 뿐이어서, x-x-A 가 만들어진다면 승리하며 끝난다.
만약 A 밑에 Q 가 있어서, Q-x-AK 가 만들어지면, 경우 2로 간다. 경우2의 규칙에 따르면 차례대로 x-Q-AK => A-Q-K 가 되어 경우3으로 가게 된다. (주: AK 는 A 밑에 K 가 있음을 의미함)
경우1) 카드가 한곳에만 있다.
행동 => 그 더미에서 제일 위의 카드를 꺼내서 바로 왼쪽에 둔다. (주: 첫번째 위치의 왼쪽은 세번째이다.)
3장-x-x => 2장-x-1장
x-3장-x => 1장-2장-x
x-x-3장 => x-1장-2장
*NOTE* 어느 경우이든 경우2로 간다. 그것도 항상 경우2-2 가 된다.
경우2) 카드가 두 곳에 있다.
행동 => 비어 있는 곳의 왼쪽 카드를 한장 꺼내서 비어 있는 곳에 둔다.
예를 들어 A - x - Q 라면, x 의 왼쪽은 A 이므로, A를 집어서 x 에 놓는다.
경우2-1) 비어있는 곳의 왼쪽에는 카드가 1장이다.
다시 카드는 두 곳으로 모이게 되지만, 비어있는 곳의 왼쪽은 반드시 2장이 된다. 즉. 경우 2-2 가 된다.
예를 들어 A - x - QK 였다면, x - A - QK 가 되지만, 이번에는 x 의 왼쪽에는 2장이 된다.
경우2-2) 비어있는 곳의 왼쪽에는 카드가 2장이다.
이 행동의 결과로 3장이 모두 오픈된다. 즉 경우3으로 가게 된다.
*NOTE* 경우1) 에서의 행동의 결과 반드시 경우 2-2)가 된다.
경우3) 세 카드가 모두 오픈되어 있다.
(주: 3장이 모두 오픈되면 A-K-Q 순서대로 정렬하는 것이 목표가 된다.)
경우3-1) A-K-Q -> 경우 4로 간다.
경우3-2) A-Q-K. Q-K-A. K-A-Q : 1개의 위치는 맞는 경우
행동 => 위치가 맞는 카드의 왼쪽 카드를 위치가 맞는 카드 위로 올린다.
예를 들어 A-Q-K 라면 K 를 A 위로 이동시킨다. 즉 KA-Q-x 가 되는데, 이 다음은 경우2의 규칙에 따라, KA-x-Q => A-K-Q 가 된다.
Q-K-A 는 x-QK-A => A-QK-x =>A-K-Q
K-A-Q 는 K-x-AQ => x-K-AQ => A-K-Q
경우3-3) Q-A-K, K-Q-A : 위치가 하나도 안맞는 경우
행동 => 아무 카드나 하나를 오른쪽으로 옮긴다. 이 경우는 간단히 Q 를 A 위로 올린다.
Q-A-K 의 경우는 x-QA-K => K-QA-x => K-A-Q 로 경우 3-2 가 된다.
K-Q-A 의 경우는 K-x-QA => x-K-QA => A-Q-K 로 경우 3-2 가 된다.
경우4) 카드의 상태가 A - K - Q 이다.
행동 => K 를 Q 위에 올린다.
그리고, 이 결과로 만들어지는 것은 경우0 이고, 승리하게 된다.
요약 : 초기 상태가 어떤 상태에서 시작하든 3장을 모두 오픈 시킨다음, 이를 A-K-Q 순서로 정렬하고, A-x-K => x-x-A 로 만들어 승리한다.
