[수리논술] Josephus 점화식
오늘 과외하면서 했던 내용. Josephus 점화식.
[Josephus와 그의 병사들은 로마 지배에 봉기하여 싸웠지만 위기에 처하자 동굴로 숨어들어 명예롭게 자결하기로 의견을 모았다. Josephus와 그의 동료 41명은 원으로 둘러서서 아무도 남은 사람이 없을 때 까지 세 번째 사람마다 자결하기로 했다. Josephus는 막상 죽음에 직면하자 생존본능(?)이 발동하여 본 문제의 해인 마지막 안전한 자리를 찾아내었고, 결국 살아남아 로마 병사들에게 항복하였다. 그 후 그는 로마에 귀순하여 '유대 전쟁사', '유대 고대사'등의 역사서를 저술하였다.]
칼럼 이름에서 볼 수 있듯 당연하지만, 이는 간단한 사고의 전환을 통해 점화식을 유도하면 된다.
n명을 원형으로 세워두고, 3번째 사람마다 자결(.....나중에 어린이에게 가르칠때는 3번째 사람마다 사탕을 먹는다고 하는게 낫겠다. 가끔 현실은 매우 잔인하다.) 한다고 가정하자. 즉, 1번째 2번째 사람은 살고, 3의 배수번째 사람은 모두 자결(...)하는 것이다. 대략 이런 형태로 지속될 것이다.
우선 n+1명이 원형으로 서있고, 3번째 사람이 자결한 그 상태에서 시행을 잠시만 멈춰보자. 전체 인원은 n명이라고 할 수 있다. 그리고 4번째 사람부터 시행이 새로 시작된다. 이 때 4번째 사람을 다시 '첫 번째 사람'으로 생각하면 결국 n명이 원형으로 서있고, 다시 3번째 사람이 자결하는 구도로 볼 수 있다.
요컨대, n명을 원형으로 세워두고 3번째마다 자결할 때 가장 마지막에 남는 사람의 자리수 번호를 f(n)이라고 할 때, f(n)과 f(n+1)사이의 관계를 구할 수 있다는 것이다. 다음과 같은 3가지로 구분된다.
1) p=f(n)=1~n-2 일 경우, 4번째 사람이 1번째 사람으로 바뀐 구도이므로, f(n+1)일 때에는 '현재 번호보다 3번 더 큰 번호'였던 것이다. 즉, f(n+1)=f(n)+3 의 관계식이 성립한다.
2) p=f(n)=n-1 일 경우, f(n+1)=1을 의미한다. (직접 n+1일때와, 한 명이 자결하고 n명이 되었을 때를 그려보라.)
3) p=f(n)=n 일 경우, f(n+1)=2를 의미한다.
일단, 초항을 살펴보자. 두 명이 있다고 할 때, 1 ㅡ> 2 ㅡ> 1의 3번 시행으로 1번 사람이 자결한다. 고로, 2번 사람이 남는다. 따라서, f(2"명")=2"번째 사람 남음" (이)라고 할 수 있다.
f(2)=2
2)에 의해 f(3)=2
3)에 의해 f(4)=1
1)에 의해 f(5)=4
3)에 의해 f(6)=1
계속해서 나가다보면, f(41)=31이 나오므로, Josephus는 31번째 자리에 있었기에 자결하지 않고 살아남을 수 있었다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
3인가여? 화작 2틀 ㅋ.ㅋ?
-
인강안듣고 걍푸는데 해설 개별로임 걍 마더텅이 200배나음
-
뭔 근학사여
-
받았네요 기쁩니다…
-
얇은책이라 그런지 전 완전히 펼쳐지는 올해꺼가 낫던데 여러분은 어케생각하시나요?
-
담배와 술
-
수능 출제 잡설 0
지도 교수님이 수능 출제 위원 썰 풀어주신거 1. 참고 서적은 교보문고랑 계약해서...
-
사야겠습니다
-
물론 내가 시험지 평가할 레벨은 아님 ㅇㅇ 근데 소비자는 평가해도 되니깐 해보자면 더프가 젤 좋은듯
-
싱싱한 육회에다가 배도 썰고 그 위에 1등급 특란 노른자 올리고 참기름에 깨 솔솔
-
생긴다면 교수님들이 검토하면서 서로 스무고개하겠지?
-
동영상으로 찍어서 반톡에 올려서 보강해준다는데 이게 맞나.. 딱히 문제는 안될거같은데
-
어렵다
-
원래 되게 잘먹는편인데 최근에 식욕이 없어서 하루 한끼..? 도 먹을까말까 한...
-
Jinhak 0
Jinhakapply.com
-
진학사를 진학사라 부르지 못하고
-
정수 문제입니다 꽤 간단하게 풀립니다. 풀이는 내일 올라갑니다!
-
917 11-3 2
익숙합니까?
-
아니 오늘 중간고사 보고 왔는데N2H4가 삼각뿔형이고N2F2가 굽은형이잖아요그래서...
-
마음껏 웃자 9
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
명륜진사
-
많이 느린가요??
-
??
-
ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
진학사 1
나도!
-
아삽 9 0
국영수 학교에서 줬는데 풀만한가요???
-
진학사 0
신설과 쓸 때 주의 :)
-
진학사 5
10칸
-
설거지 완료 4
공부하러 갑니다 답글 못 달아드림
-
주제넘지말라? 흥 웃기는군
-
고1 정시 11
정시를 해야할 거 같은데 이유로는 수시를 확올릴 자신도 없고 올린다고 해도....
-
전 캐스팅 매진이야 …………
-
이거도 되게 바꼈네 곧 오르비 카톡 이미지도 나오려나
-
1. 수능영어에 등장하는 문장들의 두 가지 특징 (2) 내적 정합성 수능영어에...
-
꼴값 1. 명사 ‘얼굴값’을 속되게 이르는 말. 2. 명사 격에 맞지 아니하는...
-
진학사 31
진학사 위 금지어를 제 손으로 없애고 제가 10년만에 처음 써보는 단어가 될...
-
아이고난
-
. 0
머리 왜이러지 쩝
-
주키마 왔다! 3
뭐지 이 Ai 미남은
-
술 먹고싶다 2
술 마구마구 퍼먹고싶다 논술 안보러가도 될 정도로 수능 잘봐서 수능 끝나자마자...
-
비슷한가요?! 개념테크트리, 솔텍1을 한달 반 사이에 돌려들어서 강의 내용 겹치면...
-
그 모든 내용에 WHY? 라고 물을테니
-
모든 준비는 끝났다
-
오래된 생각이다
-
큰일이에요! 대가리를 세게 내리치지 않아서 오늘이 수능이 되어버렸어요! 수능 국어...
-
저 0.2'' 거가 거리 10pc 의미하는 거 맞죠?
-
아 개졸려 3
-
면역의 메커니즘 이 지문 ㅅㅂ 어케 풂? 말이 안되는데 7분은.....
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ