[수리논술] Josephus 점화식
게시글 주소: https://spica.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를 선물하세요.
-
국어 > [리트 전개년 기출 언어이해] 2023 13~15 > [리트 전개년 기출...
-
뒤질래?? 1
뒤질?
-
일단 확인 3
아직 할만해
-
오히려 이러면 3
수능때 난이도 조절 실패해서 대참사날거같은데
-
생명 수능에는 1
이거보단 더 어렵게 낼 듯? 등급컷은 반수생 유입 고려하면 비슷하거나 뭐 그럴듯
-
이따구로 쉬워도 1
이따구로 쉽게 나와도 1등급컷 표점 70? 이야 독하다 독해 이래도 안해?
-
투과목 등급컷 0
망가졌네 근데
-
[자작 문항] 보이지 않는 원이 ㅈㄴ게 무서운 법(1탄) 11
"보이지 않는 검이 ㅈㄴ게~~무서운 법"이 아니고!!! 보이지 않는 원이 무섭습니다...
-
이였을듯ㅋㅋㅋ 90점이상이 1.47퍼에 80점이 9.47이면ㅋㅋㅋ
-
아니 영어 0
제발 쉽게 내주세요...1.47이 뭐야...
-
캬 어제 85받고 정신적충격 받고 개집중해서 풀었더니 kia~~~
-
1컷 34?
-
절평 전환 이후 역대 고1~3 영어 모고 중에서 1등급 비율이 제일 낮은 시험...
-
잇올 9모 0
현장접수 1~5시 사이에만 가능한거? 6시 퇴근이라 6시 이후에만 가능한데…
-
4규 시즌 1 , 이해원, 설맞이(킬러제외), 엔티켓 , 드릴 난이도순이 엌케되나염?
-
물1 48 화1 48 생1 48 지1 47 물2 50 화2 45 생2 47 지2...
-
아쉽긴 한데 뭔가 그 이상으로 생각이 들진 않네
-
아무리 사탐이라도 와 ,,,백분위100개빡세다는걸 체감빡세게함 유기안해야지 ㄹㅇ...
-
佛극우, 사상 첫 다수당 현실화…치명상 마크롱은 벼랑 끝 위기 6
RN, 유럽의회 선거 이어 총선 1위 예측 '연승행진'…의회 1당 되면 총리 배출...
-
왜 바껴서 대면 접수야,, 시간만 날리네
-
ㅇㅇ. 걔네는 동양인보다 피부암에 걸릴 확률이 높대. 그리고 한국인은 외국인에...
-
초고도비만이어도 멀쩡한 이자.. ㄹㅇ 동양인 잘난 게 체지방 잘 비축하기 말곤 없네;;
-
육군은 시간이 짧고 그만큼 빨리 전역하고 나서 남은 시간을 수능에 쏟을 수 있고...
-
기분이 좋다 수분감 마저 하러 간다
-
역대급으로 어려웠던 6평의 결과가 나왔습니다. 교육청 모의고사보다는 6평이,...
-
투과목 1컷 0
지2 48 생2 47 화2 45 물2 50
-
엌ㅋㅋㅋㅋ 이러면 영어 2맞고도 지방의대 쌉가능 아닌가 ㅋㅋㅋㅋ
-
제가 수능 영어를 공부하면서 알게 된 것들을 최대한 글로 표현해보았습니다. 너무...
-
A.재밌잖아여
-
조 바이든 미국 대통령이 도널드 트럼프 전 대통령과의 지난달 27일(현지 시간) 첫...
-
내신 1.2 정도로 가정하면?
-
등급컷 2
현역이라 모르는데 crux님이 올리신 등급컷은 확정 등급컷이라고 봐야 하는 건가요?...
-
보고싶어요
-
생각보단 적다. 문제는 6모 이후에 탈주할 애들이...
-
6평 채점결과 한판정리 만점표점/백분위/등급컷 /탐구영역 8
n2406 crux팀 출처 및 한판으로옮김 에구 몇몇 과목은 집계중 세사,투,...
-
6망수잘 0
응아니야~
-
백분위 기준 언매 미적 영어 한국사 물1 생1 95 85 3 3 89 89 문과든...
-
이러는거임. 설명좀.
-
제2외국어 할 건데 모의고사 예정 있을 때 마다 제2외국어 하는사람 없제? 하셔서...
-
앱스키마 독서 0
좀 어렵던데 나만 그런가….
-
22수능 22122 23수능 21132 문과고 27수능은 서울대 낮과 + 연고대...
-
러셀 생각하고 해서 개망했다 싶었는데 여유롭게 성공 히히
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ