구체수학 01.재귀적인 문제들.03.요세푸스 문제

일러두기
1.3 요세푸스 문제(THE JOSEPHUS PROBLEM)
Links

일러두기

이 문서는 (책) CONCRETE MATHEMATICS(구체수학)책의 1장을 공부하며 메모한 것입니다.
이 문서는 메모일 뿐이니 자세한 내용은 교재를 참고해야 합니다.

1.3 요세푸스 문제(THE JOSEPHUS PROBLEM)

1세기의 역사가 플라비우스 요세푸스(Flavius Josephus)의 이름을 딴 문제를 변형한 문제.

제 1차 유대-로마 전쟁 중, 41명의 유대인 반역자들을 한 동굴에 모아놓았다.
반역자들은 갇혀있기 싫어서 자살을 하기로 결심하였다.
자살하는 방식은 다음과 같다.
- 둥글에 원을 그리고 앉는다.
- 원을 따라 두 번째 사람을 죽인다.
- 모두가 죽을 때까지 이를 반복한다.
그런데 두 사람(요세푸스와 그의 친구)은 죽고 싶지 않았다.

요세푸스와 친구는 원의 어느 위치에 있어야 살아남을 수 있을까?

최초에 n명이 원에 앉아 있을 때, 마지막에 살아남는 사람의 번호를 J(n)이라 하자.

그렇다면 위의 문제는 임의의 n에 대하여 J(n)의 값을 구하는 문제로도 볼 수 있다.

값을 미리 계산할 수 있다면, 살아남는 자리를 차지하여 죽지 않을 수 있다.

작은 사례부터 생각하자

n = 10 인 경우부터 생각해보자.

1부터 세어나가며 죽인다고 할 때 죽이는 순서는 2, 4, 6, 8, 10, 3, 7, 1, 9 이다.
따라서, J(10) = 5

추측 : J(10) = 5 이니까, $J(n) = { n \over 2 }$ 이 아닐까?

n이 작을 때 n과 J(n)과의 관계를 간단히 표로 정리해 보자.

n	J(n)	죽는 순서
1	1
2	1	2
3	3	2, 1
4	1	2, 4, 3
5	3	2, 4, 1, 5
6	5	2, 4, 6, 3, 1

곰곰히 살펴보면 다음과 같은 사실을 알 수 있다.

J(3) = 3이고, J(4) = 1 이므로 위의 추측은 틀렸다.
2, 4, 6... 과 같이 첫 루프에서는 짝수 번호가 전부 죽는다는 것을 알 수 있다.
따라서 J(n)은 항상 홀수이다.
n이 짝수이면, 첫 루프에서 짝수가 전부 죽고 인원수가 절반이 된다.
- 즉 시작 인원 수가 2n인 경우, 첫 루프가 끝난 후의 인원 수는 n이 된다.

n이 짝수인 경우

시작 인원 수가 2n인 경우가 쉬워보이니 이것부터 생각해보자.

1, 2, 3, 4... 가 1, 3, 5, 7... 이 된 셈이므로, 각 번호에 2를 곱하고 1을 뺀 것과 똑같은 모양이 되었다.

그렇다면 다음과 같이 표현할 수 있을 것이다.

$J(2n) = 2J(n) - 1, \quad for \; n \ge 1$

이제 J(10)의 값이 5 라는 것을 알고 있기 때문에 J(20)의 값도 구할 수 있게 되었다.

$\begin{align} J(20) & = 2J(10) - 1 \\ & = 2 \times 5 - 1 \\ & = 9 \\ \end{align}$

n이 홀수인 경우

n이 홀수인 경우는 어떻게 될까?

사람의 수가 2n + 1만큼 있다고 가정하자.
일단 첫 루프에서는 2, 4, 6, 8, ... 2n 과 같이 모든 짝수 번호가 죽는다.
그리고 마지막 2n + 1 번째 사람을 건너뛰게 되므로, 두 번째 루프에서는 1 이 가장 먼저 죽는다.

아무래도 두 번째 루프가 시작되고 1이 죽고 난 다음까지를 첫 번째 루프로 생각하는 쪽이 쉬울 것 같다.

그렇다면 새로 정의한 첫 번째 루프가 끝난 직후는 다음과 같을 것이다.

1, 2, 3, 4... 가 3, 5, 7, 9... 가 된 셈이므로, 각 번호에 2를 곱하고 1을 더한 것과 같은 모양이 되었다.

그러므로, 짝수인 경우와 비슷하게 식을 표현할 수 있다.

$J(2n+1) = 2J(n) + 1, \quad for \; n \ge 1$

점화식

위에서 얻어낸 식을 토대로 다음과 같은 점화식을 만들 수 있다.

$\begin{array}{ll} J(1) & = 1; \\ J(2n) & = 2J(n) - 1, \quad for \; n \ge 1 \\ J(2n + 1) & = 2J(n) + 1, \quad for \; n \ge 1 \\ \end{array}$

python으로 표현하면 다음과 같다.

def J(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2 * J( n/2 ) - 1
    else:
        return 2 * J( (n-1)/2 ) + 1

이 점화식은 루프를 돌 때마다 n이 거의 절반으로 줄어들게 되므로 효율적이다.

그러나 생사가 달린 문제이므로 더 빠르게 계산할 수 있는 닫힌 형태의 해를 구하고 싶다. (재귀를 들어내고 $O(1)$ 함수를 만들고 싶다)

해를 구해보자

점화식을 사용해 다음과 같은 표를 쉽게 찾아낼 수 있다.

## 다음 코드를 실행해도 볼 수 있다
for i in range(1, 17):
    print(i, J(i))

n	J(n)
1	1
2	1	2J(1) - 1
3	3	2J(2) + 1
4	1	2J(2) - 1
5	3	2J(2) + 1
6	5	2J(3) - 1
7	7	2J(3) + 1
8	1	2J(4) - 1
9	3	2J(4) + 1
10	5	2J(5) - 1
11	7	2J(5) + 1
12	9	2J(6) - 1
13	11	2J(6) + 1
14	13	2J(7) - 1
15	15	2J(7) + 1
16	1	2J(8) - 1

J(n)은 홀수이며, 1로 시작하고, 2씩 증가한다.
n이 2의 거듭제곱일 때마다 J(n)의 값은 1이 된다.

따라서 n을 $n = 2^m + l$ 로 생각할 수 있다. (단, $m \ge 0$ 이고, $0 \le l \lt 2^m$ )

그렇게 되면 각 n은 다음과 같이 대응된다.

n	$2^m + l$	n	$2^m + l$	n	$2^m + l$	n	$2^m + l$
1	$2^0 + 1$	2	$2^1 + 0$	4	$2^2 + 0$	8	$2^3 + 0$
		3	$2^1 + 1$	5	$2^2 + 1$	9	$2^3 + 1$
				6	$2^2 + 2$	10	$2^3 + 2$
				7	$2^2 + 3$	11	$2^3 + 3$
						12	$2^3 + 4$
						13	$2^3 + 5$
						14	$2^3 + 6$
						15	$2^3 + 7$

점화식이 다음과 같으므로,

$\begin{array}{ll} J(1) & = 1; \\ J(2n) & = 2J(n) - 1, \quad for \; n \ge 1 \\ J(2n + 1) & = 2J(n) + 1, \quad for \; n \ge 1 \\ \end{array}$

다음과 같은 식을 세울 수 있다.

$J(2^m + l) = 2l + 1, \quad for \; m \ge 0 \; and \; 0 \le l \lt 2^ m$

이제 수학적 귀납법으로 이 식을 증명하자.

짝수인 경우

$2^m + l = 2k$ 인 경우를 생각해 보자.
$l$ 은 홀수일 수 없으므로, 짝수이다.

$J(2k) = 2J(k) - 1$ 이고, $2^m + l = 2k$ 이므로, 다음과 같이 식을 꾸밀 수 있다.

$\begin{align} J(2^m + l) & = 2J(\frac{2^m + l}{2}) - 1 \\ & = 2J(2^{m - 1} + \frac{l}{2}) - 1 \\ \end{align}$

그런데 $J(2^m + l) = 2l + 1$ 이므로,

$J(2^{m - 1} + \frac{l}{2}) = \frac{2l}{2} + 1$ 이다.

따라서 다음과 같은 결과가 나온다.

$\begin{align} J(2^m + l) & = 2J(2^{m - 1} + \frac{l}{2}) - 1 \\ & = 2(\frac{2l}{2} + 1) - 1 \\ & = 2l + 1 \\ \end{align}$

이는 위에서 추측한 식과 맞아 떨어진다.

홀수인 경우

홀수인 경우는 책에 안 나오지만 해보도록 하자.

$2^m + l = 2k + 1$ 인 경우를 생각해 보자.
$l$ 은 짝수일 수 없으므로, 홀수이다.
$J(2k + 1) = 2J(k) + 1$ 이고,
$2^m + l = 2k + 1$ 이고,
$k = \frac{2^m + l - 1}{2}$ 이므로,

다음과 같이 식을 꾸밀 수 있다.

$\begin{align} J(2k + 1) & = 2J(k) + 1 \\ J(2^m + l) & = 2J(\frac{2^m + l - 1}{2}) + 1 \\ & = 2J(2^{m-1} + \frac{l - 1}{2}) + 1 \\ \end{align}$

그런데 $J(2^m + l) = 2l + 1$ 이므로,

$J(2^{m - 1} + \frac{l - 1}{2}) = (l - 1) + 1 = l$ 이다.

따라서 다음과 같은 결과가 나온다.

$\begin{align} J(2^m + l) & = 2J(2^{m-1} + \frac{l - 1}{2}) + 1 \\ & = 2l + 1 \\ \end{align}$

이 또한 위에서 추측한 식과 맞아 떨어진다.

2진법으로 풀면 쉽게 풀린다?

n을 다음과 같이 표현할 수 있을 것이다.

$n = b_m 2^m + b_{m-1} 2^{m - 1} + ... + b_1 2^1 + b_0 2^0$

위의 n을 다음과 같이 이진수 전개하는 것도 생각해 볼 수 있는 일이다.

$n = (b_m b_{m-1} ... b_{1} b_{0})_2$

단, 각 $b_i$ 는 0 또는 1 이다.
단, 제일 앞 비트인 $b_m$ 은 1 이다.

한편, $n = 2^m + l$ 이므로 다음과 같이 표현할 수 있다.

$n = (1 b_{m - 1} b_{m - 2} ... b_1 b_0)_2$
l=(0bm−1bm−2...b1b0)2
- $l = n \; mod \; 2^m$ 이기 때문에, $n$ 의 제일 앞자리를 0 으로 바꾼 값이 $l$ 이다.
2l=(bm−1bm−2...b1b00)2
- 2l은 l << 1 과 같으므로, 제일 오른쪽에 0 을 추가해주면 된다.
$2l + 1 = (b_{m - 1} b_{m - 2} ... b_1 b_0 1)_2$

$J(n) = 2l + 1$ 이므로 다음과 같이 정리할 수 있다.

$\begin{align} J(n) & = 2l + 1 \\ & = (b_{m - 1} b_{m - 2} ... b_1 b_0 1)_2 \\ & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ \end{align}$

그런데 $n = (1 b_{m - 1} b_{m - 2} ... b_1 b_0)_2$ 이므로, 다음이 증명된다.

$\begin{align} J(n) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ J((b_m b_{m - 1} b_{m - 2} ... b_1 b_0)_2) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ \end{align}$

즉, n을 왼쪽으로 1회 비트 순환시키면 J(n)이 나온다.

단, 가장 왼쪽 비트가 0 일 경우엔 가장 왼쪽 비트를 삭제해 주어서, 제일 앞 비트를 1로 유지해 주어야 한다.

아름답다.

놀라움을 음미하기 위해 몇 가지 경우를 생각해 보자.

n = 13 인 경우
- 13 = 8 + 4 + 1 이므로, 1101(2) 이다.
- 이를 회전시키면 1011(2) = 11 이 나온다.
n = 100 인 경우
- 100 = 64 + 32 + 4 이므로, 1100100(2) 이다.
- 이를 회전시키면 1001001(2) = 64 + 8 + 1 = 73 이다.
- $100 = 2^6 + 36$ 이므로, $l = 36$ 이고, $2l + 1$ 에 의해 73이 맞다.

최초의 추측 J(n) = n/2 를 생각해보자

즉 함수 J(n)은 다음과 같은 작업을 한다.

n의 제일 왼쪽에 있는 1을 가장 오른쪽으로 옮긴다.
1을 옮긴 결과, 제일 왼쪽에 0 또는 00...이 있다면 삭제한다.
- 결과는 항상 1로 시작해야 하기 때문이다.

문제는 어느 정도 풀었지만, 함수 J(n)을 재귀시키는 경우를 생각해보자.

함수 J(J(J(...J(n)...))) 과 같이 재귀시키면, 충분히 많이 돌릴 경우 0은 전부 사라지고 1만 남게 될 것이다.

예를 들어 101101101101011(2)를 충분히 회전시키면 0이 전부 삭제되어 1111111111(2) = 1023이 남게 될 것이다.

이제 최초의 추측 $J(n) = \frac{n}{2}$ 에 대해 생각해보자.
이 추측은 틀린 가설이었다.
- 이제는 해가 있으니 해를 사용하면 이 추측이 참인 경우를 판정 가능하다.

$\begin{align} J(n) & = \frac{n}{2} \\ J(2^m + l) & = \frac{2^m + l}{2} \\ 2l + 1 & = \frac{2^m + l}{2} \\ 4l + 2 & = 2^m + l \\ 3l & = 2^m - 2 \\ l & = \frac{2^m - 2}{3} \\ \end{align}$

즉, $l = \frac{2^m - 2}{3}$ 이 정수인 경우에 한하여 추측은 들어맞게 된다.

다음은 $J(n) = \frac{n}{2}$ 를 만족시키는 몇몇 경우이다.

m	$l$	$n = 2^m + l$	$J(n) = 2l + 1 = \frac{n}{2}$	n(이진수)
1	0	2	1	10
3	2	10	5	1010
5	10	42	21	101010
7	42	170	85	10101010

이진수를 보면 흥미로운 패턴을 보인다.

일반화 : 레퍼토리법(repertoire method)

f(n) 으로 일반화해보자

이제 J(n)과 비슷한 함수를 만나게 되었을 때에도 쉽게 풀 수 있도록 J(n)함수를 일반화해보자.

J(n)의 점화식은 다음과 같았다.

$\begin{array}{ll} J(1) & = 1; \\ J(2n) & = 2J(n) - 1, \quad for \; n \ge 1 \\ J(2n + 1) & = 2J(n) + 1, \quad for \; n \ge 1 \\ \end{array}$

이를 일반화하기 위해 상수 $\alpha, \beta, \gamma$ 를 도입한 함수 f(n)을 만들어 보자.

$\begin{array}{ll} f(1) & = \alpha ; \\ f(2n) & = 2f(n) + \beta, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \gamma, \quad for \; n \ge 1 \\ \end{array}$

n 이 작은 경우에 대한 테이블도 만들어 보자.

$\begin{array}{l|l} n & f(n) \\ \hline 1 & \alpha \\ \hline 2 & 2 \alpha + 1 \beta \\ 3 & 2 \alpha + \qquad 1 \gamma \\ \hline 4 & 4 \alpha + 3 \beta \\ 5 & 4 \alpha + 2 \beta + 1 \gamma \\ 6 & 4 \alpha + 1 \beta + 2 \gamma \\ 7 & 4 \alpha + \qquad 3 \gamma \\ \hline 8 & 8 \alpha + 7 \beta \\ 9 & 8 \alpha + 6 \beta + 1 \gamma \\ \end{array}$

$\alpha$ 의 계수는 n 미만의 가장 큰 2의 거듭제곱으로 보인다.
$\beta$ 의 계수는 1씩 감소해, 0까지 가는 것 같다.
$\gamma$ 의 계수는 0에서 출발하여 1씩 증가하는 것 같다.

발견한 특징들을 사용해 다음과 같이 표현해보자.

$\begin{align} n & = 2^m + l \quad \text{(이전과 같다)} \\ f(n) & = A(n)\alpha + B(n)\beta + C(n)\gamma \\ \end{align}$

그리고 다음과 같은 추측을 할 수 있다.

식 1.14

$\begin{align} A(n) & = 2^m \\ B(n) & = 2^m - 1 - l \\ C(n) & = l \\ \end{align}$

수학적 귀납법으로 이를 증명하는 것은 생략하자. (별로 배울 것이 없다고 한다)

대신, $\alpha = 1, \beta = 0, \gamma = 0$ 인 경우에 한해 생각해보자.

$\begin{align} A(1) & = 1; \\ A(2n) & = 2A(n), \quad for \; n \ge 1 \\ A(2n + 1) & = 2A(n), \quad for \; n \ge 1 \\ \end{align}$

그리고 다음의 사실도 알 수 있다.

$\begin{align} A(n) & = 2^m \\ A(2^m + l) & = 2^m \\ \end{align}$

점화식에 f(n)을 적용해보자

$\begin{array}{ll} f(1) & = \alpha ; \\ f(2n) & = 2f(n) + \beta, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \gamma, \quad for \; n \ge 1 \\ \end{array}$

f(n) = 1 인 경우

위의 점화식에 f(n) = 1을 대입해 보자.

첫번째 식은 다음과 같이 정리된다.

$\begin{align} f(1) & = \alpha \\ 1 & = \alpha \\ \end{align}$

두번째 식은 다음과 같다.
- f(n)은 n이 무엇이건 간에 1을 리턴하므로, f(2n)도 1 이라는 점을 활용한다.

$\begin{align} f(2n) & = 2f(n) + \beta \\ 1 & = 2 \cdot 1 + \beta \\ -1 & = \beta \\ \end{align}$

세번째 식은 다음과 같다.

$\begin{array}{rl} f(2n + 1) & = 2f(n) + \gamma \\ 1 & = 2 \cdot 1 + \gamma \\ -1 & = \gamma \\ \end{array}$

따라서, $\alpha = 1, \; \beta = -1, \; \gamma = -1$ 이다.

이를 $f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$ 에 적용해 보면, 다음과 같이 된다.

$\begin{align} f(n) & = A(n) - B(n) - C(n) \\ & = 1 \\ \end{align}$

f(n) = n 인 경우

위에서 한 것과 비슷하게 f(n) = n 인 경우를 생각해보자.

첫번째 점화식은 다음과 같이 정리된다.

$\begin{align} f(1) & = \alpha \\ 1 & = \alpha \\ \end{align}$

두번째 식은 다음과 같다.

$\begin{align} f(2n) & = 2f(n) + \beta \\ 2n & = 2 \cdot n + \beta \\ 0 & = \beta \\ \end{align}$

세번째 식은 다음과 같다.

$\begin{array}{rl} f(2n + 1) & = 2f(n) + \gamma \\ 2n + 1 & = 2 \cdot n + \gamma \\ 1 & = \gamma \\ \end{array}$

따라서, $\alpha = 1, \; \beta = 0, \; \gamma = 1$ 이다.

이를 $f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$ 에 적용해 보면, 다음과 같이 된다.

$\begin{align} f(n) & = A(n) + C(n) \\ & = n \\ \end{align}$

종합

이것으로 증명은 끝났다.

결과를 종합하면 다음과 같다!

$\begin{align} A(n) & = 2^m, \quad where \; n = 2^m + l \; and \; 0 \le l \lt 2^m; \\ A(n) - B(n) - C(n) & = 1; \\ A(n) + C(n) & = n; \\ \end{align}$

이러한 방식으로 점화식을 풀어내는 것을 레퍼토리법(repertoire method)이라 부른다.

레퍼토리법에서는 우선 알고 있는 해에 대한 일반적인 매개변수들의 설정들을 구한다. 그러면 우리가 풀 수 있는 특별한 경우들에 대한 레퍼토리가 마련된다. 그런 다음에는 특별한 경우들을 결합해서 일반적인 경우를 얻는다. 이를 위해서는 독립 매개변수 개수(지금 예에서는 $\alpha, \, \beta, \, \gamma$ 세 개)만큼의 개별적인 특수해들이 필요하다.

일반식을 얻어낸 김에 식1.14를 확인해보자.

식 1.14는 다음과 같은 추측이었다.

$\begin{align} A(n) & = 2^m \\ B(n) & = 2^m - 1 - l \\ C(n) & = l \\ \end{align}$

A(n)은 자명하므로 따로 확인할 필요가 없다.
B(n)은 다음과 같이 볼 수 있다.

$\begin{align} A(n) - B(n) - C(n) & = 1 \\ - A(n) + B(n) + C(n) & = -1 \\ B(n) & = A(n) - C(n) - 1 \\ 2^m -1 -l & = A(n) - C(n) - 1 \\ 2^m -l & = A(n) - C(n) \\ 2^m -l & = 2^m - l \\ \end{align}$

C(n)은 다음과 같이 볼 수 있다.

$\begin{align} A(n) + C(n) & = n; \\ A(n) + l & = n \\ 2^m + l & = n \\ \end{align}$

일반화된 점화식에 2진법 방법 적용하기

2진법으로 풀면 쉽게 풀린다에서 구했던 2진법 J 점화식을 다시 떠올려 보자.

$b_m = 1$ 일 때,

$\begin{align} J(n) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ J((b_m b_{m - 1} b_{m - 2} ... b_1 b_0)_2) & = (b_{m - 1} b_{m - 2} ... b_1 b_0 b_m)_2 \\ \end{align}$

2진법 방식의 일반화를 위해 다음과 같이 정의하자.

$\beta_0 = \beta$
$\beta_1 = \gamma$

점화식은 다음과 같았다.

$\begin{array}{ll} f(1) & = \alpha ; \\ f(2n) & = 2f(n) + \beta, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \gamma, \quad for \; n \ge 1 \\ \end{array}$

여기에 $\beta_0 = \beta$ 과 $\beta_1 = \gamma$ 를 적용하면 다음과 같이 된다.

$\begin{array}{ll} f(1) & = \alpha ; \\ f(2n + 0) & = 2f(n) + \beta_0, \quad for \; n \ge 1 \\ f(2n + 1) & = 2f(n) + \beta_1, \quad for \; n \ge 1 \\ \end{array}$

두번째와 세번째 점화식은 다음과 같이 하나로 합칠 수 있다.

$f(2n + j) = 2f(n) + \beta_j, \quad for \; j = 0,1 \; and \; n \ge 1\\$

이 점화식을 2진법으로 전개해 보면 다음과 같다.

$\begin{align} f((b_m b_{m-1} ... b_1 b_0)_2) & = 2f((b_m b_{m-1} ... b_3 b_2 b_1)_2) + \beta_{b_0} \\ & = 4f((b_m b_{m-1} ... b_3 b_2)_2) + \beta_{b_1} + \beta_{b_0} \\ & = 8f((b_m b_{m-1} ... b_3)_2) + \beta_{b_2} + \beta_{b_1} + \beta_{b_0} \\ & ... \\ & = 2^m f((b_m)_2) + 2^{m - 1} \beta_{b_{m-1}} + ... + 2\beta_{b_1} + \beta{b_0} \\ & = 2^m \alpha + 2^{m - 1} \beta_{b_{m-1}} + ... + 2 \beta_{b_1} + \beta_{b_0} \\ & = (\alpha \beta_{b_{m-1}} ... \beta_{b_1} \beta_{b_0})_2 \\ \end{align}$

$\alpha$ 가 제일 앞에 있는 이유는, 제일 앞의 $b_m = 1 = \alpha$ 이기 때문이다.

그리고 한참 위에서 작성했던 표를 (새로운 관점으로) 다음과 같이 작성할 수 있다.

$\begin{array}{l|r} n & f(n) \\ \hline 1 & \alpha \\ \hline 2 & 2 \alpha + 1 \beta \\ 3 & 2 \alpha + 1 \gamma \\ \hline 4 & 4 \alpha + 2 \beta + 1 \beta \\ 5 & 4 \alpha + 2 \beta + 1 \gamma \\ 6 & 4 \alpha + 2 \gamma + 1 \beta \\ 7 & 4 \alpha + 2 \gamma + 1 \gamma \\ 8 & 8 \alpha + 4 \beta + 2 \beta + 1 \beta \\ 9 & 8 \alpha + 4 \beta + 2 \beta + 1 \gamma \\ \end{array}$

$n = 100 = (1100100)_2$ 인 경우를 생각해 보자.

$\beta_0 = \beta$
$\beta_1 = \gamma$

일단 위와 같이 2진법으로 표기된 $0 \Rightarrow \beta \,$ 이고, 2진법으로 표기된 $1 \Rightarrow \gamma \,$ 이므로

요세푸스 값 $\alpha = 1, \; \beta = -1, \; \gamma = 1$ 을 적용해보면 다음과 같다.

$\alpha$ 와 $\gamma$ 가 공통적으로 이진법 1을 의미하고, $\beta$ 가 이진법 0을 의미하므로, 이진법 n을 십진법으로 바꿀 때 이진법 0이 있는 곳에 $\beta$ 값인 -1을 곱해주면 된다.

$\begin{array}{r} n & = & ( \; 1 & 1 & 0 & 0 & 1 & 0 & 0 & )_2 & = 100 \\ \hline f(n) & = & ( \; 1 & 1 & -1 & -1 & 1 & -1 & -1 & )_2 & \\ & = & +64 & +32 & -16 & -8 & +4 & -2 & -1 & & = 74 \\ \end{array}$

어떻게 이 방법이 비트 순환과 똑같은 결과를 내는 것일까?

비트가 3개인 모든 경우를 살펴보자.

111 : 7인 경우
110 : 6인 경우
101 : 5인 경우
100 : 4인 경우

7인 경우

7인 경우를 먼저 생각해보자.

$\begin{array}{r} n & = & ( \; 1 & 1 & 1 & )_2 & = 7 \\ \hline f(n) & = & ( \; 1 & 1 & 1 & )_2 & \\ & = & 4 & 2 & 1 & & = 7 \\ \end{array}$

7과 같이 비트가 1만 있는 경우는 0이 없으므로 빼는 숫자가 없어 값이 그대로 나온다.

비트 순환을 하나 마나 똑같은 결과이므로 비트 순환과 똑같다.

이는 7 외에도 3( $11_2$ ), 15( $1111_2$ ) 등등 $2^x - 1$ 형태인 모든 숫자에 해당될 것이다.

6인 경우

이번에는 6인 경우를 생각해보자.

$\begin{array}{r} n & = & ( \; 1 & 1 & 0 & )_2 & = 6 \\ \hline f(n) & = & ( \; 1 & 1 & -1 & )_2 & \\ & = & 4 & 2 & -1 & & = 5 \\ \end{array}$

110 에서 1 을 빼면 101 이 된다.
110 => 101이 되었으므로 좌측 비트 순환과 똑같다.

5인 경우

이번에는 5인 경우를 생각해보자.

$\begin{array}{r} n & = & ( \; 1 & 0 & 1 & )_2 & = 5 \\ \hline f(n) & = & ( \; 1 & -1 & 1 & )_2 & \\ & = & 4 & -2 & 1 & & = 3 \\ \end{array}$

101 에서 10 을 빼면 011 이 된다.
101 => 011이 되었으므로 좌측 비트 순환과 똑같다.

4인 경우

이번에는 4인 경우를 생각해보자.

$\begin{array}{r} n & = & ( \; 1 & 0 & 0 & )_2 & = 4 \\ \hline f(n) & = & ( \; 1 & -1 & -1 & )_2 & \\ & = & 4 & -2 & -1 & & = 1 \\ \end{array}$

100 에서 1 을 빼면 011 이 된다.
011 에서 10 을 빼면 001 이 된다.
100 => 001이 되었으므로 좌측 비트 순환과 똑같다.

일반화한 식을 좀 더 일반화해보자

위에서 알아낸 점화식은 다음과 같았다.

$\begin{array}{rll} f(1) & = \alpha, & \\ f(2n + j) & = 2f(n) + \beta_j, & for \; j = 0,1 \; and \; n \ge 1\\ \end{array}$

이를 다음과 같이 좀 더 일반화해볼 수 있을 것이다.

$\begin{array}{rll} f(j) & = \alpha_j, & for \; 1 \le j \lt d ; \\ f(dn + j) & = cf(n) + \beta_j, & for \; 0 \le j \lt d \; and \; n \ge 1\\ \end{array}\tag{1.17}$

d와 c를 보면 알 수 있겠지만, n은 d진법이고, f(n)은 c진법으로 생각하는 쪽이 계산이 편리하다.

$f((b_m b_{m - 1} ... b_1 b_0)_d) = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0} )_c$

f(19) 계산 예제

이제서야 1장의 마지막 예제를 이해할 수 있을 것 같다.

1장의 마지막 예제는 다음과 같은 점화식을 통해 f(19)를 계산하는 것이다.

$\begin{array}{rll} f(1) & = 34; \\ f(2) & = 5; \\ f(3n) & = 10f(n) + 76, & for \; n \ge 1; \\ f(3n + 1) & = 10f(n) - 2, & for \; n \ge 1; \\ f(3n + 2) & = 10f(n) + 8, & for \; n \ge 1; \\ \end{array}$

19는 3의 배수 + 1 이니까, f(3n+1)=10f(n)−2를 사용해 시도해보면 될 것 같다.
- 3n + 1을 보면, d = 3 이다.
- 10f(n) - 2를 보면, c = 10이다.
- 그리고 19는 18 + 1 이니까 3진법으로 201이다.

따라서 다음과 같이 전개할 수 있다.

$\begin{array}{rlrrrrll} n & = & ( \; 2 & 0 & 1 & )_3 & = 19 \\ \hline f(n) & = & ( \; \color{red}{5} & \color{red}{76} & \color{red}{-2} & )_3 & \\ & = & \color{red}{5} \cdot 10^2 & \color{red}{76} \cdot 10 & \color{red}{-2} & & = 500 + 760 - 2 \\ & & & & & & = 1258 \\ \end{array}$

위의 5, 76, -2 는 다음과 같이 얻어낸 것이다.

$f(2) = \color{red}{5}$ .
$f(3n + 0) = 10f(n) + \color{red}{76}$ 이므로, $\beta_0 = \color{red}{76}$ .
$f(3n + 1) = 10f(n) \color{red}{-2}$ 이므로, $\beta_1 = \color{red}{-2}$ .

일러두기

1.3 요세푸스 문제(THE JOSEPHUS PROBLEM)

작은 사례부터 생각하자

n이 짝수인 경우

n이 홀수인 경우

점화식

해를 구해보자

짝수인 경우

홀수인 경우

2진법으로 풀면 쉽게 풀린다?

최초의 추측 J(n) = n/2 를 생각해보자

일반화 : 레퍼토리법(repertoire method)

f(n) 으로 일반화해보자

식 1.14

점화식에 f(n)을 적용해보자

f(n) = 1 인 경우

f(n) = n 인 경우

종합

일반화된 점화식에 2진법 방법 적용하기

어떻게 이 방법이 비트 순환과 똑같은 결과를 내는 것일까?

7인 경우

6인 경우

5인 경우

4인 경우

일반화한 식을 좀 더 일반화해보자

f(19) 계산 예제

Links