[수리논술] Josephus 점화식
게시글 주소: https://i.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를 선물하세요.
-
'PA 간호사법' 5월 국회 통과 유력…의협 "반대" 0
PA 간호사는 의사의 진료 업무 일부를 대신할 수 있는 간호사로, 전국에 약 1만...
-
. 0
오늘도..
-
행복할래 나도 0
-
수특 수2 0
도함수의 활용(1) 유제부터 level3까지 31문제 푸는데 66분 걸렸으면 ㅁㅌㅊ?
-
고3/N수, 언매 미적 과탐 과탐 선택자...
-
아가 기상 1
피곤하다
-
장학생이면 0
공부잘하는건가요? 노무현대통령 고딩때 부산상고 장학생
-
2등급 3등급섞이면 가나요?
-
ㅎㅎ 즐거우세요? 즐거운데요?ㅋㅋ
-
공부잘한 애들이 가는곳인가요?
-
노짱시절 0
부산상고 공부잘했노?
-
공부좀 했나요? 부산상고출신이라던데
-
고1 6모가 1학기 중간고사 범위 맞죠? 보통 복습하고 6모 치나요?
-
현실이 힘든건 0
윗세대와 나라의 잘못이라고 생각함. 결코 내가 못나서가 아님.
-
공부잘하는곳인가요
-
??
-
갑자기 궁금합니다
-
그냥 한심함 누가 문과 이과 하라고 칼들고 협박한것도 아니고 다른쪽이 개꿀빨고...
-
꿀이라고 그냥 무지성으로 달려들어서 꿀빨거였으면 다리자르고 사회배려자 전형으로...
-
SECX 0
-
원래 1컷 근방에서 올리기 힘든가용 한 두달도 아니고 8달째 성적이 그대로니 정신병 올 거 같음
-
한국판 결속밴드 0
https://youtu.be/8pT6NPOCKQY?si=Qb2XPx9IKczl_8KY
-
아이고난! 2
-
롤체갤4년했네 8
이제글써도되겠다
-
경력약2년 고3,n수전문 평가원 수학 수능 포함 100점 3번 정시의대 서울지역...
-
시대 편입생 일주일 다녔는데 벌써 탈주하고싶음 어캄ㅜㅜ 가뜩이나 공부 늦게 시작해서...
-
ㄹㅇ행복은탄수화물인가..
-
한완기 수1,수2 3회독 미적분 2회독 문해전 시즌1 수1,수2 빅포텐 시즌1...
-
시대k가 뭔데 3
왜 자꾸 실검에 있는거야
-
그래도 꽤 오랜 기간 배웠슴다
-
침실에 티비가 있는거... 누워서 티비보고 지하에는 아예 영화관까지 있네 나도 존나...
-
오르비 책이 급하게 사고싶을때 로켓배송 쌉가능 로켓와우 스피드로 책 받으니 기분 굿
-
안해요
-
일단 뭐 유학처럼 학술적 목적은 아니고 그냥 일상 대화나 애니 보는데 조금 이해될...
-
고려대학교. 7
고려대학교.
-
뭐임?
-
국수영물지 중 살만한거 있음?
-
정시 과목 추천 받아요 언매 미적 영어 한국사 탐구 두 개를 뭐 할지 모르겟어요...
-
안녕하세요 오르비에 처음으로 고민을 올라게된 올해 대학입학한 사람입니다. 제 고민은...
-
https://orbi.kr/00067989953/%5B%EB%8B%A8%EB%8F%...
-
본인은 지금 존나 파릇파릇한 고1임 얼마 되지 않은 작년에 이 친구를 처음 만남...
-
강민철 1
-
인증 궁금함? 2
ㅇㅇ
-
고수는 아니지만,,, 짤막하게라도 남겨봅니다....
-
대신 이레즈미는 안됨 전담이어야함
-
아니 케바케이러지말고 평균값으로 ㄱ ㄱ 킬캠이나 빡모 같은 고난도 모의고사는 1컷...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ