[수리논술] Josephus 점화식
게시글 주소: https://hpi.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를 선물하세요.
-
시험 쉬운 학교 중간 망했지만 기말에 올린 경험 있으신 분? 0
오늘 통합과학 봤는데 말장난에 꼬여서 문제 2개나 날렸음 이번 시험이 진짜 너무...
-
통합사회 통합과학 궁금해지네요 ㅋㅋㅋㅋ
-
건물주이고 싶다 4
빡치네
-
꼭 한 두개씩 틀리는데 1등급으로 올라가려면 다 맞추는 실력은 돼야하나요?
-
공부합시다 2
윤세은입니다
-
2 이상의 모든 자연수는 한 개 이상의 소수들의 곱으로 유일하게 나타낼 수...
-
왤케 선지 납득이 안되는 비율이 점점 높아지는거 같지 ㅋㅋㅋ 작년 대비해봐도 좀 더 그런거 같은데
-
화작충이여서 그런거같긴하다만 암튼 점수자체도 omr기준 84/ 푼걸론 89고..
-
직전11덮풀고 서연고약골고루나왔는데 수능도 뭐 비슷하게 나옴(영어 억까만 아니었어도'..)
-
별로임? 지문만 개 길고 등급도 없고
-
'훈련병 얼차려사망' 지휘관들, 동료 피해자들에 합의 시도 반복 2
PTSD 진단 훈련병, 국선변호사 해임하고 합의 없이 강경 대응 (춘천=연합뉴스)...
-
41기 대면멘토링 서강대학교 편안녕하세요, 여러분의 꿈의 열쇠를 찾고 조여주는...
-
80분동안 푼 점수에 5점 꽁짜로 얹어준다고 하면 한다 VS 만다 (4점 아니고 5점임)
-
오히려좋아
-
짜증나네 그냥 국어 운에맞기고 수탐에 올투자 해버릴까
-
9덮 사문 3
사문은 보정보다 무보가 백분위 표점 더 높게 나오네;;
-
연논 하... 7
100점이 대략 높공 합격선 지금까지로는 딱 50% 충족 연화 제발...
-
∀, ∃ 이거 두개 새로알았는데 엄청난 응용이 가능한듯
-
이거 하나 치려고 직장 첫 휴가받고 나온 1인 ㅋㅋㅋㅋ
-
보통 한 기출 여러번 복기 하면 어떻게 하시나요
-
평가원 작수 3 올해 9평 3 6평 1 이감 90초에서 100 사이 왔다갔다하는데...
-
이건 왜 그런거지….. 국어 어케해야하나오
-
100점은 힘들 듯 10
인정해야.
-
땡벌,, 이제수업못듣겠어땡벌..땡벌..
-
9덮 6
수능 파이티이잉
-
평가원>더프>서바>바탕>상상>한수>이감 걍 개인적인 선호도임
-
이미지모 2회 1
한시험지에 절댓값 문제가 5개임... 22번는 절댓값이 3중으로 있음 크아아악
-
생윤 홉스 질문 3
“국민은 주권자의 어떠한 행위도 처벌할 수 없다” 이 선지가 맞다는데 주권자의...
-
응애 5
응애
-
이참에 쉴지 리모델링 기간 동안만 새로 끊을지 홈트라도 할지 고민이 됨 몸...
-
하 아침애 졸려서 앞에 두지문 시간 너무씀….
-
하시발섹스
-
??? 참고로 저는 65/96
-
수능때 높은 3 낮은 2 정도가 목표입니다.. 세지 공부를 하다 안하다해서요 9모는...
-
대한민국 Top7 종합대학 중앙대 합격을 기원한다 !! 0
고삼 재삼사오수님들아.. 제군들 고생이 대단히 많다 ! 대한민국 Top7 종합대학...
-
팔 힘 심각한거같은데 12
어제 마더텅 세권가서 팔사이에 끼고 걸어다녔는데 팔에 알배겼어요,,심각한건가요,,...
-
그저 계산뿐인 대수 문제라고 볼 수 있습니다 난이도 :2/5
-
내 모든 걸 걸고 말한다 본인 학교 화작이 1등급 인원이 ㅈ나 적거나 1컷...
-
난 왜 과탐으로 알고 있었지 완전 럭키비키
-
내일부턴 진짜 3
10시간이상 한다 진짜임
-
ㅋㅋㅋ 하지마셈 그거에 감정 쏟는 1%라도 여력이 있으면 그거 아껴서 수능에...
-
수업긑 6
돌아가자빠르게
-
하 ㅈ같은 지2련
-
윈터 귀엽다 2
-
같이 시킨 다른거는 다 왔는데 얘는 배송 정보가 아무것도 안떠요ㅠ
-
전세계 인구 모두한테 각각 100원씩 걷으면 8천억 이상의 자산을 축적 가능
-
설마했는데…“연예인까지 뛰어들었다” 실체 드러난 BJ 수입 1
[헤럴드경제=박영훈 기자] “BJ 수입, 이 정도였나?” 연예인들까지 잇따라...
-
확통
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ