[수리논술] 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를 선물하세요.
-
형은 3시에 쳐자고 얼버기에 성공했어
-
안녕하세요 :) 디올러 S (디올 Science, 디올 소통 계정) 입니다....
-
제가 너무 노베라 이 개념서도 버겁네요 ebsi 수학의왕도 강좌랑 같이 빠르게...
-
그냥 갑자기 궁금한건데 의대 증원되면 의대지망생 분들이 좋은건가요?? 오히려 엔수생...
-
오야스미 0
네루!
-
5시전에는 잠들지 못하는 몸이 되어버림
-
어차피 이 ㅄ같은 입시판 1년만에 물갈이되서 뭐 강사든 컨설팅팀이든 1년뒤에...
-
작년꺼 그냥 풀어도되나요
-
바꿔야지 0
바뀌어야지
-
터키가보고싶다 0
터키 리라 환율도박살났는데 돈이없어서울었다
-
https://m.dcinside.com/board/hanmath/6399898 제...
-
저는 배우는 입장이고 선생님은 가르치는 입장에서 제가 이런 말을 한다는 것은 꽤나...
-
놀랍게도 씨엔블루임 요새 다시 많이 듣는 중 Can't stop, Love 명곡
-
시간참...
-
정떨어지려나 고기 말고 거의 다 안 먹는데
-
전 메이플 방송보는디
-
진짜 1번이라도 따여보고 싶다
-
그냥 안타깝다 더 이상 뭐라 말 못하겠다 작년부터 만나뵙고 지냈는데 그냥 뭐라 할...
-
저거두개 없었으면 난 얼마나 비참하게살았을지 감도안잡힘
-
그래서죽을려고응응
-
수험커뮤답게 음울한 분위기가 쫙 깔려있어야 뭔가 보기좋음
-
인생이 너무 좆같다
-
병 걸리고 근2년째 공부도 못하고있고 고3인데 놀고만있는 저도 너무 싫고 대학갈...
-
그땐 별생각 안들었는데 몇년이 지난 지금은 6시그마를 보면 -6시그마가 먼저...
-
독전고를 울리며 나는 간다 아침으로!
-
죽으면 다 끝인데
-
이제 자야지 5
과제 끝
-
지금 햔대인들이 불행하다고 느끼는 원인 대부분을 논박하던데ㅋㅋㅋ 그것도...
-
진짜 자러갈게요 2
빨리 주무십쇼 님들도...
-
낭만 넘치는 두근두근 키스
-
씨발
-
ㅠㅠ 다들 조언 좀 부탁드려요ㅠㅠ 주변에 조언 구할 곳이 없습니다… 진짜 간절히 부탁드려요!
-
재종내에서 연애는 하더라도 재종안에서 번따-연애는……. 뭐 작은곳이면 몰라도 시대나...
-
중하위 1에서 높1로 올리려면 일주일에 몇 문제 정도 풀어야할까요 (쉬운4점~킬러만...
-
에휴다노걍ㅋㅋ
-
근데 키스하면 8
어떤 느낌임? 해본적이 없어서..
-
그렇다고 대놓고 공감 안된다는식으로 하면 매장당하니 억지로 공감하는척 해야하는데...
-
수학 노베는 뭐부터 공부해야할까요? 알려주면 1지망 대학 철썩 붙음 14
아예 노베는 아닙니다. 중학수학 인수분해 근의 공식? 이런거 다 알고 있고 원의...
-
빨리 자야겠네 뭔 연애는 연애여 씨발
-
정신적으로도 학습적으로도 훨씬 나을텐데 할방법이 없네
-
걍 선천적 결함인가 강기분으로 치유가 안되는
-
그냥 스트레스만 쌓이다가 폭발함 스트레스를 해소할방법이 아예 없어
-
연애하고싶어 1
막 못해서 미칠정도는 아니지만
-
연애는커녕 0
친구도없는데 사회성이없음걍
-
비중이라고 다들 생각하심? 그리고 스킨십이 관계 유지와 발전에 지대한 영향력이 있다고 생각하시나요?
-
그냥 때려치우고 혼자 사는것도 괜찮은것아닐까 언제부터 이리 사회성이 좆박았는지
-
낮에는 서로 공부관련 얘기나누고 날마다 떡밥 재밌는거 던져주는거 받아먹고있고 그...
-
출세하고 싶은 욕망에 눈이 멀어서 시중 문제들 짬뽕해서 자기 교재에 사용함 근데...
-
하루 40~1시간 운동 피부관리 눈썹관리 머리 깔끔 옷 깔끔 사회성좆박지않음...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ