[수리논술] 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
후엥
-
대댓은 안 달고 글을 많이 써서 그런듯 글은 50덕코라서
-
재수학원 다닐 때 선생님께서 학원에서 6모 보게 해주니까 학교에 신청할 필요 없다고...
-
연애만 못해봤지 진짜 많이 좋아했던 여자애 이사가는날 세상 서럽게 울었어... 걔랑 꽤 친했는데
-
현정훈 단과 물1 진도 어디까지 나갔나요? 그리고 라이브반 신청하려고 하는데...
-
러셀가서 1교시 2교시 내리잤던 기억 나네
-
연락 보내면 그 사람이 기분나빠 하지 않을까...
-
왜투데이가 400 산화된 혁명가에게 갈 투데이가 나한테 오나
-
뜯지도 않은 새거에요 반값 택배로 택배비 포함 9000원에 드릴게영 시중가보다 훨씬...
-
~~
-
투데이 5에서 40까지 올랐네 호달달
-
해냈다해냈어 1
두산이해냈어
-
오르비 ㅇㅈ 특 27
애매하게 생기면 그냥 ㄱㅁ 달고 잘생기면 욕박고 예쁘면 팔로우함
-
여붕이 ㅇㅈ 16
오빠들 내 포니테일 어때?
-
허허,,,
-
ㅇㅈ메타돌면 나도 하고싶음.. 옯라방을 한번 해야되나
-
루프탑 풀파티 느낌 구도에 존잘남이었는데 이름 까먹었네
-
문붕이 조언좀 해주삼 11
미적사탐이라 확통 노베임 연대 가서 성불했다고 생각했는데.. 요즘 갑자기 다시...
-
님들아 2
내가 왜 기만인데
-
살면서 제일 아팠던것들 18
1. 발목 인대 2개 파열 2. 코로나 19 3. ㅍㄱ 수술 마취 주사... 4....
-
나 명조 하느라 못 봄 30분만 이따 하자..
-
ㅇㅈ사건의 진상 2
https://orbi.kr/00068261718/%EC%A7%84%EC%A7%9C-...
-
모쏠특) 2
화가 많음
-
장?발 8
-
장발'장 이 될 거야
-
모래주머니 달고 수학 백분위 99 받았던 나 자신이 대견하군아 진작 먹었으면...
-
제발나가
-
야붕이 인증은 해줄 수 있음
-
ㅛㅣ이고 기만은 기만이라고 써요
-
죄송합니다 4
모 기하러에게 사과하겠습니다 도형문제보고 한건데 날조당했어
-
여붕이들아 해줘
-
쉬웠나요,, 88점이면 그래도 잘본편인가요? 정답률이 막 그렇게 낮진않네용 박종민쌤...
-
여붕이 ㅇㅈ 15
제대로 찍은 사진이 없네 ㅋㅋ
-
이거 쪼개니까 초반부? 약효가 너무 약한데 이미 몸무게보다 용량이 더 커서 늘릴 수가 없음 하아
-
아 미적분때메 놓쳤다
-
눈 아파 6
다래끼 시발 샛기
-
필통어떰? 8
-
거 좀 자라 4
너무 많다
-
어떰
-
제 ㅇㅈ 반응입니다 25
이제하라고하지마세요
-
지구과학 개념 기출 열심히 한 거 같은데 도저히 안풀리네요…
-
안경 받침이랑 나사 빠지고 나사 잃어버림
-
ㄱㅁ 4
ㄱㅁ
-
ㅇㅈ 10
-
어떤분이 내신문제라고 질문하신문제.. 비주얼왜이럼
-
첨보는데 ㅋㅋ
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ