[수리논술] Josephus 점화식
게시글 주소: https://ui.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를 선물하세요.
-
ㅈㄴ 아쉽네
-
잇올에서 연애 0
하고싶다.......잘해줄게..
-
뭐야 롤 졌넹 1
어째서
-
1 나온 적 있어요?
-
지금 크럭스 테이블이 2회 수정을 거쳐서 표준점수 산출 공식이 위와 같이 됐는데,...
-
뭔가 작수랑 비슷하지 않았어요..?? 수능문제는 하도 많이 풀어봐서 이젠 쉽다고...
-
곰 호랑이 사람 0
이중 호랑이는 한자어 虎狼+접미사 -이 '곰'은 '고마'에서 음절이 축약되며 성조가...
-
나는지능도떨어지고능력도없는게쓸데없이망상만많이해가지고아무일도없는데걱정거리만늘어나고별의별...
-
슬럼프옴 ㅈ됐네 7
걍 공부가 하기싫네 독재가서 책펴놓고 마음속으로 공부하기싫어 공부하싫어 3000번 외친듯
-
개천절 지났네
-
원래 한의대 목표였는데 무슨 짓을 해서라도 의대에 가야겠습니다 의사가 월400도 못...
-
다들 왤케 잘하는거임 화학을;; 나만 존나 안잡히는건가 서바도 매번 세문제 두문제...
-
후루루룹
-
부모님 왈: >>>전역하면 시작이야 사회생활이 더 힘들다...사회에 나가봐라 지금...
-
수능 미적 개념원리 문제집 풀면 몇번빼고 풀수 있습니까? 3
제가 이번에 약간 수능 공부한게 존나 타임어택이라서 미적을 그냥 개념원리 풀수 있을...
-
질뿍 1
-
기출만 올해 할까요?
-
진짜 존나 피곤하네 뭐만 하면 찡찡거리고 전화 안되냐 나 너무힘들다 뭐 씨발 이...
-
길게 쓰긴 귀찮고 그냥 마늘 얘기할게요. 또 이 접미사 -ᄋᆞᆯ은 중세국어...
-
피부과 가야해요?
-
싹 다 되돌리는 게 맞음 ㅇㅇ 사회 여건은 미국이 아닌데 교육만 미국을 추종하고...
-
강대x 6회차 0
문제 자체는 풀면서 쉽다는 느낌이 나긴했는데 시간이...
-
내일이 중간고산데, 재수하면 수시원서는 절대 안넣을거 같아서 버릴려 하는데, 챙겨야...
-
멤버십 어쩌고 한 이유가 있었군
-
드릴 본교재 대신 워크북만 사서 푸는거 어떤가요..? 그냥 본교재만 사는게 훨씬 나은가요..
-
신 상 혁ㄷㄷ 1
찬양해
-
40일 정도 남았는데 다 풀긴 많아서 2015? 2018?
-
뭐임뇨
-
일반인이 DSM ICD 읽어 봤자겠지만요 그냥 읽어보고 싶네요 일반인이 아닌...
-
과탐의 정상화가 시급하다
-
꽤 자주 연락은 하는데 따로 보긴 어색한 사이 ...전적대(예정) 떠나면 다시 볼 일 없겠죠?
-
2-1까지 내신 4-5사이인 애인데 무조건 부산대가 목표래요 (본캠) 자세히 알지는...
-
공부 말고 책
-
너를 볼 수 있다면...
-
멘탈이 바사삭 수학황이 되는 길은 멀고도 험하구나 다들 안녕히 주무세용
-
수학 최대한 논리적으로 필요충분 잘 써서 푸는 연습해야겠다 과외하는것처럼 국어도 그렇고
-
운전면허증 3
올해 초에 1종 땄는데 다시 딴다고 생각하면 개노잼이어서 못할 듯 내 친구 다른...
-
부질없는 아픔과 이별할수 있도록
-
엔제 투표가 훨 많넹
-
기출 김기현쌤이랑♥️♥️♥️햇고 어삼쉬사풀려햇는데 생각보다너무 쉬워서 걍다풀어버림...
-
우리집 개 보고가세요 10
귀엽죠 ㅎㅎ
-
정말 잘하는 사람이 많이 들어와서 그런걸까요? 공부를 소홀히 하지 않았는데 정말...
-
실모 88의 벽 넘었다 드디어 84~88 진동 -> 88이 더 많은 84~88진동...
-
실모하고 오답하면 피곤할거 같아서 고민임..
-
외않풂
-
알바 해서 모을 수 있나.. 아 공부해야하는데 병원마다 다르다곤 하는데
-
국어꾼도 오면 좋겠네
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ