[수리논술] 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를 선물하세요.
-
대석열의 운명은?
-
될때까지 하면 그만이야
-
25 4규 시즌 1 풀고 24 커넥션 다시 푸는데 2년째 김기현 추종자라 그런지 더...
-
난 왜 이걸 내 손으로 선택해서 하고 있는지 모르겠다
-
ㅇㅇ
-
우리학교 커리큘럼 ㄹㅇ 뽀뽀마렵다 정시로 돌렸는데 수1밖에 안되어있으면 얼마나...
-
오호
-
조 바이든 미국 대통령이 대선 레이스에서 하차하는 쪽으로 설득될 수 있을 것으로...
-
내가 트럼프라면 0
모든 트럼프카드에 얼굴박게하고 프리미엄 붙여서 팔거임
-
근데 동네에 독재학원이 없어서 8to10 30분 걸려서 가야 됨 갈 말..?
-
공스타 1
라도 해볼까 독재에 있다가 독서실로 오니까 강제력이 없어서 그런지 플래너도 안...
-
올해 수험생들 난리나겠네 대석열 탄핵까지 가능할지도 ㄷㄷ 아직 나이로는 고2라 별...
-
내신대비임 근데 어렵게나오긴할듯 시간이없음 생1유전은 개념만 알고 문풀은 노베임...
-
하. 고민중독 12
수시로는 경북부산이 적정인데 모고는 중경외시 뜨거든녀 이거정시파이터로 돌랴도될까요?...
-
진학지도 관련 소식지에 선배 후기로 수시 동국대가 자랑스럽게 써있을정도던데 ㅈ반...
-
진짜 힘드네
-
고양이 털 규ㅣ찮아서 정리 안했더니 고양이 됌..
-
고등학교 어디 나왔냐고 물어보시면 솔직하게 대답하긴 할건데 안물어보시면 안말해도 되겠죠?
-
주한미군 감축당함? 잘 몰라유
-
의대 모집정지 논란 해결되는거 아닌가?!?!?!? (해결안되는거암)
-
문학을 기준으로 약간 차이가 있음. 피램은 감상 능력도 중요하지만 선지 판단하는...
-
작년에 내신으로 개념 한번 돌리긴 했었는데 리밋 건너뛰고 임팩트해도 괜찮을까요?
-
7덮 수학 1
러셀에서 응시한 현역입니다 국어는 망해서 ㅎㅎㅎㅎ… 미적 30번 붙잡다가 22번...
-
네?
-
한국 올림픽 단복에 "죄수복 같다"…중국서 조롱 이어져 1
2024 파리 올림픽이 일주일 앞으로 다가온 가운데 최근 공개된 한국 선수단 단복을...
-
범준쌤이 28번에서 적분상수 붙이는 부분적분이 기출소재라고 하셨는데 무슨기출인가요??
-
적분 k/n=x -> 1/n=dx 이거 왜 이렇게 되는건강요?? 1
조교님이 설명해주셨는데도 이해가 안가서 울고싶습니더.... .....
-
4명 모집, 입학등록자 총점 평균 967 표준편차 19점 학생부등급 2.7등급...
-
멘탈 터지네 6
하 나만 왜 안 되지.. 남들은 잘 되고
-
일반고 3점대 후반이고 생기부는 2학년 1학기까진 챙기다 놨음 대략 뭐 나올 거 같음??
-
[분석]수능/모의고사 기출 "정약용"은 몇 번 나왔을까? 0
(개인의견 다수 첨가) 오답노트 중요하냐 안하냐 말들 있었지만 , 나는 국어가 가장...
-
제발 거부권때려라 ㅋㅋㅋ 재의결 부결 가자
-
오늘 아침 일어나서 봤더니 원래 돋보기랑 위치 바뀌었네 뭔가 불편하다
-
히히 똥 발싸 1
히히 발싸!!!
-
원래 항상 백분위 98 밑으로 안떨어졌는데 어느순간부터 슬럼프가 온건지 독서 한...
-
지이잉~하러 호주 가야지 ㅋ 같은 건 너무 말이 그렇긴 한데 ㄹㅇ 기술 배우는 게...
-
선거구 저렇게 나오지도 않는데 참 이런거나 풀어야한다니
-
그냥
-
농어촌, 지균, 한부모, 기초생활, 재외국민... 그래 다 좋은 거 알겟어 근데 왜...
-
대인라 잇올 0
잇올에서 대인라 듣는 분들 진짜 그 링크 부탁드려서 그거 통해서 들으시나요? 접속...
-
아파트 독서실 청소를 안해서 예전 책이 쌓여있는데 28
내 현역 6모 시험지 있네 추억이다 ㅋㅋㅋ
-
ㅈㄱㄴ 작년에 다녔던 센터는 됐던 걸로 기억하는데
-
과는 화공이요 인풋은 요즘 비비는 거 같고...위치, 인식 말고 아웃풋만 고려했을 때요
-
수능이 4개월 안팎으로 남았는데 저희 친할아버지께서 중환자실에서 병마와 싸우시다...
-
원래 하루면 왔는데 ㅜ.ㅜ
-
의대 모집 중지될 일 없지 않음?
-
풀어볼만하려나
-
쉬는시간에 한 번 들어가보고 싶다니까 절대 안 된다던데 원래 이런가요? 작년에...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ