석방을 위한 카드 선택 문제

A, B가 감옥에 따로따로 갇혀있다. 어느 날 간수가 52장의 카드를 앞면이 위를 향하도록 일렬로 늘어놓고 A를 불러들여 이 카드들 중 원한다면 두 장의 위치를 바꿀 수 있게끔 했다. 그리고 A를 돌려보낸 후 모든 카드들을 각각 뒤집은 뒤, B를 불러들였다. (A와 대화를 못하도록 막아두었다)간수는 이 카드들 중 어느 특정한 카드를 랜덤하게 지정해, B가 만약 이 카드를 찾아내면 둘을 석방시키기로 한다. B는 최대 26장의 카드를 뒤집을 수 있을 때, 두 사람은 석방될 수 있는가? 단, A와 B는 간수가 부르기 전 이 룰을 숙지했으며 미리 작전을 짤 수 있었다.

MSRI(Mathematical Sciences Research Institute)의 회지 Emissary 2015년 가을호에 실린 퍼즐 문제. 편집진은 이 문제를 Kiran Kedlaya에게서 듣고 그는 Piotr Krason에게서 들었지만 원출처는 모른다고 한다. 여기서는 Carter와 Wagon의 페이퍼[1]에서 소개한 풀이를 살펴보고자 한다.

답은 “가능하다”이다. 카드들에 1부터 52까지의 수를 부여하면 카드의 배열은 순열로 볼 수 있다. 이 순열을 cycle decomposition할 수 있는데, 예컨대 순열 4,5,2,1,3,6은 이므로 (1,4)(2,5,3)(6)으로 쓸 수 있다.

A는 이 순열이 만약 항등순열이면 따로 카드를 바꾸지 않고 그대로 내버려두고 나온다. 그렇지 않다면, 싸이클들로 분할해서 가장 많은 원소를 가진 싸이클 를 잡아서 두 카드 과 의 위치를 바꾼다. 그러면 그 결과 원래 싸이클은 두 싸이클 와 로 분할된다. 즉 원래 크기의 절반 이하의 크기를 갖는 두 싸이클로 나뉘게 되는 것이다. 그러면 애초에 싸이클 중에서 크기가 26보다 큰 것은 많아봤자 1개까지밖에 있을 수 없는데, 있었다 하더라도 이 A의 행동으로 인해 가장 긴 싸이클은 절반 크기의 싸이클 2개로 나뉘어 그 결과 남게 되는 싸이클은 모두 26 이하의 크기를 갖게 된다.

따라서 B는 간수가 카드 를 지정하면 먼저 번째 카드를 뒤집고, 그 결과가 이면 번째 카드를 뒤집고, 이렇게 뒤집은 카드에 해당하는 순서의 카드를 뒤집는 것을 되풀이한다. 이것은 곧 가 포함된 싸이클의 원소를 하나씩 확인하는 것이 되고, 이 싸이클의 크기는 26 이하므로 26번 이내에 를 찾을 수 있게 된다.

보통 이렇게 앞 사람이 먼저 정보를 확인한 후 어떤 흔적을 남겨 B가 정답을 맞추게끔 하는 유형의 문제에서는 A가 미리 알게 된 정보를 B에게 남기는 식의 전략을 따지는 경우가 많은데, 이 문제는 정보를 남기지 않고 밑작업만을 한다는 점이 인상적이다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2018/05/08)

56. A, B가 감옥에 따로따로 갇혀있다. 어느 날 간수가 52장의 카드를 앞면이 위를 향하도록 일렬로 늘어놓고 A를 불러들여 이 카드들 중 원한다면 두 장의 위치를 바꿀 수 있게끔 했다. 그리고 A를 돌려보낸 후 모든 카드들을 각각 뒤집은 뒤, B를 불러들였다. (A와 대화를 못하도록 막아두었다)

— Elegant Math (@elegant_math) May 9, 2018

References

[1] L. Carter and S. Wagon, “The Mensa Correctional Institute” The American Mathematical Monthly, 125:4, 306-319. DOI: 10.1080/00029890.2018.1418100