구체 수학 - #1.3 요세푸스 문제

이번 절은 요세푸스 문제에 대한 내용이다.

문제 : 1부터 n까지의 번호가 매겨진 n명이 사람이 원을 형성해서, 한 사람이 남을 때까지 두 번째 사람이 죽는데, 마지막에 남는 사람은 누구인지를 구하는 것이다.

 

단순히 본다면 짝수일 때의 해는 n/2일 거라고 추측할 수 있는데

실제로 n이 4 거나 6일 때는 그렇지가 않다.

 

n이 1부터 6까지의 해를 구해보면 : 1, 1, 3, 1, 3, 5로 모두 홀수이다.

그 이유는 짝수 번호들은 첫 바퀴에서 모두 처형되기 때문이다. 

 

2n에 대한 해와 2n+1에 대한 해를 구하면 점화식을 구할 수 있다.

 

책에서 소개하는 방식을 레퍼토리 법이라고 하며 이는

- 우선 알고 있는 해에 대한 일반적인 매개변수들의 설정을 구함.

- 우리가 풀 수 있는 특별한 경우에 대한 레퍼토리가 마련됨

- 특별한 경우들을 결합해서 일반적인 경우를 얻음