[수리논술] 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를 선물하세요.
-
국숭 중심으로 써야할거 같긴한데 동홍 질러볼 수는 있을까요..?
-
같이 넣어볼만함가요
-
삼반수 고려중인데 내년에 선택과목을 바꿀까싶어서요 이번 2025수능 확통100점인데...
-
제발…
-
무려 과탐필수 중하위권이라 ㄹㅇ 어디까지 갈지 감도 안잡힘
-
맞팔 구합니다 0
ㄱㄱ
-
보통 논술 일반과 커트가 어느정도에요? 컴솦 쓰긴 했는데 논술하게 될 줄은 몰라서...
-
기출 2회독 마치고 1월부터 한주 한번 하려는데 찾아보니까 수학은 1월에 하프모...
-
정말 암담하네요 뭔가 팁이 있을까요???
-
상남자식 원서질 ㅋㅋㅋㅋ
-
연전전vs설전정 6
고거슨 과잠 대결이었구욘
-
어디가 더 재미써요? 두군데 다가부신 분들 좀 얘기 듣고싶넹
-
탈릅할까 7
현실에도 친구가 없고 여기서도 없네.. 탈릅해도 나 없어진 사실 조차 아무도 모를듯…
-
어디감? 둘다 ㄱㄴ하다면
-
아님 의대증원 고려해도 힘듦…?
-
받는게 나아요? 텔그 기준 70퍼 뜨던데 ㄹㅇ
-
미국 여판가
-
요즘 왜 안나옴뇨 트럼프 뽑힌김에 선서 한번 더 하면 안됨뇨
-
반수 고민 0
현역 23331인데 공부하느라 지쳐서 반학기동안은 놀고 싶은데 휴학하고 반수하면...
-
올1컷으로도 경제경영 택도 없네 ㄷㄷ 작년엔 성적 택도 없어서 폭난거만 알앗는데 이정도일줄은..
-
인터넷없었으면 내앞에서 입털수도 없는 좆밥새끼들이 기술의 발전덕분에 감히 나한테...
-
제가 언매가 87점인데 2컷이 85,86정도더라고요 근데 둘다 제 점수 기준 표점이...
-
과탐필수땜에 안날수도 있을거같음
-
돈보다는 0
마음이 내게는 더 와닿아~
-
면회 좀 와라 4
찰옥수수 아이스크림 400원임
-
야수의 심장으로 연경 서울대 고학부 간다 ㅇㅇㅇ
-
빠빠뇨
-
9평 33311이고 강남대성 스투와 강남대성 위업 사이에서 고민 중입니다. 강대스투...
-
제가 미적 선택자인데요 문제 3번 (확통)은 못풀겠어서 그런데 문제3번 안써도 합격 가능성 있나요?
-
555 조합 간다 막바지 칸수 기준으로 말하는거에요… 지금은… 믿지않아
-
잠깐만 자고 다시 공부할게요
-
ㅜㅜㅜ
-
현역들을 위한 글이다. 기초 예시) 한 옯붕이가 백분위 96 96 1 96 96 을...
-
토익 공부 0
수능영어 1 거의 나오고 가끔식 2뜨는 실력인데요 이정도 실력이면 기출만 풀고...
-
24학년도 수능 미적 88점입니다 공통 22번 1틀 선택 28 30 2틀 해서 88...
-
우린 남이니까 0
가조쿠가 아니니깐
-
트랙길이는 아마존 익스프레스랑 비슷함.(500m?600m) 중간에 힘들면 쉴수있음,...
-
커뮤에선 모두 게이지 뭐 게이게이야...
-
광명상가 인가경 삼여대 가능할까요? 자연계, 공대 지망합니다 그리고 이번주에 동덕...
-
가정 불화라던가 기타 등등 이유로 독립하실 분들 앞으로의 삶을 응원합니다 다들 독립...
-
대 범 준 신 범 준 황 범 준 ㅋㅋㅋ
-
사실 여사친도 없고 수능 이후로 개백수처럼 방구석에 쳐 박힌 채로 아무 것도 안...
-
걍 ㅂㅅ같은 애니프사 달면서 역한 말투에 이상한 글만 올려도 뭐라 안하는데 게이는...
-
ㄹㅇ 국어 1틀 좀 아깝다....... 100맞았으면 더 좋았을거같음 과외같은거 할때나 조교할때
-
주관식 다 맞는거 자신있는 강사 없을꺼임 시간압박속에 알아도 틀리는 경우 많음
-
욘세이과잠 2
-
현실세계에서 노느라 못 봤어요
-
씹덕들 2D에서 여자그려놓고 남자라 우기는거 뇌이징 돼서 그런 컨셉 잡는거지...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ