플라비우스 요세푸스(Flavius Josephus; 37-100)는 1세기의 유대인출신 정치가이자 역사가이다. 그는 66년에 발발한 유다이아 전쟁에서 유대군을 지휘해서 갈릴리 지역을 지켰다. 전쟁은 유대인들에게 그리 유리하게 진행되지 않아 그도 로마군에 의해 포위되어 67년, 다른 유대인들과 동굴 안에 갇히는 신세가 되었다. 포로가 되는 것이 죽음보다 싫었던 동료 유대인들은 특별한 규칙을 통해 순서대로 동료들의 목숨을 서로 끊어주기로 했다. 그 규칙은 다음과 같다:
원형으로 둘러앉아 순서를 매기기 시작한다. 순서를 매기기 시작한 사람에서 세 번째 순서에 있는 사람을 죽인다. 그리고나서 기존 순서를 유지하고 그 다음 사람부터 다시 순서를 매기기 시작해서 세 번째에 있는 사람을 또 죽인다. 생존자가 없을 때까지 이것을 반복한다.
자결하고 싶지 않았던 요세푸스는 규칙이 정해지자 마지막에 생존할 수 있는 번호를 재빨리 알아내고는 자신 포함 두 사람이 살아남았을 때 그를 설득하여 로마군에 투항하게 된다. 그는 이 일로 평생 변절자라는 오명을 안고 살았다. 역사서 <<유대전쟁사>>와 <<유대고대사>>를 남겼다.
여기서는 이것을 수학문제로 바꿔본다. 기본틀은 커누스의 “구체수학(Concrete Mathematics)”의 내용을 따른다.
위 그림과 같이 1번부터 번호를 적고 1번부터 숫자를 읽어가면서 짝수번째에 만나는 수를 제거해 나가기로 하자. 오른쪽 그림처럼 12까지 숫자가 적혀있다면 없어지는 숫자는 순서대로 2, 4, 6, 8, 10, 12, 3, 7, 11, 5, 1로 9번이 마지막으로 남게 된다.
$n$개의 번호를 적고 위 규칙에 따라 숫자를 지워나갈 때 마지막에 남는 수를 $a_n$이라 하자. 숫자를 하나 지울 때마다 전체 수의 개수가 하나씩 줄어들기 때문에 최후에 남는 수는 $n$에 따라 달라지기는 하더라도 뭔가 정해질 것이 자명하므로 이렇게 정의된 $a_n$은 수열이다.
우선, 짝수는 너무나도 당연하게 지워진다. 문제는 짝수가 모두 지워지고난 다음인데, 전체 숫자가 짝수개라면 처음 시작했던 숫자 1이 숫자를 지우면서 한 바퀴 돌아온 다음에도 살아남는다. 한편, 전체 숫자가 홀수개라면 처음 시작했던 1은 한 바퀴 돌아오는 순간 사라지게 된다. 그래서, 우리는 최후까지 남는 숫자 $a_n$을 구하기 위해 원형으로 적은 수가 짝수개일 때와 홀수개일 때로 구분해서 문제를 바라보기로 한다.
적혀있는 수가 짝수개일 때
편의상 $2n$개라 하자. 이 때의 숫자는 아래 그림의 왼쪽처럼 되었다가 규칙에 따라 숫자를 지우면서 한 바퀴 돌아오면 오른쪽 그림과 같은 상태가 된다.
오른쪽의 그림을 분석해 보면 전체 개수가 $n$개이며 지금부터도 똑같이 1부터 시작해서 차례대로 짝수번째 만날 숫자를 지워나가게 된다. 즉, 아래 두 문제는 숫자만 다르게 적혀있을 뿐, 같은 문제를 풀고 있는 셈이 된다.
더 좋은 것은, 같은 자리에 있는 왼쪽 수와 오른쪽 수 사이에는 $n \mapsto 2n-1$이라는 관계식도 성립한다. 왼쪽 문제의 답이 $a_n$이라는 사실과 이 관계식을 이용하면 오른쪽 문제의 답은 $2a_n -1$이다. 그러므로 우리는 다음과 같은 중요한 관계식을 얻는다. $$a_{2n} = 2a_n -1$$
적혀있는 수가 홀수개일 때
편의상 숫자가 $2n+1$개 있다고 하자. 이 때는 숫자가 어디까지 지워진 것을 한 바퀴 실행한 것으로 봐야 하는지가 문제인데, 이번에도 남아있는 수와 1부터 숫자가 순차적으로 적혀있는 모델을 비교할 것이므로 가장 작은 숫자부터 시작하는 시점을 한 바퀴로 봐야 좋은 관계식이 얻어진다. 따라서, 1까지 지워진 오른쪽 아래 그림의 상태가 한 바퀴를 돌아온 상태로 봐야 한다.
오른쪽의 그림을 분석해 보면 숫자가 $n$개이며 지금부터는 3부터 시작해서 차례대로 짝수번째 만나는 숫자를 지워나가게 된다. 즉, 짝수개 적혀있을 때처럼 아래 두 문제는 숫자만 다르게 적혀있을 뿐, 같은 문제를 풀고 있는 셈이 된다.
그리고, 이번에는 같은 자리에 있는 왼쪽 수와 오른쪽 수 사이에 $n \mapsto 2n+1$이라는 관계식이 성립한다. 왼쪽 문제의 답이 $a_n$이라는 사실과 두 그림 사이의 관계식을 이용하면 오른쪽 문제의 답은 $2a_n +1$이다. 그러므로 우리는 다음과 같은 중요한 관계식을 얻는다. $$a_{2n+1} = 2a_n +1$$
결론
따라서, 변형된 요세푸스 문제는 다음과 같은 관계식을 통해 해결할 수 있다. $$a_1 =1, \quad a_{2n} = 2a_n -1, \quad a_{2n+1} = 2a_n +1, \quad n=1, 2, 3, \cdots$$