요세푸스 문제의 정의 (Josephus Problem)

요세푸스 문제의 정의 (Josephus Problem)

 

n 명의 사람이 삥 둘러앉아있고 매번 k번째 사람을 처형 할 때 마지막에 살아남는 사람 구하기.

 

예를들어 n = 5, k = 3 이라고 하면

 

step1: 1, 2, 3, 4, 5 (3번 처형)
step1: 4, 5, 1, 2    (1번 처형)
step1: 2, 4, 5       (5번 처형)
step1: 2, 4,         (2번 처형)
step1: 4             (4번 살아남음)

 

결국 4번이 살아남는다..

 

y(n)을 n 명이 주어졌을 때 살아남는 사람의 번호라고 정하자.

그러면 y(n)은 다음과 같은 수열로 주어진다.

-----------------------------------------------------------------------
1  2  3  4  5  6  7  8  9 10 11 12  13 14 15 16 17  18  19  20  21 22

-----------------------------------------------------------------------
1, 2, 2, 1, 4, 1, 4, 7, 1, 4, 7, 10, 13, 2,  5, 8, 11, 14, 17, 20, 2,  5,
-----------------------------------------------------------------------

위의 수열로 부터 다음 관계를 알수 있다.

    [0] 정의에 의해서 y(1)==1 이다.
    [1] 만약 y(i)==i 이면 y(i+1)==2 가 된다.
    [2] 만약 y(i)==i-1 이면 y(i+1)==1 이 된다.
    [3] 위의 1, 2 경우가 아니면 y(i+1)==y(i)+3 이 된다.