[수리논술] 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를 선물하세요.
-
공정하게 실력대로 보상받아야 되는게 맞잖아... 수시는 백번 양보해서 그렇다 쳐도...
-
가을이였다 0
시발개춥다
-
어 왜 춥냐? 6
어...?.
-
농어촌이 엄청 크구나
-
아침부터왜저러는 1
'논리학을 논하는 나!'
-
https://orbi.kr/00069316804 이게...
-
망했다 2
깊은잠 1분 ㅋㅋㅋㅋ 아.
-
ㅇㅂㄱ 3
-
진짜?
-
혹시 이러는분 계신가요? 대처법좀 지난 3년 정도 힘든 일이 좀 많았었는데,, 그때...
-
헤헤 7시 방향으로 오줌 양갈래로 발싸
-
아가 기상 1
자고싶다
-
좋은 아침이에요 4
-
역시 자기객관화 joat과 날먹마인드는 농어촌 평균 ㅋㅋㅋㅋ
-
난 누구나 말할수 있는 자유가 있다고 생각함
-
아 잇올가기싫다 2
라고 생각했다가도 전적대(예정) 꼬라지를 보면 그런 생각이 싹 사라짐 ㄹㅇ 어차피...
-
그걸 비난하는게 잘못아닌가
-
공간이 풍선의 표면이고 풍선에 바람을 넣으면 풍선표면이 늘어나면서 풍선에 찍힌...
-
그렇군..
-
얼버기 13
-
ㄹㅈㄷ ㅇㅂㄱ 2
는 아니고 모기 세마리 잡고 좀만 더 자러갑니다...
-
얼리 버드 기상 5
좋은 아침
-
학원쌤이 풀어보라 하셔서 풀어봤는데 이감만 풀다가 이거 푸니까 시험지가 더 커서...
-
이공계, 특히 생명쪽 지망하면 무조건 국어 비문학 잘해야 합니다 1
분야별로 다르겠지만 AI나 바이오쪽은 공부하다보면 언젠가 반드시 논문을 많이 읽어야...
-
의대 2년조기입학하는사람 유튜브보니깐 조금 있던데요 2년조기입하면 과외는 못하겠죠?...
-
요즘 마스터들 불매운동 중이네요 할 만큼 하고 하직합니다..!
-
안자는사람 2
너무놀아서 생활패턴 망했다.. 그냥 ㅈ같다ㅏ
-
Ky 정시 농어촌으로 간 사람이 일반전형으로 쓰면 어디대학가나여?
-
이제서야 언매고정적으로 다 맞기시작..! 과연 이게 이득일까
-
아 너무 속상하다
-
불키고 과제한다 시부레
-
이거 어케빼지?......... 슬슬 평균 넘을거같은데 야식을 줄일까요 아니면 수능...
-
고2 수학 1
김기현 파데킥오프 하고 아이디어 듣고 있는데 제가 고2 9모 수학 6등급인 너무...
-
얘만 돈받으려고 않았을거 같긴 한데 솔직히 두창이도 정부 당 동원해서 여론선동...
-
오르비잘자 5
-
머가 좋을까요 시간상 하나만 할 수 있을듯해서
-
최애 정진솔이던 극성 닰붕이었는데 파생그룹인 아르테미스나 루셈블은 뭔가 그때 그...
-
기하 선택 작수 92 / 9평 96
-
너무 힘들다 사실 그냥 다 지치고 버거운 느낌 새벽이니까 가짜 힘듬이겠지
-
도박묵시록 카이지 슈타인즈게이트 데스노트 이런거 되게 재밌게 봤고 아인...
-
문학계속 기출위주로 공부하는데 계속 시간이 빨리거나 선지가 깔끔히 안맞아 떨어져...
-
원래 온라인에서 무료로 다운받을 수 있었는데 갑자기 바껴서 교사만 다운로드 할 수...
-
원정에서 토트넘 현실이 이랬는데 그 분 사라지니 ㄷㄷㄷㄷㄷㄷ 대승 손흥민 있었으면...
-
고2 아수라 0
정파인데 들을까요?
-
교과서는 에너지띠 이론 그냥 파울리의 배타원리로 퉁치고 조국광복회도 북한이...
-
미대 입시생이라 이쪽밖에 모름 이대 미대로는 상위권인디.. 서울대 디자인과 넣는...
-
텐하흐 나가 ㅗㅗ
-
알바하면서 내 또래 서양인지 유렵인지 모르겠는데 백인 여자들 손님으로 오면 너무...
-
지금 반토막임 코묻은돈 용케 모아서 셀트리온에 50넣었는데 잠깐 40%찍고 이후로...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ