요세푸스 문제
[image]
유대인 역사가 플라비우스 요세푸스가 겪은 경험을 바탕으로 만들어진 문제이다.
당시 예루살렘에서 살았던 요세푸스는 유대-로마 전쟁 때 유대군 장교로 참전했다가 동료 병사들, 자신을 포함해 총 41명과 함께 요타파타[1]에서 서기 70년에 황제가 될 베스파시아누스가 지휘하는 로마군에게 포위되었고, 동료들은 로마군의 손에 죽느니 스스로 죽겠다고 집단자살하기로 했다. 그러나 직접 자살하는 것이 어려웠는지, 그들은 서로 죽이기 위한 알고리즘을 세운다. 요세푸스를 따라온 동료들은 위의 그림과는 다르게 2명 살리고 한 명 죽이는 식으로 자살했다.[2] 그러나 요세푸스는 동료들의 뜻에 반대하고 살고 싶었고, 수학적 논리력을 발휘하여 끝까지 살기 위한 자리를 찾아서 결국 살아남아 베스파시아누스에게 항복했다.
위키피디아출처에 따르면 41개의 숫자 중 하나를 건너뛰는 형태로 없애고 만약 41을 넘어가게 되면 다시 가장 처음번호로 돌아가는 식을 반복해 마지막에 남은 숫자를 구하는 문제이다.
이와는 다르게 보다 일반적인 문제도 있는데, 1~n 까지의 총 n개의 숫자가 있고 처음에는 k를 없애고 그 다음에는 2k를 없애는 식으로 하다가 n을 넘어가게 되면 존재하는 숫자 중 가장 낮은 숫자로 되돌아가 이와 같은 형태를 반복하는 문제이다. 만약 다 세지 못한채 한바퀴를 돌게 되면 그 남은수는 누적된 채 계속 세개 된다. 남은 수를 1개 구하는 경우도 있고, k-1개 구하는 경우도 있으나 두 경우에 있어서 풀이의 차이는 거의 존재하지 않는다.
n 명을 원형으로 세워놓고 3번째마다 지울 때 마지막 남은 사람의 자리수 번호를 $$f(n)$$ 이라 하자
이제 $$f(n)$$ 과 $$f(n+1)$$ 사이의 관계를 찾아보자
$$n+1$$ 명을 원형으로 세워놓고 3번째 사람을 지우면 이제 n명만 남게 되고
4번째 사람부터 다시 시작하는 형태가 된다.
즉, 사람의 배열은.. $$4, 5, 6, 7, 8, 9, \cdots n, n+1, 1, 2$$ (3을 지워서 총 n명) 가 되고
처음 $$f(n)$$ 기준으로는 $$1, 2, 3, 4, 5, 6, \cdots n-3, n-2, n-1, n$$ 순서와 매핑이 된다.
(이 부분이 바로 점화식을 유도하는데 핵심적인 사고이다)
이때 $$n$$명중에 $$p$$번째가 가장 마지막까지 남는 자리라고 하면
즉, $$f(n)=p$$ 라 하자
위의 두 배열의 매핑관계를 보면..다음과 같이 점화식을 유도할 수 있다.
$$p = f(n) = n-1$$ 일때는 $$f(n+1) = 1)$$ $$\cdots$$ ㄱ
$$p = f(n) = n$$ 일때는 $$f(n+1) = 2$$ $$\cdots$$ㄴ
$$p = f(n) = 1, 2, \cdots n-2$$ 일때는 $$f(n+1) = f(n) + 3$$ $$\cdots$$ㄷ
$$f(2)=2$$
ㄴ에 의해 $$f(3)=3$$
ㄱ에 의해 $$f(4)=1$$
ㄷ에 의해 $$f(5)=4$$
ㄱ에 의해 $$f(6)=1$$
ㄷ에 의해 $$f(7)=4$$
ㄷ에 의해 $$f(8)=7$$
ㄱ에 의해 $$f(9)=1$$
즉, 41명일 때 요세푸스는 31번째 앉아서 마지막까지 살아남을 수 있었다.
다음 방법은 프로그램 언어 '''파이썬'''을 이용한 프로그래밍이다.
답을 이용해 선험적 추론을 할 수 있다. 답을 구하고자 하는 사람들에게 도움이 되길 바란다.
1. 유래
유대인 역사가 플라비우스 요세푸스가 겪은 경험을 바탕으로 만들어진 문제이다.
당시 예루살렘에서 살았던 요세푸스는 유대-로마 전쟁 때 유대군 장교로 참전했다가 동료 병사들, 자신을 포함해 총 41명과 함께 요타파타[1]에서 서기 70년에 황제가 될 베스파시아누스가 지휘하는 로마군에게 포위되었고, 동료들은 로마군의 손에 죽느니 스스로 죽겠다고 집단자살하기로 했다. 그러나 직접 자살하는 것이 어려웠는지, 그들은 서로 죽이기 위한 알고리즘을 세운다. 요세푸스를 따라온 동료들은 위의 그림과는 다르게 2명 살리고 한 명 죽이는 식으로 자살했다.[2] 그러나 요세푸스는 동료들의 뜻에 반대하고 살고 싶었고, 수학적 논리력을 발휘하여 끝까지 살기 위한 자리를 찾아서 결국 살아남아 베스파시아누스에게 항복했다.
2. 문제
위키피디아출처에 따르면 41개의 숫자 중 하나를 건너뛰는 형태로 없애고 만약 41을 넘어가게 되면 다시 가장 처음번호로 돌아가는 식을 반복해 마지막에 남은 숫자를 구하는 문제이다.
이와는 다르게 보다 일반적인 문제도 있는데, 1~n 까지의 총 n개의 숫자가 있고 처음에는 k를 없애고 그 다음에는 2k를 없애는 식으로 하다가 n을 넘어가게 되면 존재하는 숫자 중 가장 낮은 숫자로 되돌아가 이와 같은 형태를 반복하는 문제이다. 만약 다 세지 못한채 한바퀴를 돌게 되면 그 남은수는 누적된 채 계속 세개 된다. 남은 수를 1개 구하는 경우도 있고, k-1개 구하는 경우도 있으나 두 경우에 있어서 풀이의 차이는 거의 존재하지 않는다.
3. 방법1. 점화식을 이용한 풀이
n 명을 원형으로 세워놓고 3번째마다 지울 때 마지막 남은 사람의 자리수 번호를 $$f(n)$$ 이라 하자
이제 $$f(n)$$ 과 $$f(n+1)$$ 사이의 관계를 찾아보자
$$n+1$$ 명을 원형으로 세워놓고 3번째 사람을 지우면 이제 n명만 남게 되고
4번째 사람부터 다시 시작하는 형태가 된다.
즉, 사람의 배열은.. $$4, 5, 6, 7, 8, 9, \cdots n, n+1, 1, 2$$ (3을 지워서 총 n명) 가 되고
처음 $$f(n)$$ 기준으로는 $$1, 2, 3, 4, 5, 6, \cdots n-3, n-2, n-1, n$$ 순서와 매핑이 된다.
(이 부분이 바로 점화식을 유도하는데 핵심적인 사고이다)
이때 $$n$$명중에 $$p$$번째가 가장 마지막까지 남는 자리라고 하면
즉, $$f(n)=p$$ 라 하자
위의 두 배열의 매핑관계를 보면..다음과 같이 점화식을 유도할 수 있다.
$$p = f(n) = n-1$$ 일때는 $$f(n+1) = 1)$$ $$\cdots$$ ㄱ
$$p = f(n) = n$$ 일때는 $$f(n+1) = 2$$ $$\cdots$$ㄴ
$$p = f(n) = 1, 2, \cdots n-2$$ 일때는 $$f(n+1) = f(n) + 3$$ $$\cdots$$ㄷ
$$f(2)=2$$
ㄴ에 의해 $$f(3)=3$$
ㄱ에 의해 $$f(4)=1$$
ㄷ에 의해 $$f(5)=4$$
ㄱ에 의해 $$f(6)=1$$
ㄷ에 의해 $$f(7)=4$$
ㄷ에 의해 $$f(8)=7$$
ㄱ에 의해 $$f(9)=1$$
:
ㄷ에 의해 $$f(41)=31$$즉, 41명일 때 요세푸스는 31번째 앉아서 마지막까지 살아남을 수 있었다.
4. 방법2. 이진법을 이용한 풀이
5. 방법3. 프로그래밍을 이용한 풀이
다음 방법은 프로그램 언어 '''파이썬'''을 이용한 프로그래밍이다.
【 파이썬 코드 펼치기 · 접기 】
답을 이용해 선험적 추론을 할 수 있다. 답을 구하고자 하는 사람들에게 도움이 되길 바란다.