[수리논술] 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를 선물하세요.
-
내가 멍청해진건가
-
생윤vs윤사 2
사탐런해서 치대나 한의대를 목표로 하고 있습니다 내신으로 윤사, 생윤 밖에 안해봐서...
-
영화관 입개루 13
히히
-
작년엔 거의 필수메타였는데.. 퀄이 떨어졌나?
-
진짜 허리 존나아프다... 아ㅅㅂ ㅈ됐다 소리가 절로 나옴
-
방법이 없을까요? 남들 다 좋다는 운동, 수면, 명상 등등 헬스했을 때도 그렇고...
-
이제 그만할 때 됐지 미련없지 뭐
-
횡단보도 건너려니까 갑자기 붙잡고 성경은 예언서 어쩌고 씨불이길래 이건 또 무슨...
-
커뮤픽 아녓냐? 여기서 보니 반갑네 ㅎㅎ
-
드릴 난이도 0
방학때 드릴할건데 뉴런에서 브랜뉴런에서 조금틀리는거 제외하면 정답률 80퍼정도는...
-
n제 3회독? 0
슬슬 시중에서 유명하다고 말 나온 컨은 거의 다 풀었는데 남은 기간 동안은 n제에서...
-
오늘도 화이팅 1
10시되면 ㅈㄴ 졸려서 2시간 기절하는 거 아닐까 싶다.... 미적분 ㄹㅇ...
-
여친도 나랑 비슷하게 공부하는 수험생이면 가능 그 외에는 불가능
-
간쓸개 풀려는데 2
글자가 너무 작다... 안경을 써야겠음
-
ㄱㄱ
-
뭐야이거;;
-
오늘의 운세에서 1
야간 데이트하기 좋은 날이라는데 누구랑....?
-
여캐일러 투척. 3
수능 만점 기원 3일차
-
부모님이 집공 하라고 하심 비많이오고 천둥치고 바람도 씨게 불어서 일단 개이득..?...
-
패드 쓸 때 0
밝기 좀 낮추고 종이 필름 붙이고 쓰면 눈 딱히 안 아픔
-
얼리부기 6
아카데미로 가자
-
다들 ㅎㅇㅎㅇ 0
-
비오니까 머리 7
다꼬이네 ㅜㅜ
-
아 ㅅㅂ 애플워치 10
안가져옴
-
강대x 써킷이 4
공통 9~14번, 20,21번 선택 27~29번 급 문제가 있는거구나 11문제넹
-
아침추천좀 2
배고푸당
-
평가원 교육청은 잘 나오는데 뭘까
-
관악구 쪽인데 거의 1시간이 찍히네
-
비 오는게 좋다.
-
그래도 이성으로 절제하긴 하는데 하 ㅅㅂ 그냥 말거니까 화가 확 올라오네...
-
아니 그럼 다른 메디컬도 높아질거 아냐..
-
7모해설끝. 0
와 ㄹㅇ 개어렵네 미친ㅋㅋㅋㅋㅋ 최근 평가원 애지간한거보다 더 어려운거 같은데 그냥 숨쉴구멍을안주네
-
자기가 하나의 드릴만 풀어야한다면 이건 꼭 풀어야한다를 기준으로 골라주세요
-
본인도 11덮 예상 대학 건동홍이였음.
-
반수생 사탐 0
6모 사문,생윤 둘 다 1 떴는데 불안해서… 기출 문제집 한 번 쫙 돌리고 N제...
-
이게 무슨 일이야...
-
팔이 안움직여 0
머리로 누르고잒네
-
진짜 방송 탔어요? 자다가 일어나보니 방송탔다고 허네
-
ㄱㅊㅈㄴㄱㄷ 3
ㅎㄱㅇㅎ!
-
7x7 칠주 뒤 구평이에오
-
공화당 전대 주변서 1명 사살돼… “이란, 트럼프 암살 시도” 첩보도 0
트럼프 피격 사건 후유증 계속 위스콘신주 밀워키에서 약 5만명 이상이 참석한 공화당...
-
그냥 현강처럼 책상 두 세자리씩 붙여서 시험 보는 건 아니죠?
-
기숙 나오니까 0
공부 진짜 안되네… 기숙학원 가서 인간개조 끝난줄 알았더만 집 오니까 원상복귀 됨 ㅋㅋㅋㅋ
-
기차 출발 한당 1
ㅇㅅㄹㅎ
-
얼버기 3
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ