공학계열 3번

[문제 3-1] 참가자 수가 $\displaystyle 2n$명일 때는 짝수 번호를 가진 사람들이 1라운드에서 탈락하게 된다. 참가자 수가 $\displaystyle 2n$명일 때 1등을 차지하는 사람의 번호를 $\displaystyle k$라 하자. 1라운드가 끝난 후에 이 사람의 위치는 앞에서부터 $\displaystyle \frac{k+1}{2}$번째일 것임이 분명하다. 그런데 이 상황은 참가자수가 $\displaystyle n$명일 때와 정확히 일치한다. 문제의 조건에서 참가자수가 $\displaystyle n$명일 때 $\displaystyle m$번을 가진 사람이 1등을 한다고 하였으므로 $\displaystyle \frac{k+1}{2}=m$인 사람이 1등을 하게 될 것이다. 따라서 $\displaystyle k=2m-1$이므로 참가자 수가 $\displaystyle 2n$명일 때 1등의 1라운드에서의 위치는 $\displaystyle 2m-1$번째이다.

[문제 3-2] [문제 3-1]에서와 마찬가지로 참가자 수가 $\displaystyle 2n+1$명일 때 $\displaystyle k$번째의 사람이 1등을 하게 된다고 하자. 1라운드에서는 1번과 짝수번호를 가진 사람이 탈락하게 되므로 1등을 하게 될 $\displaystyle k$번째 사람은 1라운드를 마친 후 $\displaystyle \frac{k-1}{2}$번째에 서게 된다. 또한 이 때 정확히 $\displaystyle n$명의 사람이 남게 된다. 문제에서 $\displaystyle n$명의 참가자가 존재할 때 $\displaystyle m$번째 사람이 1등을 하게 된다고 하였으므로 $\displaystyle \frac{k-1}{2}=m$이 되는 사람이 1등을 하게 된다. $\displaystyle k=2m+1$로 정리가 되므로 결국 $\displaystyle 2n+1$명의 참가자 중 $\displaystyle 2m+1$번째 사람이 1등을 하게 됨을 알 수 있다.

[문제 3-3] 참가자가 총 $\displaystyle n$명일 때 마지막에 1등을 하게 되는 사람의 번호를 $\displaystyle f(n)$이라 하자. 이전의 두 문제로부터 다음의 두 식을 이끌어 낼 수 있다. $\displaystyle f(2n)=2f(n)-1,\ f(2n+1)=2f(n)+1$

다음과 같은 과정을 거쳐 $\displaystyle f(2012)$를 구할 수 있다.$\displaystyle f(2012)=2f(1006)-1=4f(503)-3=8f(251)+1=16f(125)+9$$\displaystyle =32f(62)+25=64f(31)-7=128f(15)+57=256f(7)+185$

인데 $\displaystyle f(7)=7$이므로 $\displaystyle f(2012)=256\times7+185=1977$이다.