[수리논술] 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를 선물하세요.
-
내일도 4시에 일어나야
-
휴면계정 된다고 해서 로그인해봄;
-
가나다순 3칸3칸3칸 잭팟메타로 가자
-
후후 내 태그를 보시라
-
연대 빵꾸 5
시간대별 경쟁률 이정도로 낮았던적이 있나요?? 진짜궁금해서 물어보는건데 이정도면...
-
누가 요청해서 배치표 찾아보다가 여기까지 옴;
-
뭔가 멀리서 바라보면 귀여운데 나한테 다가오면 뭔가 무서움 무섭다기보다 거부반응을...
-
- 20대중후반에 취업한 애들은 이미 대리이상 달고 난리남 - 다들 결혼하고 난리남...
-
?
-
댓글 수정하면 오르비 스티커 단거 날아갔는데 이제는 유지된 상태로 나오네
-
국어 너무 안해서 불안해져서 뭐라도 해야뎃음
-
칠전팔기 미2
-
여기 올리면 구독과 좋아요 많이 눌러줄거지?
-
89년생 1
89
-
문과 수학 1
고정 1이고요 가끔 기출풀다가 미적분 속도 나와서 좀 꼬아서 낼 때도 잇더라구요ㅗ...
-
와우 여기 살아있네요 22
근데 이상한 게 많이 생겼네요
-
몇년만의 로그인인건지...그런데 쪼렙이네요.. 다른분들은 더... 분발하세요 예전에...
-
안녕하세요 이번에 6야반 유시험전형으로 지원했는데 둘다 물먹었네요 강대는 별관...
-
친구들이그냥 수원대 전기가라고 한경대도 전기전자제어공인데 어떡하죠..
-
아 이거 4
과거 흔적 좀 없애야 하는데 fail...
-
안주무시고계신분들.. 33
몇년생입니가?1. 98년 이상 귀요미.. = 십팔2. 97년 = 193. 96년 =...
-
아놔 열심히 댓글달고 있었늗네 갑자기 글이 사라졋다해가지고글쓴이 : 오빠, 머하고...
-
제목보고 어그로끌려서 오셨으면 ㅈㅅ 사실 오징어인데 어려보임 평소에도 어려보인단...
-
헤헤 이제 여기에 거주하던 사람들은 대학생보다 대졸생이 더 많아졌지(...)...
-
To. 1
여기는 과제의 쪽수가 늘지 않는 새벽에나 오는 곳이었는데, 쌀쌀한 일요일 아침에...
-
2014년 하반기 신입사원 채용합니다. #학력 : 무관 #나이 : 무관 #근무시간...
-
클래지콰이 lover boy클래지콰이 sweety클래지콰이 sweety (cosmo...
-
오랜만에 예전 생각들이 나서 와봤는데아무도 안오는 공간이 되었겠지그 때 그 친구들...
-
아직 있네? 0
와우
-
언수외탐 백분위 96 98 87~88 99 99 성대인문 안대나요 ㅠㅠㅠ안댄다면...
-
내일 과외 미팅때문에 간만에 들어왔는뎈ㅋㅋㅋㅋㅋ 아 진짜 여기도 추억이다다들 카톡에서 ㅂㅂ
-
안녕하세요 군대에서 공부중이 장수생입니다...고민이 많습니다. 1
안녕하세요 군대에 늦게나마 입대해서 26살 9월에 전역하는 말년...
-
에비앙이뭐임 3
왠에비앙
-
이과 삼수생인데 진로에 대한 막막함이 크네요,, 도와주세요,, 1
재수 하면서 망했죠 물론 제가 열심히 하지않은 것은 압니다. 그런데 저는 왠지 수식...
-
두둥
-
나엄청오랫만에 4
글쓰고감ㅋ 역시나는뉴비임ㅋ
-
2013학년도 정시모집 전형일정자세히 보기구분기간원서접수 가, 나, 가·나군...
-
미리미리 검증을 거쳐 폐인으로 편입시킬걸그랬나?ㅋㅋㅋ.... 이런거 필요없나;
-
ebs 파이널 수리가 14번 ㄷ번 행렬좀 알려주세요... 3
영행렬이 아닌 행렬 A의 제곱은 0 .ㄷ ) A=B제곱 을 만족하는 행렬 B는...
-
1년치 모의고사 성적인데 객관적으로 수능에 어느정도의 점수가 나온다ㅗ 할수 있나요? 2
원점수-백분위 순작년수능 : 언어(84%) 수가(94%) 외(4등급턱걸이)...
-
웬일 2
여기 아직도 있니 헤헤이런 식상한 대사 ㅠ_ㅠ 과제하기시렁 라ㅜㄴㅇ ㅓㅏ룬아ㅓㄹ...
-
제목은 거창하게 썼지만 아침에 도서관 출첵 정도 같이 했으면 좋겠습니다. 나이 과...
-
음.. 저는 현재 인서울 중상위권 4년제 대학 휴학중에 있는 사람인데요08학번...
-
여기, 아이핀 인증등 가입하기 귀찮아서 친구 아이디로 올립니다. 어디 마땅히...
-
나 입대하고 처음 들어온 것 같아
-
2012학년도 재수 실패한 놈임삼반수 하려고 맘먹었음상근예비역이 떳음 입영날짜...
-
작년 8월에 전역후에 올해 독재로 대학가겠다고 꼴깝고 독재의 벽을 넘지 못한 23살...
-
08학번으로 화학과로 진학하고내가 이방향이 맞는지 방황하다가1년휴학하고 1년은...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ