[수리논술] Josephus 점화식
게시글 주소: https://snu.orbi.kr/0006407291
오늘 과외하면서 했던 내용. 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를 선물하세요.
-
평가원 교육청 언매는 다 맞거나 1개 틀리고 사설 모고는 계속 2~3개씩 틀리는데...
-
예전에 잠깐 내신기간에 학원 근무할 당시 여자쌤들은 교무실에서 다 죽어가는데...
-
웬만한 인강선생보다 오개념 없고 깔끔하고 친절함ㅇㅇ
-
네
-
독서 -2점 문학 -5점 언매 -2점 91점. 문학 34번은 소거법으로 겨우 맞춤....
-
전체 줄거리,전문 봤는데도 효과 못봤다고 그러는거임? 국어 못하는 입장에서...
-
1교시발 0
으악
-
교재 구매란에서 없어졌네요
-
질문있어요 1
학교에서 수험표? 같은걸 내라는데 이게 안되면 안되나요? 수시 수험표인듯 이걸...
-
뇌신경 1
뇌신경이 말초 신경인지 묻는 평가원 선지가 있었던 것으로 안다. 당연히(?) 말초...
-
컨디션 좋을 때 56일 밖에 안 남았네 ㅈ댓다... 할 거 ㅈㄴ 많은데... 컨디션...
-
한자 1급 일본어 jlpt n3 따고 중국어도 재밌게 공부했었는데 영어 이 3끼가...
-
"Sushi"를 좋아해서
-
나는야 담요단~
-
6시 30이면 적당하나요?
-
공부 안 해도 되는 거 아닌가요? (진짜모름)
-
답이 어마어마하게 복잡합니다 괜히 답 구하신다고 고생하실까봐
-
12시까지 탐구 박아야지 캬캬
-
사문 질문 2
2번이 맞는 이유가 관료제의 구성원들이 연공서열뿐만 아니라 자격과 능력을 기준으로...
-
국어 실모 0
국어 모고볼때 ㅈㄴ 개떨어서 ㄷㄷㄷㄷ하면서 봄 데근데 혼자서 국어실모 풀때는...
-
스카 좀 클린하려나
-
내가좋아한다는 사실이 상처가 될 수 있잖아요 <<이말 5
이해가 안댔는데 메인보고 이해했다
-
영어 2>1 7
영어 2에서 1로 올린 분들 공부 어케 하심?
-
실모를 벅벅 0
-
불수능과 물수능의 중간 적당한 등급컷은 어느정도임? 국어 90 수학 84 정돈가
-
살까
-
본인의 최종 내신은 4.01이다! 그저 개꿈..... 붙어놓고 나도 이게 왜 붙지?? 라고 생각했음
-
병원 갔다가 스카갈게요..
-
지구과학은 3
개천절부터
-
지금 이태원 1
이태원 프리담~
-
졸리고 공하싫 11
하지만 해야함 언제 끝남 이 짓거리 근데 끝낼 준비는 안됨
-
이거 풀 때 입모양으로 으어아우오 이러면서 풂ㅋㅋ
-
해석 따로 안 해주는 거임?
-
이해원n제에서 배터리 3칸은 잘 풀면서 배터리2칸에서 막히고.. 히카도 21 22는...
-
수능 3점, 수특 레벨1 쎈b단계 상문제 제외 다 맞을 수 있음 근데 그 이후...
-
핑프 ㅈㅅ해요 두각 시대 둘다 현강 다니긴하는데 국어단과는 따로 안다닙니다...
-
국어는 어떻게 매일 하기가 싫지?
-
공부하다 뭔가 막힐 때 기본으로 돌아가 그 원리를 파악하고 다시 막혔거나 틀린...
-
시대북스 저번주 수요일에 주문한거 아직도 배송준비중이네 1
아무리 추석 껴있다 해도 같은날 시킨 다른 사이트 책들은 다 왔는데..
-
휴가다 0
-
좋은 아침이에요 2
-
4층복도 너무 어두워서 불키고 반은 더워서 복도소파에 앉아있었는데 복도 불이 자기...
-
올해 수능 보겠네 웃긴건 나도 본다는 점,,,,ㅋ
-
얼버밤샘 8
얼버기는 아닌거 같아요
-
왔다갔다 하는데 넘 오래걸려
-
그래서 좀 엄한 느낌이거든요 직원 분들이 친절한 분은 친절하지만
-
어때요
-
좀 아
-
얼버기 6
-
과외 늦을것같거나 들고가야할 물건이 너무 커서 지하철에 들고타기가 좀 그럴때가 아님...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ