[수리논술] Josephus 점화식
오늘 과외하면서 했던 내용. 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를 선물하세요.
-
넵
-
지금듣는노래 1
-
갑자기 왜이렇게 5
우울하지.. 울고싶군
-
ㅇㅇ
-
오곡 오고곡 8
공부해야지
-
혹시 워라밸 잘 지키고 계신가요? 이번학기 팀플 4개 + 과제 + 토익만 해도...
-
드뎌 다 도착 이제 기출 끝나면 고양이도 사서 커리 끝... 생1 50한자리는 내가...
-
대학교 드가자마자 부모님이 bmw미니사주는 삶이라 부럽네
-
어떠셨나용
-
국어자습 언어엔제 수학엔제,인강 사탐복습 국어인강 언제듣노....
-
f(x)=(x-ltl)(x-lt-2l) 이 함수 그래프가 어떻게 생겼을까여
-
허허허 씨발
-
비문학 시간을 줄여 시간 내에 풀어보자
-
생각보다는 일본의사 연봉이 낮네요.. 엔저 환율 때문에 낮아보이는 건가..
-
예2이상은 해외다니는애들도 많고 힐링하는 애들 많은데 예1은 학교는 다닌다 하는데...
-
30초 주기로 훌쩍이면서 기침 반복하는데 얼음을 와그작와그작 씹어먹네 감기 걸렸으면...
-
4덮 뽑아서 풀어봤는데 4개 찍었어...
-
캬
-
항상 1~1.5지문 버리게 됩니다. 어디서 시간이 많이 새고 있ㅇ나요? 참고로...
-
[속보] 북, 동해상으로 탄도미사일 발사…25일만에 무력 도발 2
북한이 17일 오후 미상의 탄도미사일을 동해상으로 발사했다고 합동참모본부가 밝혔다....
-
인모드 받아야지 1
이게시발 찹쌀모찌야 사람이야
-
https://orbi.kr/00068095509 계속 난이도 얘기가 있어서 진짜...
-
웬만한 수험생이 할정도는 다 한거겠죠? 현강은 7월쯤부터 서바 모의반 들어갈거...
-
ㄱㄱㄱㄱ
-
좀 느리더라도 뉴런 수분감 완벽하게 해놓는게 좋겠져? 2~3번은 다시풀어봐야 할거같은데....
-
수잘싶 15
아.
-
중안부 ㅇㅈ 19
쿄쿄
-
26 감사합니다 4
드디어 저도 정상적인 글을 써서 올리는군요
-
ㅠㅠ
-
고딩때도 보면 분명 운동 방정식 세웠는데 못풀거나 오래 걸리는 경우 있잖아요 등속,...
-
이참에 수능이나 두 번 더 봐버려?
-
뭔가 말이 이상한데 저는 처음에는 실에 추 메달아서 돌릴 떄 장력+구심력=중력인줄...
-
킬캠 1회 기하 0
81인데… 평가원이면 2등급일까요?
-
근데 대학에서 여러과가 다같이 듣는 과목은 좀 고등학교로 내리자 7
미적분학, 선형대수학, 일반 물리&화학(얘네는 물화12에 꽤 많이 있긴한데...
-
Vaia미쳣다 0
솔루션이나 qna관련사이트 죄다 유료라 찾아도 쓰질 못햇는데 여긴 무료에다 설명도 개친절함
-
안녕하세요 :) 디올러 (디올 연구실) 입니다. [맨 아래 애플워치 이벤트]...
-
풀때는 ㅈ같았는데 다 풀고 나면 계속 벡터 분해하고 각도 구하고 해야하는 뉴턴...
-
이화의 국수 성적같다고 하면 뭐가 더 유리한가요..? 상관없나요? 자연은 당연히...
-
안녕하세요, 생달입니다. 오늘은 생명과학1 다인자유전에 대한 스킬 정리입니다. 본인...
-
공부하기싫어요 2
ㅜ ㅜ
-
근데 피부라는게 ㄹㅇ 돈쓰면 노화도 어느정도 막아지나 7
인강강사들 보면 유독 나이대에 비해 젊어보이는 사람들 천지임 생각나는거만해도 윤성훈...
-
하나 찍맞이긴 한데 공부 ㅈ같이 한 거 치고 졸라 잘봤네
-
허리 디스크인줄 알고 엑스레이도 찍어봤는데 디스크쪽에 문제 있는건 아니고 하도 다리...
-
댓글로 끝말잇기 ㄱ? 18
댓글 달면 대댓글로 끝말잇기 해드림
-
학교에서 수업 다 듣고 수행평가도 대충이라도 해서 내는거면 그냥 수시러아님? 아니...
-
이게 인강규칙인가 책을 한번사면 또 못사더라고요 똑같은걸 그래서 야뎁...
-
[오늘의 독해13] LET ENGLISH BE ENGLISH 0
오르비 학생분들 안녕하세요:) 저 개인적으로는 수능영어를 가르침에 있어서 보다는...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ