요세푸스 문제(Josephus problem)

요세푸스 문제

유대-로마 전쟁에서 플라비우스 요세푸스는 병사 40명과 함께 로마군에게 포위됐습니다. 포위된 요세푸스는 병사들과 함께 로마군에게 죽느니 우리들의 손으로 목숨을 끊자는 결심을 합니다. 이들은 원형으로 선 뒤 시계방향으로 자신의 옆사람을 죽여주기로 했습니다. 요세푸스는 마지막에 홀로 살아남아 스스로 목숨을 끊지 않고 로마군에 항복했습니다.

만약 요세푸스가 처음부터 살고 싶었다면 어디에 서야 마지막에 살아남을 수 있을까요? 이 질문이 요세푸스 문제입니다.

원형 리스트를 순회하며 특정 조건으로 요소를 하나씩 제거했을 때 제거되는 순서를 `요세푸스 순열(Josephus permutation)`, 마지막에 남는 요소를 알아내는 문제를 `요세푸스 문제(Josephus problem)`라고 합니다.

출처: https://www.youtube.com/watch?v=uCsD3ZGzMgE

 

해설

n명의 사람이 원형으로 서 1번부터 옆사람을 죽였을 때 가장 마지막에 남는 사람의 번호를 $W(n)$이라고 합시다. 다른 말로 하면 크기가 n인 요세푸스 문제의 답을 $W(n)$입니다. n이 1부터 20일 때 $W(n)$을 계산해 보면 다음과 같습니다.

W(n)

규칙이 보이시나요? 우선 $W(n)$의 값은 모두 홀수 입니다. 그리고 어떤 주기를 가지고 1부터 커지는 것을 반복하죠. 1만 표시해서 주기를 파악해 봅시다.

W의 주기성

$W(1)=1$이고 $W(2^k)=W(2^{k-1})$이 성립합니다. 따라서 n이 2의 제곱수일 때 W는 항상 1입니다.

$$W(1)=1,\quad W(2^k)=W(2^{k-1})\\[0.75em]\therefore\quad\text{if}\quad n=2^k\quad\text{then}\quad W(n)=1$$

 

$2^k<n<2^{k+1}$일때는 어떻게 알 수 있을까요?

$n=2^k+l$ 이라 해봅시다. 이때 위 조건에 따라 l의 범위는 $0< l<2^k$입니다.

요세푸스 문제는 n-1명을 죽이고 1명이 마지막에 살아남습니다. 먼저 l명을 죽이고 시작해도 결과는 같습니다. $l < n$이니 한 바퀴를 돌지 못하고 l명을 죽일 수 있습니다. l명이 죽고 나면 남은 $2^k$명에 대해서 요세푸스 문제를 푸는 것이니 처음 죽이기 시작한 사람이 살아남습니다. 따라서 l명을 죽이고 난 후 처음 죽이는 사람이 문제의 답이 됩니다.

l명을 죽이고 나서 처음 죽이는 사람은 $2l+1$번째 사람입니다. 

이를 위 식과 합치면 $W(2^k+l)=2l+1\quad(l=0,1,2,3,\dots)$입니다.

 

이를 이진법으로도 해석할 수 있습니다. 

n에서 가장 큰 2의 제곱수($2^k$)를 빼고 그 수($l$)에 2를 곱한 뒤 1을 더하는 것은 n을 이진수로 변환한 뒤 가장 앞 1을 제거하고 오른쪽에 1을 쉬프트 하는 것과 같습니다.