[수리논술] Josephus 점화식
게시글 주소: https://m.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를 선물하세요.
-
기만글이의도가아닌데.. 학교생활궁금한거암거나물어보세요
-
ㅇㅈ메타라도 돌았냐?
-
ㅇ
-
주식이 궁금해서 잠을 못 자겠잖아
-
가군- 1명중 1등 나군- 1명중 1등 다군- 3명중 3등 ㅅㅂ ㅋㅋ 다 꼴등
-
내일 할게요
-
무서워요
-
자러.갑니다. 이렇게.말하면.뭔가.나이든.사람.같지.않나요....
-
재밌게좀해보세요 2
제가심심해요
-
다들 ㅂㅂ 2
ㅂㅂㅂㅂ
-
508인난 일단 쫄튀함
-
아오 좀 취한다 0
집가서 씻고 자야지
-
1. Temu에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
오르비 끝
-
제가 가고싶은대학 못가면 분캠 등록하고 전액장학금 받고 그냥 1년내내 학교안다녀도...
-
아 배 1
총리
-
지움 6
개 쫄 려 흐아앙
-
1년만에 까네 학생 인증 안해도 돼서 걍 서울대 재학생이라 했음...
-
걍 ㄹㅇ 4점짜리 연습 하고 싶은데 4점(11~15)들 걍 양치기로 문제 많이...
-
학생 때는 ㅅㅂ 당연하지 ㅋㅋ 하고 풀었는데 이걸 설명하라 함.... 근데...
-
수능국어복기 9
나는 항상 번호순으로 풀었음 파본검사 후 독서에 경제 없고 철학 있어서 1차...
-
드릴 워크북<---걍 goat임 24수능2에서 6모 만점받기까지 딱 시중에 있는거는 이것만 풀었음
-
소통해용~ 13
-
잠이 안와요,, 내일도 독서실 가야 하는데
-
이거 맞는말이에여? 컨설턴트분이 해주셨던 말이랑 비슷한데
-
봐도봐도 너무 재밌네 오프닝도 마음에 딱들고
-
1. 연세대 문화인류 여긴 연세대에서 그나마 핵빵 가능성이 보이는 과라 넣음 소신...
-
안녕하세요 오르비 회원님들 문과 출신 30초반 아저씨입니다.. 단도직입적으로...
-
바로 옆에 쓰레기통 있는데..ㅠ
-
옯스타 맞팔해요 1
@orbihaku
-
동국대 경제 계속 6,7칸으로 최초합 뜨고 등수도 10후에서 20초 진동 했는데 이...
-
https://orbi.kr/00071046160/
-
근데 이제 입시도 잘 모르고 아는 사람도 없고 먼가 슬프다 ㅠ
-
미친새끼들이 역사 좋아하지도 않으면서 존나 더럽히네 나는 세계사도 했는데 동사까지...
-
원광치스나이퍼 0
푱푱
-
그래서다른거라도잘해보려고
-
나 진짜 너무 심심해
-
ㅈㄴ 마려운데 안잡히네
-
1. Temu에서 기존회원 신규회원 룰렛 이벤트함 2. 5만원 확정지급 링크 통해...
-
반도체트랙이 대상이 되는 학과가 전자공,컴공,화공,기공,물리,화학과라고 홈페이지에...
-
빌런스 컨설팅 0
엔젤스 논란이 있으니까 빌런스로 가는거임 ㄷㄷ
-
영상을 만들어오라 이거지
-
단거+단거=♡♡♡♡♡
-
내주변에선 건동홍도 거의 안보이는데 우리학교에선 그위로 열명도 못갔을듯
-
깨끗하고인프라가좋음
-
한양대 가고 싶다 한양대 가고 싶다 한양대 가고 싶다 한양대 가고 싶다 한양대 가고...
재밌네요ㅋㅋㅋ 그와중에 josephus소오름...
왜 뭔가 우리 학교 프린트에서 본거 같은 느낌이지 ㄷㄷ