도전 과제 : 요세푸스 문제

Created on July 13, 2021

2021   ·   education tutoring mathematics korean   ·   education

본 자료는 인공지능을 활용하지 않고 작성되었음을 알립니다.

The Josephus Problem

요세푸스 문제는 1세기에 살았던 역사학자 플라비우스 요세푸스(Titus Flavius Josephus, 37 – c. 100)의 이름을 따서 만들어진 문제이다. 요세푸스와 요세푸스의 병사 $40$명, 총 $41$명이 로마 군에 의해 동굴에 갇혔는데, 이들은 항복하기보다는 다함께 자결하기로 결정하였다. 이들이 자결하는 방식은 아래와 같았다. 마지막까지 생존하는 사람은 과연 누구일까?

출처: The Josephus Problem, Numberphile

https://www.youtube.com/watch?v=uCsD3ZGzMgE

  • 멈춰야 할 지점들

    • 2:07 - 요세푸스 문제의 답을 $n=5, 6, 7$의 경우에 대해 구해보자. 어떤 패턴이 보이는가?

      $n$명의 사람을 앉힌 다음 $1$번부터 게임을 시작할 때, 최종 생존자의 번호를 $w(n)$이라고 하자.

      $n=5$일 때 $w(n)=3$

      $n=6$일 때 $w(n)=5$

      $n=7$일 때 $w(n)=7$

      $w(n)$의 값은 항상 홀수이다.

    이유: 첫번째 라운드에서 짝수 번째 사람은 모두 죽기 때문에, 이들은 최종 생존자가 될 수 없다.

    • 2:55 - 요세푸스 문제의 답을 $n=1, 2, \;\dots, 13$의 경우에 대해 구해보자. 어떤 패턴이 보이는가?

      아래 표에서 $13$ 이후의 수에 대해서 일반화해서 적어보자. $w(n)=1$이 되는 때는 언제인가?

      $n$ $w(n)$
      1 1
      2 1
      3 3
      4 1
      5 3
      6 5
      7 7
      8 1
      9 3
      10 5
      11 7
      12 9
      13 11
      14 13
      15 15
      16 1

    • 5:14 - $w(n)=1$을 만족하는 $n$의 패턴은 어떠한가? 이를 수학적으로 표현한 다음 증명해보자.

      $8=2^3$인데, $4$명을 죽이고 나면 다시 $4=2^2$명이 남고 $1$번의 차례가 된다. $1$번은 마지막까지 죽지 않고, 따라서 최종 승자가 된다. (출처: Numberphile)

      $8=2^3$인데, $4$명을 죽이고 나면 다시 $4=2^2$명이 남고 $1$번의 차례가 된다. $1$번은 마지막까지 죽지 않고, 따라서 최종 승자가 된다. (출처: Numberphile)

      추측

      $0$ 이상의 정수 $a$에 대하여, $n=2^a$일 때 $w(n)=1$이다.

      증명

      수학적 귀납법을 이용하자. $a=0$인 경우, $n=2^0=1$이고 이 경우 $1$번이 곧바로 유일한 생존자가 되므로 $w(n)=1$이다. $a=k$일 때, $w(2^a)=1$이라고 가정하자. $(\star)$ 이때 $a=k+1$인 경우, $2^{k+1}$명이 처음에 앉아 있는 상태에서 시작할 것이다. 처음 한 바퀴를 돌아 처음 인원 수의 절반인 $2^k$명이 남아 있는 상황이 되면, 다시 $1$의 차례가 된다. 이때 남아 있는 사람의 번호는 $1, 3, 5, 7, \;\dots, 2^{k+1}-1$이 되는데, 이들에게 새로운 번호 $1, 2, 3, \;\dots, 2^k$을 부여하자. 그러고 나면 가정했던 $(\star)$과 동일한 상황이 된다. 따라서 가정 $(\star)$에 의해 $w(2^{k+1})=w(2^k)=1$이 되고, 수학적 귀납법에 의해 모든 $0$ 이상의 정수 $a$에 대하여, $w(2^a)=1$이다.

    • 7:02 - 일반적인 경우에는 어떠한가? 이에 대해서도 수학적으로 표현한 다음 증명해보자.

      $13=2^3+5$인데, $5$명을 죽이고 나면 $8$명이 남고 $11$번이 시작하는 사람이 된다. (출처: Numberphile)

      $13=2^3+5$인데, $5$명을 죽이고 나면 $8$명이 남고 $11$번이 시작하는 사람이 된다. (출처: Numberphile)

      추측

      $0$ 이상의 정수 $a$와 $0\le l<2^a$인 정수 $l$에 대하여, $n=2^a+l$일 때 $w(n)=2l+1$이다.

      증명

      시작한 이후 $l$명이 죽은 상황을 생각하면, 그때는 $2l+1$번째 사람의 순서가 된다. 그런데 남아있는 사람이 $2^a$명이므로, $2l+1$번째 사람에게 $1$번을 부여하고 생존한 나머지 사람들에게 순서대로 나머지 번호를 부여한다고 하면 그때부터는 $2^a$명이 남아있는 첫번째 상황으로 바꾸어서 생각할 수 있다. $2^a$명이 남아 있을 때는 처음 칼을 휘두르는 사람이 이기기 때문에, 최종 생존자는 $2l+1$번째 사람이다. 따라서 $w(2^a +l)=2l+1$이다.

    • 13:35 - 어떤 자연수 $n$을 이진법으로 나타낸 다음, 맨 앞 자리 숫자를 맨 뒷자리로 옮기면 $w(n)$이 됨을 보여보자. (예를 들어, $n=41=101001{(2)} \rightarrow w(n)=17=010011{(2)}$)