석방을 위한 카드 선택 문제

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 \rightarrow 4 \rightarrow 1, 2 \rightarrow 5 \rightarrow 3 \rightarrow 2, 6 \rightarrow 6이므로 (1,4)(2,5,3)(6)으로 쓸 수 있다.

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

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

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

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

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

석방을 위한 카드 선택 문제”의 2개의 생각

  1. 몇년 전에 같은 아이디어의 문제를 본 기억이 있는데, A가 카드 위치를 바꾸지 않아도 되는 확률이 상당이 높더군요. (30% 이상) 카드 장수가 많아져도 이 확률은 수렴합니다.

    좋아요

    1. 맞습니다. k>n/2에 대해 가장 긴 싸이클 길이가 k인 순열 개수가 n!/k로 나오니, 모든 cycle length가 n/2 이하일 확률은 1-(\frac{1}{\lfloor n/2 \rfloor+1} + \cdots + \frac{1}{n}) \rightarrow 1-\ln 2=0.307 \ldots가 되어 말씀하신 바와 같이 30% 이상의 확률로 성공하게 됩니다.

      좋아요

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중