조합론 · 재귀 · 이진법

마지막까지 살아남는 자리

원을 그리고 둘러앉아 한 사람씩 사라질 때, 끝까지 남는 자리는 어디인가. 2천 년 전의 전설에서 출발해 이진수 한 줄로 끝나는 이야기.

원 하나를 그려 보자. 그 둘레에 마흔한 명이 1번부터 41번까지 차례로 둘러앉아 있다. 어느 한 사람이 시작점이 되어 자기 바로 옆 사람을 제거한다. 그러면 그다음에 살아 있는 사람이 다시 자기 옆에서 살아 있는 사람을 제거한다. 이렇게 원을 따라 한 칸씩 건너뛰며 제거가 이어지고, 결국 단 한 사람만 남는다.

질문은 단순하다. 당신이 이 원 안 어딘가에 앉아야 한다면, 끝까지 살아남기 위해 몇 번째 자리를 골라야 하는가? 자리를 무작위로 고른다면 살아남을 확률은 41분의 1에 불과하다. 그러나 제거의 규칙이 완전히 결정되어 있으므로, 사실 결과도 처음부터 정해져 있다. 누가 마지막에 남는지는 운이 아니라 계산의 문제다.

이 수수께끼는 흔히 요세푸스 문제(Josephus problem)라고 불린다. 일견 복잡해 보이지만, 끝에 가서는 놀랄 만큼 간결한 답으로 귀결된다. 답에 이르는 길에는 수학자가 답을 모르는 문제를 마주했을 때 실제로 밟는 사고의 단계가 고스란히 담겨 있다. 작은 경우부터 직접 해 보고, 표를 만들어 패턴을 찾고, 가장 깨끗한 한 가지 경우를 먼저 증명한 다음, 그것을 지렛대 삼아 전체를 푸는 흐름이다. 우선 사람 수를 확 줄여 작은 원에서 시작해 보자.

01 작은 원에서 시작하다

일곱 명이 둥글게 앉아 있다고 하자. 1번이 2번을 제거한다. 다음으로 살아 있는 3번이 4번을 제거하고, 5번이 6번을 제거한다. 여기까지는 단순히 짝수 자리가 차례로 사라지는 모습이다. 그런데 이제부터가 미묘하다. 6번을 제거한 다음 차례는 7번인데, 7번의 다음 자리에는 이미 빈자리(8번은 없다)를 지나 1번이 살아 있다. 그래서 7번이 1번을 제거한다.

이제 살아 있는 사람은 3번, 5번, 7번뿐이고 차례는 3번이다. 3번이 다음 생존자인 5번을 제거한다. 남은 사람은 3번과 7번, 차례는 7번이다. 7번이 3번을 제거하면서 마지막에 7번만 남는다. 일곱 명의 원에서 살아남는 자리는 7번이다.

여기서 사람 수를 바꿔 가며 같은 과정을 손으로 따라가 보면 흥미로운 일이 벌어진다. 다섯 명이면 3번이, 여섯 명이면 5번이, 여덟 명이면 1번이 살아남는다. 답이 자리마다 제멋대로 튀는 듯하지만, 한 가지만은 한눈에 들어온다. 살아남는 자리는 언제나 홀수다.

02 패턴을 사냥하다

모르는 문제를 풀 때 가장 정직한 출발점은 직접 데이터를 모으는 것이다. 사람 수 n을 1부터 16까지 바꿔 가며, 살아남는 자리를 W(n)이라 적어 표로 늘어놓아 보자.

표를 왼쪽에서 오른쪽으로 훑으면 두 가지가 분명해진다. 첫째, 앞서 본 대로 W(n)은 모두 홀수다. 둘째, 값이 3, 5, 7, …처럼 2씩 꾸준히 커지다가, 어느 순간 갑자기 1로 되돌아간다. 그리고 그 되돌아가는 지점이 정확히 n = 1, 2, 4, 8, 16 — 즉 2의 거듭제곱일 때다.

03 2의 거듭제곱이라는 열쇠

여러 값 중 하나만 완전히 이해해도 나머지가 줄줄이 풀리는 경우가 있다. 여기서는 2의 거듭제곱이 바로 그 열쇠다. 사람 수가 16처럼 2의 거듭제곱일 때 왜 항상 1번이 살아남는지, 그 한 가지를 먼저 못 박아 보자.

열여섯 명이 둘러앉았다고 하자. 첫 바퀴를 돌면 짝수 자리 여덟 명이 모두 사라지고, 홀수 자리 여덟 명만 남는다. 중요한 것은 이 시점에 다시 1번 차례로 돌아온다는 사실이다. 남은 여덟 명을 1번부터 다시 번호 매기면, 처음과 똑같은 상황 — 2의 거듭제곱 인원에 1번 차례 — 이 재현된다. 한 바퀴를 더 돌면 또 절반인 네 명이 남고, 여전히 1번 차례다. 네 명이 두 명으로, 두 명이 한 명으로 줄어드는 동안 1번은 한 번도 제거되는 쪽에 놓이지 않는다. 인원이 깨끗이 반으로 접힐 때마다 1번은 늘 칼자루를 쥔 자리에 머무르며 끝까지 살아남는다.

04 하나의 공식으로 묶기

이제 두 가지 관찰을 합칠 차례다. 어떤 사람 수든 연이은 두 2의 거듭제곱 사이에 놓인다. 그래서 임의의 n을 다음과 같이 쓸 수 있다.

여기서 2^a은 n을 넘지 않는 가장 큰 2의 거듭제곱이고, ℓ은 그러고 남은 나머지다. 예컨대 n=13이면 2^a=8, ℓ=5다.

요령은 이렇다. 우선 제거를 정확히 ℓ번만 진행한다. 이렇게 제거되는 처음 ℓ명은 짝수 자리 2, 4, …, 2ℓ번이다. ℓ번의 제거가 끝나면 남은 인원은 n − ℓ = 2^a, 정확히 2의 거듭제곱이다. 그리고 다음 차례는 방금 제거된 2ℓ번 바로 다음 사람, 즉 2ℓ+1번이다.

그런데 앞 절에서 못 박아 두었다. 2의 거듭제곱 인원의 원에서는 그 순간 칼자루를 쥔 첫 주자가 살아남는다. 여기서 첫 주자가 바로 2ℓ+1번이므로, 결국 그 사람이 끝까지 남는다.

이 한 줄이 표 전체를 그대로 재현한다. 그리고 처음의 마흔한 명 문제도 바로 풀린다. 41 = 32 + 9이므로 살아남는 자리는 2 × 9 + 1 = 19번이다.

같은 결론은 점화식으로도 얻는다. W(1) = 1에서 출발해, 인원을 짝수·홀수로 나누어 보면 W(2n) = 2·W(n) − 1, W(2n+1) = 2·W(n) + 1이 성립한다. 작은 경우의 답을 두 배로 키워 가는 이 규칙을 따라가도 어김없이 2ℓ + 1에 도달한다.

05 이진법의 마법

사실 이 패턴은 처음부터 숨어 있었다. 사람 수를 평소처럼 십진수로 적었기 때문에 잘 보이지 않았을 뿐이다. 같은 숫자를 이진수로 적으면 답이 거의 한눈에 드러난다.

마흔하나를 이진수로 쓰면 101001이다(32 + 8 + 1). 생존 자리를 얻는 방법은 놀랄 만큼 기계적이다. 맨 앞 자리의 숫자를 떼어 맨 뒤로 보내기만 하면 된다. 이 한 칸 회전을 순환 왼쪽 이동이라고 부른다.

왜 이런 단순한 손장난이 통할까? 비밀은 앞서 세운 n = 2^a + ℓ 분해에 그대로 들어 있다. 이진수에서 맨 앞의 1은 바로 가장 큰 2의 거듭제곱 2^a를 뜻하고, 그 뒤에 남은 자릿수들이 모여 만드는 값이 정확히 ℓ이다. 그런데 답인 2ℓ + 1은 — ℓ의 모든 자릿수를 왼쪽으로 한 칸 밀고(2배) 맨 끝에 1을 채워 넣는(+1) 연산이다. 이것이 바로 맨 앞 1을 떼어 맨 뒤로 보내는 순환 이동과 같은 일이다.

요컨대 처음부터 사람 수를 이진수로 적어 두었다면, 답을 구하는 규칙이 훨씬 빨리 눈에 들어왔을 것이다. 십진수의 옷을 벗기자 문제의 골격이 그대로 드러난 셈이다.

06역사 속의 진짜 문제

지금까지 푼 것은 "두 사람마다 한 명씩" 건너뛰는 깔끔한 교과서판이었다. 답은 위치 19로 떨어졌다. 그런데 이 수수께끼가 태어난 본래 이야기에서는 규칙이 조금 달랐고, 그래서 답도 달라진다.

문제의 이름은 1세기의 유대인 역사가이자 지휘관이었던 요세푸스(본명 요세프 벤 마티아스, Joseph ben Matthias, 약 37~100년)에게서 왔다. 제1차 유대-로마 전쟁이 한창이던 서기 67년, 그는 갈릴리의 요새 도시 요타파타(Yotapata, 오늘날의 요드파트)를 지키다 로마군에게 포위당했다. 로마군을 이끈 사령관은 훗날 황제에 오르는 베스파시아누스(Vespasianus)였고, 포위는 47일간 이어졌다. 도시가 함락되자 요세푸스는 마흔 명 남짓한 동료와 함께 동굴에 숨었다. 모두 합해 마흔한 명. 사로잡히느니 죽음을 택하기로 한 그들은 한 가지 약속을 정한다.

건너뛰는 간격이 둘에서 셋으로 바뀌면, 앞 장에서 쌓아 올린 우아한 이진법 공식은 더 이상 그대로 통하지 않는다. 짝수가 한 바퀴에 모두 사라지던 규칙도, 2의 거듭제곱에서 답이 1이 되던 규칙도 무너진다. 마흔한 명이 세 칸 간격으로 줄어드는 과정을 차례로 따라가 보면, 끝까지 남는 자리는 19가 아니라 31이다. 그리고 만약 마지막 직전, 곧 두 사람이 남는 순간을 본다면 그 두 자리는 16번과 31번이다.

여기서 잠깐 짚어 둘 것이 있다. "요세푸스가 자기 자리를 미리 계산해 살아남았다"는 설정은 이야기를 매력적으로 만드는 장치이지만, 그가 직접 남긴 기록과는 결이 다르다. 요세푸스 자신의 저작 『유대 전쟁사』에서 그 동굴의 마지막 장면은 제비뽑기로 순서를 정했다고 적혀 있다. 즉 정교한 좌석 계산이 아니라 운에 가까운 추첨이었다. 끝까지 남은 그는 동료 한 사람과 함께 죽음을 멈추고 로마군에 항복했다 — 우연이었는지 계산이었는지, 본인은 신의 섭리로 돌렸다. 좌석을 꿰뚫어 본 수학자의 일화는 후대에 이 사건이 수학 문제로 다듬어지며 덧입혀진 옷에 가깝다.

이 일화가 본격적인 수학 문제로 처음 정리된 것은 17세기 초, 한 프랑스 수학자가 "마흔한 명, 세 칸 간격"이라는 구체적 설정을 퍼즐로 제시하면서였다. 이후 18세기에 이르러 한 수학자가 사람 수와 간격이 임의의 값일 때 답을 구하는 일반 점화식을 세웠다. 동굴 속의 절박한 약속이, 세기를 건너 누구나 풀 수 있는 깔끔한 수학 문제로 자리를 옮긴 것이다.

07간격이 바뀌면, 그리고 그 너머

본래 문제가 "세 칸 간격"이었듯, 건너뛰는 간격은 얼마든지 달라질 수 있다. 사람이 n명이고 간격이 k일 때 마지막 생존자의 자리를 구하는 일반 공식도 알려져 있다. 한 명만 있을 때는 그가 곧 생존자이고, 사람이 한 명 늘 때마다 답이 일정하게 밀려나는 점화식으로 정리된다.

이 점화식의 속뜻은 단순하다. 사람이 한 명 줄어든 더 작은 원에서 답을 이미 안다면, 사람을 한 명 더 붙이고 첫 번째 희생자만큼 출발점을 k칸 돌려 주면 한 단계 큰 원의 답이 된다는 것이다. 간격 k가 2인 특수한 경우에는 이 점화식이 앞 장의 이진법 마법으로 깔끔하게 압축되지만, k가 3 이상이면 그런 손쉬운 지름길은 사라지고 점화식을 한 단계씩 밟아 가는 편이 정확하다.

같은 구조는 수학 바깥에서도 모습을 드러낸다. 여럿이 둘러서서 구호에 맞춰 한 명씩 빠지는 술래 정하기 놀이, 정해진 간격으로 차례를 지워 나가는 각종 탈락식 게임이 모두 이 문제의 변형이다. 컴퓨터 과학에서는 원형으로 이어진 자료를 일정 간격으로 순회하며 처리하는 상황을 분석하는 도구로도 쓰인다. 동굴 속의 한 장면에서 출발한 물음이, 놀이판과 알고리즘으로까지 가지를 뻗은 셈이다.

08문제를 푸는 방법, 그 자체

이 문제가 오래 사랑받는 이유는 답이 19라서가 아니다. 답을 모르는 문제 앞에서 무엇을 해야 하는지를, 그 과정 자체가 또렷이 보여 주기 때문이다.

출발점은 거창한 통찰이 아니라 손을 더럽히는 일이었다. 사람 수를 하나씩 바꿔 가며 직접 원을 그리고 누가 남는지 적어 내려가는 것. 그렇게 표가 쌓이자 비로소 패턴이 떠올랐다 — 답은 늘 홀수더라는 것, 그리고 사람 수가 2의 거듭제곱일 때마다 답이 1로 돌아오더라는 것. 데이터를 모으지 않았다면 결코 보이지 않았을 규칙이다.

다음은 가장 또렷한 한 가지를 붙잡아 끝까지 증명하는 단계였다. 2의 거듭제곱에서 답이 왜 반드시 1인지를 — 한 바퀴마다 짝수가 사라지며 사람 수가 정확히 절반으로 줄고 차례는 처음으로 돌아온다는 사실로 — 확실히 매듭짓자, 나머지 모든 답이 그 닻에 매여 풀려 나왔다. 어중간하게 여러 갈래를 넘보기보다 확실한 하나를 깊이 파고드는 편이 전체를 여는 열쇠가 된 것이다.

마지막은 그 발판을 딛고 일반 법칙으로 건너뛰는 일이었다. 임의의 사람 수를 2^a + ℓ로 쪼개니, 이미 증명해 둔 2의 거듭제곱 결과가 그대로 살아나 답이 2ℓ + 1임이 드러났다. 데이터를 모으고, 패턴을 찾고, 가장 단단한 한 점을 증명하고, 거기서 전체로 나아간다 — 답이 주어지지 않은 문제 앞에서 길을 내는 이 순서는, 마흔한 명의 원을 한참 벗어나는 곳에서도 똑같이 통한다.