[수리논술] 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를 선물하세요.
-
씨발 딸피를몇번이나놔주는거야
-
내가 못하는건 맞지만…
-
2는 아닌가
-
시발 조졌네 0
이걸 지네 채희상 박준빈뭐함
-
미적 백분위 94~96 정도 나오는데 10월15일에 시작해서 이해원n제 시즌2...
-
심찬우듣고 5에서 1ㄷㄷㄷ
-
“방법적 회의는 사유하는 ‘나’라는 존재의 확실성에서 출발한다. “ 가 왜 틀린...
-
시간이 없어서 그런데 거꾸로 공부하는거 어떻게 생각하세요 어차피 문풀이랑 실제...
-
입문 엔제 풀면 잘할 수 있을까요? 빨더텅 오답하고 있는데 여기서 너무 많이 틀려서요..
-
스토리로 대리만족
-
너무 좋아서 미쳐버릴것같다
-
육군 보직 2
은 그냥 랜덤인가요? 개인 시간 많은 보직 가고 싶은데
-
담원 개못하네 4
딸피 다놔주는게 3시드? ㅋㅋㅋㅋㅋㅋㅋㅋ
-
훠훠
-
그림 그려도 되나요..되나요..
-
제일 크게 일조한거 같지 않음? 뭔가 예전처럼 킬러 2개씩 넣어주면 1컷 다시...
-
멘탈 관리 2
님들아 억지로라도 행복하고 웃으셈 지금 다 힘들텐데 신나는 노래를 든던가 밝은...
-
논리규칙들을 가지고 논리적으로 사고하는건 계산기임
-
와 미쳤네 그냥
-
딸도 저지랄을 ㅋㅋㅋㅋ
-
정석민 문실정 2
따로 돈 더주고 구매할만큼 가치 있나요... 이렇게 품절일 줄 몰랐음
-
국어 듄스트라다무스 2~3강 복습 영어 스피드보카 day22 생윤 잘생긴윤리 23~25강
-
엔제 시간잡고 풀기
-
벌써 그 계절이라고?
-
3점이랑 4점 두세개 빼고는 손못대서 울었음 근데 원래 실력인거같긴해요 빨더텅...
-
앉아서 공부하는게 안맞는거 같아요 저 스스로 왜 나는 이렇게 불성실할까 생각을 정말...
-
할 때 된 거죠? 하사십 2 진행중인데 다 끝내고 들어갈까요 아님 실모랑...
-
수학이너무재밌다 사탐개념기출돌돌이하다보면 자꾸수학하고싶어짐 물론수학도잘못함
-
어느정도였을까
-
돌고도는프사 2
프사회전
-
사람의 유전 정답률 40프로 이상인 것만 하는거 어떤가요?
-
사설에서 절대로 따라할 수 없는 미친 퀄리티같음 만약 기억 지우고 그거 다시...
-
고2 정시파이터인데 곧 수2 시발점 끝나는데 1. 확통 시발점을 듣는다 2. 수1 뉴런을 듣는다
-
대치동에 고3/N수만 전문으로 하는 개별진도 학원 있나요? 0
1대1 과외는 부담되고, 고3/N수 전문으로 하는 개별진도 학원에서 실모 질문만...
-
모킹버드 기출 제작이 갑자기 안됩니다.. 비복원 추출이 불가하다고 뜨는데 어떻게 해야 하나요??
-
신성규쌤 해강 기대
-
안봤으면 좋겠다 히히
-
질문해드려요 4
댓달면 해드림 댓없으면 슬프게 그냥 갈 예정
-
무빙건?
-
오늘한거 1
네.
-
씹덕스러움을 첨가했습니다.. 양해 부탁드려요!!! (실화를 바탕으로...
-
9모 100받았고 드릴 4 5 (8~90프로 정도 맞혔어요) 커넥션 설맞이 풀었는데...
-
21 6모때 정철 관동별곡 비연계로 출제... 당시 연계교재에 사?속?미인곡...
-
왕잠시 본진에서 이탈좀 하겠소
-
초반 15초 진짜 지림... 코토하는 신이다...
-
쓸건 없지만 0
그냥 오답하다 말고 아무말이나 하고싶다.. 아무 할말은 없지만 할말없다는게 할말이다
-
우흥 우흥흥..
-
고딩때 친구랑 원서철때 마지막으로 연락했다가 오랜만에 연락이 닿았는데 내가 사복 간...
-
강의 듣기 귀찮아서 유기하고 시험 한번 풀어봤는데 61점 나옴;; 2급만 따면...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ