[수리논술] Josephus 점화식
게시글 주소: https://io.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를 선물하세요.
-
총 합산 77.2점인데 3등급 턱걸이 할 수 있을까요ㅠㅠ 수행 40점 만점에...
-
국어성적이 올라가나요? 사회생활을 하면서 다양한 일을 겪고 사람들과 이야기를 나누면...
-
영어 1이면 의대뚫리노 ㅋㅋ<가 내글이였는데
-
올해 야구 다시는 안봄 ㅇㅇ (올스타전 코시 제외)
-
올라서 다행이에요. 자랑할 곳이 없어서 여기에 올려요
-
교재 이름이 신선하네요 ㅋㅋ
-
옯붕이들 사랑해 0
-
올해 수학다음으로 영어를 많이했다니까 ㄹㅇ sibal 6모 개색갸!!
-
[화제의 연구]수학만 못한다고? '난산증' 의심해봐야 4
[아시아경제 윤신원 기자] 다른 과목은 다 잘하는데 수학만 못 하는 아이가 있다면...
-
안녕하세요, 의대 수리논술 전문 유튜브 채널 '수학GPT'에서 2024학년도 의대...
-
반대로 말하면 약간 난이도는 그렇게 높진 않은듯…? 도표는 ㄹㅇ goat 평가원 그 자체
-
되게 간단하고 직관적이라 기분좋음 ㄹㅇ
-
수특이 난이도 나한테 딱 맞는데 비슷한 거 아시는 분?!
-
매월승리 7호? 0
아직 배송 안오거 맞죠?
-
과탐 씨발샛기야 9모때 다시보자 어어 그래그래
-
무신사 같은 데 베스트 상위권에 머슬핏 ㅈㄴ 많음;;
-
아 진짜 좟같네 0
요즘 애들 왤케 싸가지가 없냐... 독서실인데 엄연히 라인 그어져있는데 ㅈㄴ 쳐...
-
부슬비와 보슬비 모두 비자립적 어근+명사로 보는 게 적절함 3
부슬/보슬이 단독으로 기능하는 건 '부슬부슬/보슬보슬' 같은 첩어나...
-
생각해보니 1학년때 가버리면 선이수과목땜에 시간표 줄줄이꼬임..
-
매일 그날 공부할거 다 끝내고 1시간정도 책읽으려는데 이게 도움될까??
-
국어 > [상상국어 모의고사 시즌3 4] 공통, 화작 > [ebs를 부탁해 수특...
-
진학에도 안뜨는거같던데 백분위인데 러프하게 알려주실수있나용 화작 85 미적 96...
-
방인혁 expert zero 랑 expert 1 중에 뭐가 나을까요??
-
이번에 여름방학에 미적분 처음 공부하는고2 정시파입니다. 학원 안다니고 인강으로...
-
6모 화작 77 미적81 영어 55 물리 39 지구 29 9모 목표 화작 90 미적...
-
ㅅㅂ ㅠㅠ
-
숨 쉬기 불편해서 습관적으로 숨 참게됨 비염 진짜 씹...
-
수학 황 계신가여... 질문드립니다 ㅠㅠㅠㅠㅠㅠㅠㅜ 1
작수 낮 2 올해 6모도 낮 2인 반수?생입니다(4월부터 시작함) 4월부터 고1수학...
-
화작 확통 쌍윤 95 93 3 89 93 더 올릴 예정이긴 합니다만... 0.현재...
-
이미지 미친개념+기분 수1,2,확통 1회독 완료했는데 입문엔제 들어가도 되나요?...
-
시중에서 구할 수 있는걸로... 중고거래 귀차나
-
뭐뇨이..
-
열등감 때문에 못해먹겠다
-
서울대 정시 0
전사고에서 내신 4점대이고 절대평가 과목들은 모두 A 받았습니다. 1학년때 영어가...
-
막 계정에 있는 거 다 털어가지 않음? 비번만 바꾸고 나머지 하나도 안 건드린 건 무슨 경우지...
-
시대인재 컨텐츠 1
재종이 아니고 단과만 듣는 경우는 컨텐츠가 어떻게 배부되는 건가요? 듣는 수업...
-
Ad,ae 길이비율 구하는 근거가 뭔가요
-
안녕하세요 이제 곧 여름방학이기도하고 현재 수학 모의고사 성적이 계속 2~3등급...
-
5뜨는 정시파이터 혀녀긴데 이제 개념유형 지로함수 중 마닳은 1부터 안 풀고...
-
이감 상상 한수 있는건 아는데 뭐가 좋은지 모르겠고 어디서 사는지도 몰겠네
-
저 앱 컷나는데 이유가 뭘까요 신용점수가 낮은 것도 아니고 다른 대출도 없는데...
-
진짜그냥물린데
-
하 서브웨이 전부 해체해서 먹는얘는 나밖에 없을거임 18
이거 먹기 너무 어려워 걍 빡쳐서 칼로 썰고 포크로 찍어먹는중 보여주고 싶은데 보여주면 욕먹을듯
-
"군병원에선 '탈구'랬는데"...발가락 골절된 채 한 달 복무한 병장 1
강원도 한 육군 부대에서 복무 중인 20대 병장이 발가락이 부러진 채 한 달이나...
-
PC는 이제 정치적 생명력을 다한 사상 미국에 대적할만한 국가들의 경쟁력을 좀먹는데...
-
내신cc여도 윤사 표점 75 76 77 78 그라운드 뒤짚던데...
-
내신 계산 해보려 하는데 이거 123학년 반영비 같게 하면 되나요?
-
근데 화학 4단원은 시작도 안했다고? 1,2,3단원으로만 2등급 쟁취하기 도전
-
납득했습니다 안타깝네요 절평인데 이딴거 내는게 괘씸해서 한문제라도 전원정답 시켜볼랬는데 ㄲㅂ
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ