[수리논술] 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를 선물하세요.
-
왜 이렇게 긴거지 6개월도 아니고 1년은...
-
할 수 없으니 애석.
-
아랍어 > 이윤석 [쉽게 이해되는 수능 아랍어] 3강
-
ㅋㅋ ㄹㅇ 실제로 처음보는 유일한 mbti
-
양적관계를 아예 못풀다가 최근에 감잡으니까 마더텅에 고난도 문제들도 풀리긴 하던데 시간이 좀 걸림
-
오늘도 화이팅
-
대충 7시간은 잤는데
-
남르비 어셈블. 14
머리 어느 정도 주기로 깍음? 애매하네
-
-블랫아웃, 앞 흐려지는 증상은 줄어듬 -약 먹은뒤로 대체적으로 무감정성이 강해져서...
-
사탐 한 과목당 2시간씩 하는건 괜찮을까요..?
-
첨들어보는데 전문직 학과 많네
-
얼버기 4
-
나가서 공부할까 0
어디가지
-
성적이 안올 4
실검ㅋㅋㅋㅋㅋ
-
임정환 생윤 0
임팩트 안 하고 올림픽 해도 되나여? 림잇이랑 마더텅 돌림
-
체첸클리어 2
세계사 공부하다가 나무위키로 글만 다시 ㅇㅇ 영상은 안 돼..!
-
덕코복권이제그만 0
해야겠다 완전바닥났네 다시 공부하러감여 ㅎㅇㅌ
-
잘생겨지로 출발
-
간다 가보자고 6논술+정시로 고대 서강대 이대 쟁취한다
-
뒤졌다 다시 겸손하게 배워야지... 피지컬 올린다 딱대 ㅋ
-
제곧내 근데 넘 사람이 없어서 이거 지금 질문해도 되려나
-
그 작년에 0
강민철 프사 달고 활동하시던 분 중에 유명한 분 있었는데 누구였더라 기억나시는분?
-
[OK!제보] 대형개 입마개 하랬더니…"딸들 줄에 묶고 다녀라" 3
반려견 유튜버의 막말과 신상 털이 논란 피해자는 SNS 폐쇄하고 외부 연락 자제...
-
금오공대 아이린 4
예전에 오루비 할때 몇번 들어는 본 것 같은데 누구지 이왜실검 1위
-
귀엽죠?? 3
-
고속버스터미널 10
사르비 꺼라
-
서바이벌 전국 0
그냥 서바랑 브릿지랑 곂치는 문제 있나요 아니면 n서바랑
-
얼버기 3
-
이런저런 공부 잡생각 때문에 잠을 하나도 못잤는데 나 근데 이제 학원 갈준비...
-
혈액팩 2
슈우웁
-
수능영어 시간 부족 문제의 실전적 해결방안 [학습칼럼] 6월 모의고사가 어렵게...
-
도서관을 가 0
어서어서 가
-
안녕하십니까. 국어 기출 거의 2,3번씩은 봤고 다시 회독 중인데 문제들이나 선지...
-
유~성 왕감사 라고하면 안되겠죠?
-
여자고 키150대후반임 입시안할때 50키로초반이엇고 수시때부터 살쪄서 재종에...
-
무조건 성공이다
-
오르비에 활동중인 컨설팅 팀 어디가 좋을까요? 지난주에 수시컨설팅 크럭스 에...
-
공부 딜레마 0
기출 문제 풀어 보면 객관식인데도 정답률 10%대 문제들을 마주하게 되는데 당연히...
-
집가서 좀 쉬다가 공부 조금씩 하시나요 아니면 집중 안되더라도 꾸역꾸역 버티면서 하시나요
-
시대 수학 공통 미적 서바 들어가면 하나는 현강 하나는 라이브 들을라고 하는데...
-
저도 오늘부터 그만큼 하게요... 고려대는 못가도 대학생활 망치기 싫음
-
ㅇㅂㄱ 1
-
ㅇㅂㄱ 3
아웅 졸려 ㅜㅜ
-
아개졸려 0
ㄹㅇ
-
혹시 W관 배정 받았는데 목시 본관에서만 강의 하시는 선생님(이신혁 쌤) 강의 배정...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ