[수리논술] Josephus 점화식
게시글 주소: https://wwww.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를 선물하세요.
-
3나오긴했는데 4로 봐도 되는 수준의 허수임 걍 마더텅이나 n기출 같은 기본 기출서가 더 괜찮을까용
-
스카 화장실 모기 2마리 잡음
-
200 넘게 벌었었는데..
-
최면 9
...
-
이과인데 수학 3~2등급이 목표인데 확통을 해야할까요?
-
'포메인' 0
-
반수반 문자가 안오넹 떨어졋나 ㅠ
-
여긴 헬스장 코치님들도 무섭게 생겨서 웨이트존도 깔짝거리다가 걍 사이클만 타고 잇음…
-
미적하고 지구,사문 조합으로 지방국립대 기계공학과 갈 수 있을까요.....?...
-
지금까지 드릴 543했고 다음엔 뭐하는게 좋을까요 이해원? 설맞이?
-
고능아 ㅇㅈ 2
-
개어렵다는 평이 좀 있는거같은데 딴거부터 하고 하는게 나을까요? 모고 2등급 중반정도 나옴 ,,
-
25 시즌1 1컷 아는사란ㅁ
-
캬~~
-
진짜 오랜만이네 2
다들 하이
-
ㅈㄱㄴ 한대부고 국어국문 지망 학생입니다 4.2로 인서울 가능할까요...
-
돈 많이 모으는 편임?
-
솔직히 대구 살면 서울대 버리고 경북대 갈 수 있는 거 아님? ㅇㅈ?
-
천만덕 가쥬아
-
국어 언매 추천 0
고2인데 방학때 하려고하는데 고1 때 내신으로 열심히 해서 유베입니다 근데 거의 다...
-
뉴깅이 3분휴식 5
넵..
-
궁금궁금
-
다들 수학 n제 어떻게 얼마나 푸시는지요…? 현우진 드릴을 풀려고 했는데 작년것도...
-
스텝0인지 1인지는 안풀거임 기본예제 같은거
-
대학생이 벌면 잘 버는 편인가
-
이러다가 또 망하겠다
-
오분휴식 1
아따 수학 재미지다잉
-
(경품O) 간단한 설문조사 참가 해주실 수 잇나요.. 6
세특 때문에 설문 조사 빠르게 해야하는데 그냥 해달라 하면 아무도 안 하실 것...
-
내마위 2기 4
설렌다
-
시대갈까걍
-
독재학원 조교 어떰? 12
해보신분들 계신가요? 어때요?
-
컨설팅은 보통 듣기좋은말 해준다는데 거기서 비교과 약한편이라하면 진짜 약한건가요...
-
취업시장은 완전히 ㅈ망했고 이제 AI 노동력/직업 대체로 더 떡락할텐데 어디 뭐...
-
갑자기 장원영이 고백해버리면 뭐라고 거절해야하지…
-
잘 안써서 팔아요 쪽지주세요 양도도 되고 대여도 됩니다
-
죄다 비호감이나 ㅂㅅ애 투표했네 ㅜㅜ
-
놓쳤네ㅠ
-
저처럼 활동하면 3
벌점 안바듬요
-
사실 궁금한거 물어보려고 가입했는데 문제집이나 질문올려도 대답해주시는분들은 정말...
-
벌점이 하나도 없다니 15
역시 난 유익한 글만 쓰는 클린유저
-
엄마가 뭐라 안하네 ㅋㅋ 이제 해탈의 경지에 오른건가
-
내일 광화문 교보 가서 사오려구요
-
도와주세요 제발 3
제가 2학년을 잘 다니고 중간 성적까지 괜찮았는데, 몸에 큰 이상이 생겨 수술을...
-
메가랑 이투스 패스 있습니다 1타는 글씨가 더러워서 못알아 먹겠고 2타는...
-
악재가 어휴 3루 누구돌리지
-
시아와세나하이니낫타아토데
-
나도투표해조>< 24
으헹헹
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ