[수리논술] Josephus 점화식
게시글 주소: https://i9.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를 선물하세요.
-
배경지식이 쌓이면 쌓일수록 이상한 쪽으로 자꾸 자아가 생겨요 내가 쓴 것도 아닌데...
-
[단독] 공수처장 후보 딸, 20살 때부터 로펌 근무…“알바였다” 3
오동운 고위공직자범죄수사처(공수처)장 후보자의 딸이 20살 때 재개발 예정지에 있던...
-
민희진, 대표 단독 '뉴진스 계약 해지권' 요구…하이브 '거절' 5
이사회 거치지 않고 계약 해지 가능하게 하는 주주 간 계약 수정안 (서울=연합뉴스)...
-
국내 첫 ‘딸 출산’ 레즈비언 부부 “혈연만이 가족이라 생각 안 해요” 2
에세이 ‘언니, 나랑 결혼할래요?’의 저자 김규진씨는 지난 2019년 동성 연인...
-
‘경영난’에 수도권 분만병원도 ‘폐업’…“분만 인프라 회복 정책 必” 1
수도권 분만병원으로 신생아 출산을 담당해 온 A여성병원이 개원 40여년 만에 문을...
-
내가 이래서 지나가는 사람들(특히 10,20대 여자들)이 마음에 안드는 표정하고...
-
하.. 인생 거의 기말 전부 만점 받아겠는데 뷴명하는 답들을 잘 썼는데 어디서 깍인거니
-
정시에 내신반영 된다고들 하시던데 100%수능 성적만 보는 전형은 없어지는건가요?...
-
늘 그랬듯 미래의 내가 걱정을 해결해줬잖아
-
[단독]복지부, 의대 2000명 증원 근거자료 공개 거부 2
보건복지부가 의대 2000명 증원 결정에 사용한 한국보건사회연구원,...
-
Ladies and Gentlemen, My name is Ryan from...
-
ㄴㅇㅅ 어차피 로스쿨이나 사기업 가는 거 아니면 학점은 ㅈ망해도 상관없어~!
-
평균은? 80점 2
내 점수는 8점
-
전공의 : 세후 2000이상 벌려고, 주88시간이상 갈리며 버텼는데 이번 정책으로...
-
이제 개념 1회독 마쳤고 기출은 안했어요. 근데 개념 2회독에 문풀 하고 싶어서...
-
시발점 완수 이외엔 볼만한게 없...
-
경희대치과병원 1
사랑니 잘 뽑나요?
-
일단 2학년이고, 자사고 다니고 있는데 내신 박아서.. 맘 굳게 먹고...
-
예뻤네요 0
Was pretty
-
굿ㅋㅋ
-
이런..
-
. 1
계단에서 쭈구리 처럼 밥 먹으려고 구랬는데 사람 마주침 머쓱 .. 안에서 먹으면...
-
자고일어나니 2
감기에 걸린 느김이 콧물이 쥴쥴
-
확통 안하면 안해도 되는 건가요?
-
ㅈㅂ 씨발제발 제발하느님 칸없는데 급하게 답수정하느라 화이트금지사항을 생각을못함...
-
갓생을 살아봐요 2
몬스터를 마시며..
-
으아앙
-
ㅇㅂㄱ 7
1교시이슈
-
대학병원은 지금이랑 똑같을듯
-
동생 고삼인데 학교내신만 챙김 진짜 수능공부 일절 안함 (엄마피셜 모고가 항상 낮게...
-
스펙이랑 경력도 괜찮다고 생각했는데 진짜 잘 안 구해지네요..
-
병신 머저리 걍 ㅈㄴ 비호감
-
5등급이래서 4등급으로만 올리면 된다던데 난 내신 갖다버렸어서...국어랑 영어내신 어떻게 공부함?
-
이게 뭐노... 채권에 속성을 두개나 부여해버리면 대가리 터져버렷
-
컴공도 빙하기 오는 건가?
-
얼리버드 1
일찍 일어난 새가 아침을 먹는다
-
1빠 맨날 잠안자고 핸드폰 만지작거리다가 그만 잠자는법을 잊어먹어벌임
-
개념인강책(완료)+기출문제집(마더텅 자이스토리같은거 말고 600~800문제이내...
-
하나
-
다들 공부 어케 하심?? 지구만 어케 해보면 될거같은데 꿀팁좀 주세요..ㅎㅎ
-
문학은 김상훈이 좋대서 김상훈 들어볼려고 함. 그런데 문학 독서 다른 쌤 커리 타면...
-
이강인 벤치 0
-
퇴근 1
크어 힘들다
-
외로움…..사실 자취 탓이 아니라 아싸찐따라 사람을 못 만나서 외로움
-
일단나부터
-
현우진~라면ㅋㅋ!!
-
깨어있을때 공부량만 채우면 큰 상관 없는듯
-
나만 이상한거 같나...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ