[수리논술] 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를 선물하세요.
-
알바 0
사장님이 공부할 수 있게 배려도 많이 해주셔서 편의점 야간 알바 하는 중인데...
-
아오 ㅠ
-
“나” 기상 2
-
레전드얼버기 2
ㄹㅈㄷ
-
이벤트스토리 제대로본건 첨인데 정말재밌게봤습니다..
-
엄.. 미안.. ㅎㅎ
-
해뜬다 1
다시 더움의 시간이
-
마라탕후루단 입성
-
잠 자려면 개 오래 걸리고 전에 검사하니까 잠들어도 깊게 안자고 얕게만 잔다던데 내...
-
으히히
-
2주분량꿈을ㄷㄷ 근데 건물구조나 설정 재밌네
-
잠 좀 자자
-
지금 스카감 8
아버지 매우 당황
-
영재학급 대표로 선서를 하고 부화기를 직접 만들던 시절 아 옛날이여 우울증 때문인지...
-
삼수하고 대학 교체하고 바로 3월에 입대하려고 하는데 정시발표나고나서 이 때 가만히...
-
확실히 졸리니까 3
언어가 단조로워짐
-
ㅇㅇ
-
드릴을풀며 탈릅한오르비언과 디엠을주고받는 나
-
움직이자
-
바로 수특가면 ㅈ됨?
-
물1 화1 하기 전에 영재고 준비할땐 안했었는데 별 문제 없었던 걸로 기억
-
고2를 고3처럼 보내고 고3을 재수처럼 보내서 수능 점수로 대학에 가자 이거였는데...
-
잘생긴 남자가 극도로 희귀하니까 여자들 눈이 남자에 비해 낮게 형성된거라고...
-
전문항 정복하려면 시간 얼마나 걸리나요 수학에 시간 많이 투자 가능 작수 미적 98베이스
-
시름 그러지안기위해선 무게감이있는사람이.되어야겠지요 그래서오늘부터.다이어트철회합니다
-
오르비에선 그냥 찐따처럼 대접받을 수 있다니 참으로 감사한 일이다
-
잊었다고 생각한 7년간 짝사랑한 ㅊㅇ이 생각이 나 그니까 제발 저 메타들 좀 안열어주면 안됭까
-
미적 선택이고 모의고사를 보면 88~92정도 점수대가 나옵니다 시간이 충분히...
-
입시 좌우명이 ‘정시선언한 이상 남부끄럽지 않게 고2를 고3처럼, 고3을...
-
작년 수능 때 ㄹㅇ 기본 개념만 안 상태로 수능치러 갔다가 4등급 받음 근데 올해는...
-
어떻게 생각하세요? 공부 방해도 그렇고 특히 밤에 휴대폰하는거 고치기가 힘든데 걍...
-
드릴을 풀겠습니다
-
내 남은 행복의 전부를 너네에게 나눠줄게
-
근데 다들 8
안 자고 뭐하시나요
-
ㅜㅜㅜㅜ낼 계획 다망가졌네
-
그와 동시에 현실에 안주하지 않기.
-
정주행 하고싶네 수능 끝나면 어벤져스 시리즈도 정주행 해야지
-
난내년에도1학년임 ㅈ댓다 난올해도1학년이고 작년에도1학년이엿고 재젹년에도1학년이엿음
-
시험공부 싫다 그냥 적성 안 맞음 핑계인가? ㅋㅋ ㅎ ㅋㅋ
-
담주에 들어가는데 원내휴가 사이클이 어떻게 돌아가는건지 알구싶습니다 그리고 원내휴가...
-
피곤하다 6
왜그와중디아4를켜가지고
-
진짜 과탐런함 4
같은 48점인데 과탐은 소신 사탐은 상향!?!?! 이거보고 과탐하기로 했다
-
에 있는 책으로만 공부하면 몇등급 ㄱㄴ?
-
8연승후 6연패 1
너무억울해서잠잘수가없어요
-
세상에는 나랑 다른 사람이 너무 많다 모든 부분에서 내 앞가림이나 잘해야지
-
옯붕이는 한다면 한다.
-
개빡
-
두 분 얼굴을 보니 ㄱㅊ아짐
-
휴학하고 반수할랬더니 마음이 싹 가셨는데 2학기 복학하긴 싫고 대외활동이랑 일은...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ