[수리논술] 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
한다면 한다... 근데 죄송해요 누군가는 봤을 거 같음...ㅎ 사진이 업써
-
개인적으로 악감정은 없지만 아보카도나 이런 친구들 보면 멀쩡히 잘만 하던데 그런...
-
잘생겨도 못생겨도 불쾌함 굉장히 신기함
-
3분 안에 16
50000덕 모이면 함
-
제 성적은 아니고 사촌 성적인데 궁금해서..
-
안녕하세요. 코딩하는 알로스입니다. 최근에 제가 칼럼을 쓰는 일이 없이 간단하게...
-
의대면접기출자료 0
2021년까지 제작했습니다(즉 3년전자료) 제가 과외할때 학생들 면접복기시켜서...
-
오르비
-
좋아요 8
와 구독 알림설정까지
-
원해요...? 8
근데 전 원하지 않는 거 같은디 성의를 보여봐요
-
둘 중에 벼락치기 쉬운 과목이 뭔가욤
-
현역 화미물화 13143 재수 언미물화 12124 화학 버리고 사탐런 박을 것 같음...
-
ㅇㅈ은없슴디가
-
요아정 뭐먹 0
지
-
맞팔하고 가세요
-
15분까지 2
좋아요 15개 박히면 지금 찍은거 ㅇㅈ함
-
3분안에 16
좋아요 100개 넘으면 상탈인증함 ㅋㅋ 되겠냐
-
나같은 사람 뉴가 봐줌.. 그리고 넘 많이했어
-
운이라는게 수능만점 받아도 원원 cc가 설의 가는건 그해 수능 난이도 같은 지원자...
-
돌아와버렸다 18
이 입시판에.. 날 기억하는 사람은 아무도 없겠지ㅜㅜ
-
궁금
-
와 대박 0
잘 쓸게요 ㅠㅠㅠㅠ
-
여붕이 차례
-
????
-
18~20살때 역변하는 경우도 많은듯 동안 + 성인 되면서 자기관리 + 호르몬 변화...
-
이건 거짓말이야
-
키 150 8
몸무게 122 존못 남붕인데 인증해도되나요
-
한개틀리고 3등급 말이되냐고
-
ㅇㅈ 30
으악
-
고작 2분만에 찍힘 ㅋㅋㅋㅋ 정작 본인은 하고 아무것도 못봤음 ㅅㅂ...
-
ㅇㅈ 메타가 일찍 열리겠네
-
좋아요 눌러줘 1
https://www.orbi.kr/00068260525/%EC%A2%8B%EC%95...
-
너무 재밋엇슴
-
현실은 새터, ot, mt(모텔 아닙니다~), 축제 등등 술먹고 노느라 살이 더 불어남 ㄹㅇㅋㅋ
-
인증메타 열게요~
-
양승진>김기현
-
님의 성별은? 2
.
-
사실 본인 2
9년차 슼갈입니다 ㅇㅇ
-
존나 싫은데 그렇다고 월요일이 안 오는 건 싫어!!!!!!
-
누가 카드찍었는데 미소년 카드입니다 이랬는데 뭔 말임
-
안대!!!
-
토익독해 때문에 죽고싶습니다 진짜(독해 극복하신분들 부탁드립니다) 0
단어도 다 알고, 문장구조도 다 알아서 거품구 제거 할수도 있는데 읽어도 먼...
-
내 과톡방엔 암것도 안오는데 뭐지?
-
시험기간에 하면됨
-
수특 벅벅vs수능루틴 주간지 벅벅 마더텅 끝내서 이제 할거 찾아야함...
-
쓰니 어디살아? 6
제주특별자치도 제주시 우도면 연평리 "1557"번지
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ