[수리논술] Josephus 점화식
게시글 주소: https://iu.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를 선물하세요.
-
원하시면 힌트드림
-
안녕하살법 2
-
소름돋고 어쩌고 저쩌고 다 근들갑떠는걸로밖에 안보인다
-
가장 무서운 거 0
걱정 없이 평온하게 살다 ㅈ같은 일이 뜬금없이 닥치는 거 존나 멘탈 아작날 거 같음...
-
3모때 그냥 문제지 순서대로 풀었는데 문학 다 푸니까 시간이 별로 없어서 급하게...
-
Tmi 8
이 분 저 윈터스쿨때 담임이었고 지금은 저희 집앞 학원에 근무중이심 의외로 목소리 걸걸하셨던
-
오늘자 노추2 0
ㅇㅇ ㄹㅇ 노추임 저거 ㄹㅇ 노래임 네버고나깁유업.
-
형이야
-
부럽다 부러워
-
진짜 나형은 이랬음??
-
준비중인 똥글 리스트 11
1. 인강 vs 현강 2. 실모 활용법 3. 시기별 해야 할 공부 4. 본인이 썼던...
-
잡담 태그 차단 4
어케하는 거임 안 나오는데
-
진짜 위기입니다 어 그게 나네..
-
잘 살고 계시려나
-
뜨끈한 국밥에 4
치킨이 먹고셒구나
-
다들행복하세요 1
-
자러갑니다 3
팔이 불타는거 같네요 근육통이 기대됩니다
-
반수생이다 보니 문학론+개념어강의를 듣고 체화하고 싶은데 고전시가tmi의 양이 좀 부담스럽네요.
-
눈감은채로 밤샘 7시간뒤 독재학원 첫등원 또밤새것어 자고싶ㅇㅓ요
-
인증할 사진 찾는중 26
근데 올릴만한게 없어요 그리고 찾다보니 오르비언들 눈이 썩는것으로부터 지켜줘야한다는...
-
다들 바이 3
-
챠챠챤넬토로쿠~ 챤넬토로쿠~
-
졸귀
-
오늘글을너무많이썻네 12
자기전의오르비는끗
-
지론지론 3
그냥 평소에 하던 생각인데 그렇다고 망상이나 헛소리는 아니고 그렇다고 엄청...
-
국어 새기분 익히마 수학 뉴런 끝 수분감 못끝냄 영어 안함 물리 기출300플러스...
-
살아났으면 좋겠어요
-
바로 나.. 죄송합니다 부모님...
-
나 악력 오른손 58 왼손 39임
-
왜 오른손에만 굳은살이
-
언매 기하 쌍지요
-
사실 이건 모든 개념공부때 하는 말이긴 한데, 개념 자체를 외운다기보다는, 개념서의...
-
이게 맞나요?
-
결혼하려고 혼수까지 준비해서 몸만 가면되는데...하
-
작수 7등급 노베이스부터 지금까지 한게 신택스(작년에 수강), 알고리즘,...
-
우선순위는 중요도 순서로도 갈 생각이지만 필요하신 작품있으면 그것부터 할 생각이에요...
-
수능이 아니더라도 일상에서 그리고 사회에서 배워두면 아주 유용할 것 같다고...
-
내일5월학평임? 3
수학은어디까지범위임?
-
키빼몸 몇인가요 다들 35
저는 119
-
나머지한과목죽쑤기
-
크아악 2미스
-
난 애니프사가 좋아 14
-
히히
-
수학1등급받는법 8
기하선택하기
-
둘다 그냥 기테마 1에 에필로그 4 주는거 아님??
-
사실 기억에 남는건 강k 뿐인..
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ