개요

이 문서는 [[CONCRETE-MATH]]책의 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 = n \; mod \; 2^m$ 이기 때문에, $n$ 의 제일 앞자리를 0 으로 바꾼 값이 $l$ 이다.
- 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 이니까, 를 사용해 시도해보면 될 것 같다.
- 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}$ .

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

01.RECURRENT PROBLEMS

개요

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