서론

101은 왜 101일까?

\(10^21+10^10+10^01=101\)이니까.

101이 알고보니 4진법으로 나타낸 수라면?

\(101_{(4)}=4^21+4^10+4^01=17_{(10)}\)

그럼 일반화하면?

\({b_kb_{k-1}\dots b_1b_0}_{(p)}=\sum_i^kb_ip^i\)

\(p\)는 자연수일 필요가 있을까? → 이것도 생각해볼 주제이다. 자연수가 아니라면 어떤 수의 \(p\)진법 표현은 유일하게 나타나는가? 수능 끝나고 생각해보자

사실 어떤 수의 \(p\)진법 표현이 유일한지 아닌지는 꽤 중요한 문제가 될 수도 있으나, 후술할 문제 풀이에서는 \(a_2\)진법 표현을 원래 알던 10진법 수로 바꾸기만 하지 10진법 수를 \(a_2\)진법으로 바꾸지 않으므로 문제 없다.

본론

$$n=:{b_kb_{k-1} \dots b_1 b_0}_{(2)}\\ c:=[1,-2]\\ D:=[0,a_1]$$

\(n\)의 2진법 표현, \(c,D\)를 위와 같이 정의하자. 참고로 \(c[0]=1 ,\,c[1]=-2\)이다. 즉 c와 D array의 index는 왼쪽부터, 0부터 시작한다.

그러면 \(a_n\)은 다음과 같이 쓸 수 있다.

$$a_n=a_{{b_k b_{k-1} \dots b_1 b_0}_{(2)}}={D_{b_k}C_{b_{k-1}} \dots C_{b_1} C_{b_0}}_{(a_2)}$$

\(a_1, a_2\)도 넣어보고 일반적인 경우(\(n>2\))를 생각하면서 왜 위의 수식이 성립하는지 곱씹어보자.

이제 \(a_8-a_{15}=63\)을 해석해보자.

$$a_8=a_{{1000}_{(2)}}={D_1 C_0 C_0 C_0}_{(a_2)} \\ a_{15}=a_{{1111}_{(2)}}={D_1 C_1 C_1 C_1}_{(a_2)} $$

\(a_8-a_{15}\)을 계산하기 위해 각 자리수별로 빼준다. 유치원 때 십진법 뺄셈 배운 대로 똑같이 하면 된다.

$$\begin{align} a_8-a_{15}&={(0)(C_0-C_1)(C_0-C_1)(C_0-C_1)}_{(a_2)}\\ &={0333}_{(a_2)}\\&=3(a_2^2+a_2+1)=63 \\ &\therefore a_2=4 , -5 \end{align}$$

표기법이 좀 근본이 없는 건 나도 아는데 미적분학1+ 책에는 이런 말이 써져 있다. "수학은 형식에 구애받지 않는다". 혹시나 해서 보충설명하자면.. 첫번째 수식은 \(a_8-a_{15}\)를 \(a_2\)진법으로 나타냈을 때 0,1,2번째 자리수가 \(C_0-C_1\), 3번째 자리수가 0이라는 뜻이다.

이제 (가) 조건에 \(n=1\)을 넣고 \(a_2\) 값을 넣어 \(a_1\)을 계산해보면, \(a_2=4, a_1=\frac{3}{4}\)만 되는 것을 확인할 수 있다.

이제 \(a_8,a_1\) 구해서 나눠주면 답이 나온다.

$$\begin{align} a_8=a_{{1000}_{(2)}}&={D_1C_0C_0C_0}_{(a_2)} \\ &=(\frac{3}{4})(1)(1)(1)_{4} \\ &=48+16+4+1\\ &=69 \end{align}$$

\(a_8/a_1=69/(3/4)=92\), 답은 2번이 된다.

요약

$$n=:{b_kb_{k-1} \dots b_1 b_0}_{(2)}\\ c:=[1,-2]\\ D:=[0,a_1]$$

$$a_8=a_{{1000}_{(2)}}={D_1C_0C_0C_0}_{(a_2)}\\a_{15}=a_{{1111}_{(2)}}={D_1C_1C_1C_1}_{(a_2)}\\$$

$$\begin{align}a_8-a_{15}&={(0)(C_0-C_1)(C_0-C_1)(C_0-C_1)}_{(a_2)}\\&={0333}_{(a_2)}\\&=3(a_2^2+a_2+1)=63 \\&\therefore a_2=4 \;or\;-5 \end{align}$$

$$\begin{align}a_8=a_{{1000}_{(2)}}&={D_1C_0C_0C_0}_{(a_2)} \\&=(\frac{3}{4})(1)(1)(1)_{4} \\&=48+16+4+1\\&=69 \end{align}$$

$$a_8/a_1=69/(3/4)=92$$

답은 2번

참고(흥미 있는 사람만)

Knuth 아저씨가 쓴 구체수학이라는 책을 사서 1장쯤 읽어보면 아래 내용이 나온다. 프로그래밍과 수학, 정수론, 수열, 생성함수 등에 관심 있는 사람이면 수능 후에 사서 읽어볼만하다. 나도 바빠서 아직 초반부까지밖에 못 읽어봤지만, 왠만한 3,4학점 수업보다 이 책이 더 값질듯.

$$f(j)=\alpha_j \qquad (0 \le j \lt d) \\ f(dn+j)=cf(n)+\beta_j \qquad (0 \le j \lt d, 0 \le n)$$

요세푸스 문제는 위와 같이 일반화할 수 있으며, 이에 대한 해는 아래와 같이 나타낼 수 있다.

$$f((b_mb_m-1\ldots b_1 b_0)d)=(\alpha{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\ldots \beta_{b_1} \beta_{b_0})_c$$

덧붙임말

D 배열이 굳이 $[0, a_1]$과 같이 정의한 이유를 궁금해하는 사람이 있었다. 첫째로, 단일한 수가 아닌 배열로 정의한 이유는 2진법이 아닌 3,4,5,진법이라면 D 배열을 $[0, a_1, a_2, \ldots]$과 같이 만들어 초항에 대한 정보를 D 배열에 반영해 줘야 하기 때문이며, 둘째로 굳이 $D[0]=0$으로 만든 이유는, 그냥 딱히 넣을 수(number)가 없어서 그렇게 했다고 봐줘도 무방할 듯 싶다. 이 문제에는 $a_0$이 딱히 정의되어 있지도 않으니..