[수리논술] Josephus 점화식
게시글 주소: https://image.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를 선물하세요.
-
수학 한 달 안한다고 해서 2등급 되려나?
-
거업나 느리네
-
현역보다 재수때 더 못 갔어 현역때 성적이 좀 더 좋았으니까 현역땐 현실을 직시하지...
-
다 맞춘사람 5천덕 언 미 영 지1 물2 과목당 1천덕씩
-
낫배드
-
82인데 ㅈ망한거임!.ㅠ??
-
원래도 못했는데 더 못하네;; 6모 작년보다 못볼듯
-
집으로 배달시켜 놓으면 산책도 하고, 집가자마자 바로 먹고 나올 수 있고 1석...
-
지거국인데 언제 들어올라나.. ㄹㅇ 돈없다..
-
본인이 5모 더프 14 20 맞추고 9번 틀린 병신이면 ㄱㅊ 4
일단 나부터
-
6월에 결혼식 있어서 지금 살짝 장발 이긴 한데 단정하게 잘라야겠지? ㅋㅋㅋㅋ 자취...
-
개념 2번 돌렷고 유형문제집도 기출2.3점도 했고 지금 실전개념 막판 하고 있는데...
-
흠
-
사탐런 고민 6
슬슬 무휴학 반수 시작하려하는데 작년 화생 63 나왔으면 무조건 사탐런 해야할까요?...
-
기하 1될려나요
-
뭐해야하냐??
-
실모성적이 나락으로 가고있다 조졌음 인생이 ㅋㅋㅋㅋ 실모를 너무 n제 풀듯이 푸나...
-
확통공부를 안해서그런가 공통 ㄱㅊ앗는데 확통이 왜케 안풀리냐
-
질문이안보여캬아아아악
-
평소엔 15부ㄴ컷인데 오늘 20분걸림ㅅㅂ
-
아싸 1000덕 아꼈다
-
투표햐주새염
-
중하위권 학생들에게 하고 싶은 이야기입니다. 해당 글에서는 과외의 장점 중 하나인...
-
https://www.instagram.com/06_dream_o0?igsh=bmU4...
-
ㅈㄱㄴ
-
아 아쉽네..
-
맛있었다.
-
문언독 짱 ^~^(독서풀시간없엇다.)
-
독서 2개틀리고 화작 2개틀림..
-
수필 음
-
지금 재수생인데 6모,9모때 학교에서 점심식사는 어떻게 하셨나요??
-
현역 5덮 0
확통4틀 69 언매3틀 83 3 1 ㄱㄴ?
-
1로 찍고 전사함
-
진지하게………..
-
확통에서 절었네 9
이 요망하고 앙큼한 개수세기는 며칠만 안세면 꼭 고집을 부려요
-
5덮 국어 5
94점 수학- ㅈ됨
-
11 부호틀 썅 0
아 존나
-
공통과목에서 1,2,3,4,5,6,7,8,9,16,17,19번 빼고 다 찍었는데...
-
미적 1컷 어느정도 나올 거 같음? 보정컷 말고 92나오려나
-
드리블 0
드리블=뉴런 인가요?
-
5덮수학 92다 0
물론찍은것도있긴한데진짜태어나서이점수처음받아봐요개신난다
-
13답 머임 2
13번 먼가요
-
하 27번 마지막에 연립하고 -tan 옮길때 -안 붙여서 틀렸네... 22 27 28틀
-
.
-
14 22 안 풀리던데 대체 어캐푸는거지.. 정수 -1일때 최대 아닌가..
-
2번 찍었는데 맞았음 좋겠네요
-
20 21 맛있엉
-
. 0
근데 맨날 밥 먹고 뛰어다니니까 힘들쿤.. 인간은 왜 살이 찌는것임 먹거 뛰어야 할 생각하니 착잡.
-
무지성 2, 4 박고 틀림..
-
작년 9월부터 시작해서 모든 시험이 언문독을 고로시하는데 너무한 거 아니냐
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ