[수리논술] 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를 선물하세요.
-
들고 있던 사람이 탈퇴했나
-
나도랩싓앨범들으면서 느끼고싶은데 멜로디라인은 묻어있어야 플리에 담을 맛이 나네...
-
개념 적고 쉬워서 변별을 어케 하지 다른 과목처럼 신유형 추론으로 승부 보나?
-
ㅇㅈ 3
미방…. 어렸을 적 사진….넵…..허허 한번 올려봄ㅋㅋㅋ
-
오마이갓 비상사태
-
하루에 3시간 이상 공부하면 죽는 병이라도 걸렸나 하 오늘은 무조건 넘긴다..
-
급하게 넘겨 검토진분들께 죄송하네..
-
이럴수가..
-
괜히 어디 나가야 되는 날만 밤 새다가 오르비 재밌는 거 없나 하고 슬금슬금...
-
7ㅐ추를 벅벅
-
쉿이랑 나띠 솔로곡인 슈가코트
-
읽지도 않는 책 무작정 사 모으는 거 자제하고 있었는데 0
연초에 이런 딜을 봤거든요 대충 흥미는 있는데 할인폭이 아주 크지는 않았던 걸로...
-
나그만따돌려
-
너랑 같이 공부 할 생각에 벌써부터 손에서 물이 나온다
-
얼버기! 5
-
얼버기 6
-
피코 강사분께 0
저작권에 대해 너무 무지하신 거 같습니다.책임감이 있으신 성인이시라면 피하지...
-
첫차타고 집가기 2
3개월만이네
-
비닐 안 깐 기범비급 세트 (정오 ㅈㄴ 많아서 아예 새로 보내줬었는데 걍 쓰던 거...
-
제목 그대로
-
저 메인글 저격 뉴진스민지는 본만모 허위논란 자작극 본인이라 믿음이 진짜 1도...
-
금요일 토요일 1
수학만 했어
-
흐무흐무
-
벌써 새벽 4시 0
공부를 못해서 우울하군아...
-
팔로우수 뭐지 2
얼버기 올리자마자 두분 삭제..
-
얼버기 8
-
글은 왜 안써
-
오르비가 죽었다 2
...
-
사람들 반응이 너무 안좋은데 다시 복귀해도 메이드인경상도는 폐지하려나 정용화편 너무...
-
방굽습니다 4
아직도 안주무신다면..! 당신은 진짜 위기입니다
-
네.
-
전화컴 다니는 지거국 중경외시 이상 학교 문과 둘중 누가더 취업 잘됨? 연봉수준...
-
독재 바꿔야겠네 7
뭔 재수학원이 뻑하면 쉬니 돈벌기 싫은듯
-
대지고기 먹으면 두드러기 올라옴..ㅜㅜ 원래는 안그랬는데
-
나 고등학생때는 되게 밝았는데
-
검독수리는 시속 240으로 꼴아박고 고릴라는 근욱빵빵임
-
나 혼자만 침전하는 느낌이야
-
잘나온 사진 수집하면서 장보는거마냥 컬렉션 제작 가능
-
oh how did you feel넌 내 삶에 큰 공이라고어제의 내가 몰래 가져놓은...
-
이걸 쏟네 ㅅ#
-
내일은 푹 자고 6
시냅스만 풀어야겠다
-
누가 스타트 끊을거임?
-
초딩한테손흥민반팔티사주먼젛아함? 환장할까? 저학년이고 이미삼 어때?축구 ㅈㄴ좋아하는애임
-
ㅠㅠㅠ 제가 자꾸 고장 나는데 어쩌죠?? ㅜㅜㅜ 너무 좋은데 어쩌죠?? 너무...
-
지사의 중에선 좀 쳐주나요? 아니면 하위지사의인가요?
-
스카, 공부하러 카페 진짜 시간 낭비 그자체임.. 만나서 같이 공부할 생각을 한다?...
-
안녕하세요
-
인증 못봤어..
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ