전설의 수학 문제를 찾아서 - 원탁위의 카드 (1) (2016, 서울대)

전설의 수학 문제를 찾아서 8번째 문제는 2016학년도 서울대 구술 고사 문제인 원탁위의 카드입니다. 이 문제는 중복조합, 불변성, 일대일 대응의 의미와 개념, 그리고 그 활용을 잘 보여주는 훌륭한 문제입니다.

전설이라고 부를 수 있는 수학 문제들은 어떤 것일까요? 문제 풀이의 난이도와 관계 없이, 수학 문제를 푸는 재미가 있는 문제, 학문적인 의미를 가지고 있는 문제, 문제 풀이의 원리가 여러 다른 문제에서도 두고 두고 사용되는 문제입니다. “전설의 수학 문제를 찾아서”는 전설이라고 부를 수 있는 수학 문제들을 찾아 풀어보고, 무엇을 배울 수 있는지 그 배경과 의미를 설명하는 연재글입니다.

이 문제는 $2$ 개의 병렬적인 서로 다른 문제들로로 구성이 되어 있습니다. 원래는 하나의 글에서 두 문제를 모두 다루어보려고 했는데, 글이 길어져서 두 개의 글로 나누려고 합니다. 이 글에서는 첫번째 문제를 다루어 보도록 하겠습니다. (두번째 문제는 다음 글에서 다루고 있습니다.)

전설의 수학 문제를 찾아서 – 원탁위의 카드 (2) (2016, 서울대)

[문제1]과 그 의미

집합 $S=\{1, -1, i, -i\}$가 있다고 하자. 원탁에 $n$명의 학생들이 각각 한 장의 빈 종이를 들고 원탁에 같은 간격으로 앉아 있다. 그리고 학생들이 각각 집합 $S=\{1, -1, i, -i\}$의 원소중 하나를 골라 자신이 갖고 있는 종이에 썼다.

어떠한 이웃한 두 학생이 쓴 수의 합도 $0$이 되지 않는 경우의 수를 구하시오.

이 문제의 첫 번째 질문이 결국 묻고 싶은 것은 다음과 같습니다

경우의 수를 셀 때 사용하는 기본적인 여러 도구-순열, 조합, 중복조합-들의 개념을 정확히 이해하고 있는가?

문제가 가진 규칙성을 발견하고 첫번째 질문에 대해 대답하기 위해서는 위해서는 순열과 조합, 중복조합과 같은 기본적인 도구들의 개념을 바르게 이해하고 있어야 합니다

다른 많은 문제들과 마찬가지로, [문제1]을 풀기 위해서는 먼저 문제의 조건에 맞는 예를 몇 개 써보고, 문제가 갖고 있는 규칙성을 찾은 다음, 그것을 이용하여 답을 작성할 수 있어야 합니다.

이 문제의 가장 큰 장점은 문제가 가지고 있는 규칙성이 매우 다양하다는 점입니다. 문제를 푸는 사람이 발견하는 규칙성에 따라 서로 다른 풀이를 만드는 것이 가능합니다.

문제가 갖고 있는 규칙성을 파악해 보기 위해, 문제의 조건대로 이웃한 두 학생이 쓴 수의 합이 $0$이 되지 않도록 카드를 나열해보겠습니다. 예를 들기 위해 학생의 수는 $5$명 ($n=5$)로 하고, 학생1을 기준으로 반시계 방향으로 학생2, 학생3, 학생4, 학생5를 배치해 두겠습니다. $$\require{AMScd}
\begin{CD}
\text{학생1} @. @<<< \text{학생5}\\
@VVV @. @AAA\\
\text{학생2} @>>> \text{학생3} @>>> \text{학생4}
\end{CD}$$

이제 학생들의 순서가 고정되어 있기 때문에 원탁위에 앉아 있는 학생들의 배열을 $$학생1-학생2-학생3-학생4-학생5-(학생1)$$ 과 같이 학생1을 시작으로 하는 직선 모양의 배열로 바꾸어 줄 수 있습니다. 학생1이 맨 끝에도 있는 이유는 학생5가 학생1과 이웃하고 있는 원형 배열의 특징을 유지하기 위해서 입니다. 이렇게 원모양의 배열을 직선 형태의 배열로 바꾸면 사용할 수 있는 수학 도구(순열과 같은)들이 늘어나기 때문에 문제를 푸는데 많은 도움이 됩니다.

이제 모든 준비가 되었으니, 문제의 조건을 만족시키는 구체적인 예를 몇 개 써보겠습니다. 먼저 학생1의 숫자가 $1$일 때입니다. $$\begin{array}{c c c c c c}
\text{학생1}&\text{학생2}&\text{학생3}&\text{학생4}&\text{학생5}&\text{(학생1)} \\\hline
1 & 1 & i & i & i & (1)\\
1 & i & -1 & -1 & i & (1)\\
1 & i & -1 & -i & -i & (1)\\
1 & 1 & -i & -i & 1 & (1)
\end{array}$$

음..아직 문제의 규칙성이 뚜렷히 보이지 않는 것 같지만, 왠지 같은 숫자가 연속하는 부분이 있다는 것 특이합니다 (이미 알아차리신 분들도 계실 것이라고 생각합니다.) 이제 같은 숫자가 연속되는 부분을 묶어보면 본격적으로 이 문제의 규칙성이 뚜렷하게 나타나기 시작합니다. $$\begin{array}{c c c c c c}
\text{학생1}&\text{학생2}&\text{학생3}&\text{학생4}&\text{학생5}&\text{(학생1)} \\\hline
\bbox[5px, border:2px solid red] {1} & \bbox[5px, border:2px solid red]{1} & \bbox[5px, border:2px solid blue]{i} & \bbox[5px, border:2px solid blue]{i}& \bbox[5px, border:2px solid blue]{i} & (1)\\
\bbox[5px, border:2px solid red]{1} &\bbox[5px, border:2px solid blue]{i} & \bbox[5px, border:2px solid green]{-1} & \bbox[5px, border:2px solid green]{-1} & \bbox[5px, border:2px solid blue]{i} & (1)\\
\bbox[5px, border:2px solid red]{1} & \bbox[5px, border:2px solid blue]{i} & \bbox[5px, border:2px solid green]{-1} & \bbox[5px, border:2px solid black]{-i} & \bbox[5px, border:2px solid black]{-i} & (1)\\
\bbox[5px, border:2px solid red]{1} & \bbox[5px, border:2px solid red]{1} & \bbox[5px, border:2px solid black]{-i} &\bbox[5px, border:2px solid black]{-i} & \bbox[5px, border:2px solid red]1 & (1)
\end{array}$$ 앞으로 이렇게 같은 숫자로 묶인 부분을 모둠이라고 부르겠습니다. 학생들이 선택할 수 있는 숫자는 $1$, $-1$, $i$, $-i$이므로, 모든 모둠은 $1$로 채워진 모둠, $-1$로 채워진 모둠, $i$로 채워진 모둠, $-i$로 채워진 모둠 중 하나입니다. 이 중 $1$로 채워진 모둠과 $-1$로 채워진 모둠을 실수모둠, $i$와 $-i$로 채워진 모둠을 허수 모둠으로 부르겠습니다.

이제 앞서 찾은 예에서 모둠을 관찰하면 정말로 중요한 규칙성을 하나 관찰할 수 있습니다. 바로 실수와 허수 모둠이 번갈아 가며 나타나고 있다는 것입니다! 이렇게 실수와 허수 모둠이 번갈아 나타나는 이유는 인접한 두 수의 합은 $0$이 될 수 없다는 문제의 조건 때문입니다. 만약 어떤 학생이 숫자 $x$ ($x\in \{1,-1, i, -i\}$)를 선택했다고 하고, 그 다음 학생이 선택할 수 있는 수를 표시하면 다음과 같습니다. $$
\begin{array}{c|c|c|c}
x & & & \\ \hline
1 & 1 & i & -i \\ \hline
-1 & -1 & -i & i \\ \hline
i & i & -1 & 1\\ \hline
-i & -i & 1 & -1
\end{array}$$이 숫자들을 보면 재미있는 규칙을 관찰할 수 있습니다. $x$ 다음에 $-x$를 선택할 수 없는 이유는 두 수의 합 $x+(-x)=0$이기 때문입니다. $-x$를 $x \times 1$로 해석하면 아주 재미있는 규칙을 발견할 수 있습니다. 어떤 숫자 $x$를 선택하더라도 그 다음에 올 수 있는 숫자는 $3$개는 바로$3$개의 숫자의 의미는바로 $x$에 $1$을 곱하거나, $i$를 곱하거나, $-i$를 곱한 숫자라는 것입니다! $x$에 $1$과 $i$, $-i$를 곱한 수를 나열해 보면 동일한 결과를 얻을 수 있습니다. $$\begin{array}{c|c|c|c}
x & 1\cdot x & i\cdot x & -i\cdot x \\\hline
1 & 1 & i & -i \\ \hline
-1 & -1 & -i & i \\ \hline
i & i & -1 & 1\\ \hline
-i & -i & 1 & -1
\end{array}$$ 따라서 어떤 학생의 번호가 $x$일 때, 그 다음 학생의 번호가 $x$라면 두 학생의 번호가 같아지므로 두 학생은 같은 모둠에 속한다는 것을 나타냅니다. 만약 다음 학생의 번호가 $ix$나 $-ix$라면, $x$에 $i$나 $-i$를 곱한 것이므로 $x$가 실수라면, $ix$나 $-ix$는 허수가 되어 실수에서 허수 모둠으로 전환이 되는 것을 나타냅니다. 반대로, $x$가 허수라면, $ix$나 $-ix$는 실수가 되어 허수 실수 모둠으로 전환이 되는 것을 나타냅니다.

이제 이 규칙을 활용하면 서로 다른 $2$개의 해법을 만들 수 있습니다. 이 글의 주제는 두번째 방법에 대해 이야기 하는 것이 목표이므로 첫번째 방법은 풀이의 얼개를 설명하고 넘어가도록 하겠습니다.

첫번째 방법-같은 것을 포함하는 순열

어떤 학생의 번호에서 $1$이나 $i$, $-i$를 곱해서 다음 학생의 번호를 결정한다는 규칙을 생각하면 생각하면, 학생1에서 출발하여 학생1까지 돌아올 때 까지의 학생들의 번호를 정해주는 과정은 다음과 같이 나타낼 수 있습니다. (이 때 학생k에서 학생k+1의 번호를 만들기 위해 곱해주어야 하는 숫자를 $a_k$이라 하고, 학생1을 기준으로 학생2, … 학생n이 반시계 방향으로 배치되어 있다고 가정하겠습니다.) $$\begin{align}&학생1(x)\xrightarrow{a_1}학생2(a_1x)\xrightarrow{a_2}학생3(a_1a_2x)\xrightarrow{a_3}\cdots\\
&\cdots\xrightarrow{a_{n-1}}학생n\xrightarrow{a_n}학생1(a_1a_2\cdots a_nx)\end{align}$$ 이 줄의 처음과 마지막에 있는 학생1은 같은 학생이므로 $$x=a_1a_2a_3…a_nx$$ 이 되어야 합니다. 그런데, $a_n$는 $1$, $i$, $-i$ 중 하나이므로 $a_n\ne 0$ 입니다. 따라서 $$a_1a_2a_3\cdots a_n=1, (a_k\in \{1,i, -i\})$$ 입니다. 따라서 $$a_1, a_2, a_3, … a_n$$에서 $1$이 $p$번, $i$가 $q$번, $-i$가 $r$번 쓰였다고 한다면 다음과 같은 조건 $$\begin{align}
&p+q+r=n, (p,q,r\geq 0) \\
&1^p(i)^q(-i)^r=(-1)^r(i)^{q+r}=1\end{align}$$을 만족하는 $1$과 $i$, $-i$를 사용하여 만들 수 있는 “같은 것을 포함하는 순열”의 개수를 세는 것으로 문제를 풀 수 있습니다.

두번째 방법-중복조합

앞서 문제에 조건에 맞추어 서로 다른 숫자를 써보면 실수와 허수가 반복되는 모둠의 전환이 생긴다는 것을 알 수 있었습니다. 렇다면 각 모둠의 크기는 어떨까요? 모든 모둠이 적어도 $1$개의 숫자를 갖고 있어야 한다는 것 이외에 모둠의 크기에 대한 뚜렷한 규칙성은 보이지는 않습니다. 따라서 [문제1]에서 요구하는 경우의 수를 구하기 위해서는 크기가 고정되어 있지 않은 실수 모둠과 허수 모둠이 번갈아 가며 나타날 수 있는 경우의 수를 세어주면 됩니다. 그렇다면 이러한 경우의 수는 어떻게 셀 수 있을까요? 바로 중복조합입니다!

중복조합의 목적

중복조합은 무엇을 세기 위한 도구일까요? 물론 중복조합의 정의대로 같은 것을 중복하여 뽑는 수를 셀 때 중복조합을 사용할 수도 있고, $$a+b+c=5$$를 만족하는 음이 아닌 정수 $a$, $b$, $c$ 순서쌍 $(a,b,c)$의 개수를 세는 데에도 사용할 수 있습니다. 하지만 중복조합의 가장 본질적인 목적은 같은 것이 반복되는 모둠의 전환을 다루기 위한 것입니다. 앞서 예를 든 방정식 $$a+b+c=5$$의 경우에도 다음과 같이 각 모둠의 크기의 합을 $5$로 유지하면서 첫번째 모둠을 $a$로 채우다가 두번째 모둠을 $b$로 채우고, \세번째 모둠을 (c\)로 채우면 방정식의 음이 아닌 정수해를 표현 할 수 있습니다.
$$\begin{array}{c| c}
\text{모둠 전환 }a\rightarrow \color{red}{b} \rightarrow \color{blue}{c}& (a,b,c) \\\hline
(a)-\color{red}{(bbb)}-\color{blue}{(c)} & (1,3,1) \\
(aa)-\color{red}{(bb)}-\color{blue}{(c)} & (2,2,1) \\
(a)-\color{red}{(b)}-\color{blue}{(ccc)} & (1,1,3) \\
()-\color{red}{(bbb)}-\color{blue}{(cc)} & (0,3,2)
\end{array}$$ (제일 마지막 경우는 첫번째 모둠에 아무것도 들어가지 않은 채, 두번째 모둠으로 전환이 시작된 것이라고 해석할 수 있습니다.) 이렇게 세 모둠($a$ 모둠의 크기를 적당히 바꾸어 가며 모둠을 전환할 수 있는 경우의 수를 세면 방정식 $a+b+c=5$의 음이 아닌 정수해를 셀 수 있게 되는 것이입니다. 이렇게 중복조합의 가장 근본적인 목적은 같은 것으로 채워진 모둠을 전환할 수 있는 경우의 수를 세는 데 있습니다.

이제 원래 문제로 돌아가 보겠습니다. 문제의 조건에 맞는 경우를 찾기 위해서는 학생1부터 학생5까지를 몇 개의 모둠으로 나누고, 각각의 모둠안에 같은 숫자로 채워주면 됩니다. 그리고 모둠이 바뀔 때는 앞서 찾은 규칙성에 의해 실수 모둠과 허수 모둠이 교대로 나타나 줄 수 있도록 해주어야 합니다. 논의를 간결히 하기 위해 앞으로 모둠의 이름은 $A$, $B$, $C$와 같은 대문자로, 각 모둠안에 들어있는 수의 개수(모둠의 크기)는 $a$, $b$, $c$와 같은 소문자로 나타내겠습니다.

경우의 수를 세기 위해 먼저 사전작업을 몇가지 해두겠습니다. 먼저 대칭성에 의해 학생$1$이 숫자$1$을 선택했을 때 경우의 수와 다른 수 ($-1$ 또는 $i$ 또는 $-i$)를 선택했을 때의 경우의 수가 같습니다. 따라서 전체 경우의 수는 $$\text{학생1이 숫자$1$을 선택했을 때의 경우의 수}\times 4$$이므로 학생1이 숫자 $1$을 선택했을 때의 경우를 세기로 하겠습니다.

또한 학생1이 실수 $1$을 선택하면 학생1이 포함되어 있는 한 모둠은 모두 같은 수로 채워야 한다는 규칙 때문에 학생1이 포함되어 있는 모둠은 모두 $1$로 채워야 합니다. 이제 경우의 수를 세기 위한 사전작업을 모두 마쳤으므로 전체 모둠의 개수에 따라 경우의 수가 어떻게 달라지는지 살펴보겠습니다. 먼저 모둠의 개수를 정하고, 모둠을 채울 수 있는 숫자의 종류를 정하는 방법과, 각 모둠의 크기를 정하는 방법을 정하는 방법을 생각해보겠습니다. (학생5가 학생1과 이웃하고 있다는 사실을 과 실수 모둠과 허수 모둠이 반복해서 나타나야 한다는 사실을 꼭 기억해주세요!)

① 전체 모둠의 수가 $1$개 일 때

만약 학생 $5$명 전체가 하나의 모둠 $A$에 들어간다면, 학생1이 실수 $1$을 선택했다는 가정 때문에, 모둠 $A$를 채울 수 있는 숫자는 $1$뿐입니다. 따라서 모둠 $A$를 채울 수 있는 숫자의 종류를 결정하는 방법은 $1$가지입니다. $$\begin{array}{c| c | c}
\text{모둠} & \text{종류} & \text{채울 수 있는 수} \\\hline
A & \text{실수} & 1 \\
\end{array}$$ 그렇다면 모둠의 크기는 어떻게 정해주어야 할까요? 전체 모둠의 수는 한 개이므로 모둠$A$의 크기는 $5$가 되어야 합니다. 따라서 $$a=5, (a\geq 1)$$입니다. 이 방정식의 음이 아닌 정수해의 개수를 중복조합을 사용하여 나타내면 $_1\mathrm{H}_4$입니다. (해의 개수는 단순히 $1$로 나타낼 수 있지만, 모둠의 개수가 $2$개 이상일 때 해의 개수를 중복조합으로 나타내는 것과 표현을 맞추기 위해서 중복조합을 사용해서 나타냈습니다.) 따라서 전체 모둠의 개수가 $1$개 일 때의 경우의 수는 모둠 $A$를 채울 수 있는 숫자의 종류와 모둠의 크기가 될 수 있는 수를 곱하면 $$_1\mathrm{H}_4\times 1=\ _1\mathrm{H}_4\tag{1}\label{eq1}$$

② 전체 모둠의 수가 $2$개 일 때

만약 학생 전체를 $$A(실수)-B(허수)$$와 같이 두 모둠으로 나눈다면, 실수 모둠과 허수 모둠이 번갈아 가며 나타나야 한다는 규칙에 따라 두 번째 모둠 $B$는 허수 모둠이 되어야 합니다. (첫번 째 모둠 $A$가 $1$로 채워져 있기 때문에 두 번째 모둠$B$를 $-1$로 채우면 모둠 $A$에서 모둠 $B$로 전환이 될 때, 모둠 $A$의 마지막 학생과 모둠 $B$의 첫번째 학생이 가지고 있는 숫자의 합이 $1+(-1)=0$이 되어 버립니다.) 따라서 모둠 $B$는 $i$로 채울 수도 있고, $-i$로 채울 수도 있습니다. 따라서 두 모둠 $A$, $B$를 채울수 있는 숫자를 결정하는 방법은 $1\times 2=2$입니다. $$\begin{array}{c| c | c}
\text{모둠} & \text{종류} & \text{채울 수 있는 수} \\\hline
A & \text{실수} & 1 \\
B & \text{허수} & i, -i \\
\end{array}$$ 이제 모둠의 크기를 생각해보겠습니다. 두 모둠의 크기의 합은 $5$이고, 각 모둠에는 적어도 한 명의 학생이 있어야 하기 때문에, $$a+b=5, (a, b\geq 1)$$입니다. 이 방정식의 자연수 해의 개수는 $_2\mathrm{H}_3$이므로 전체 모둠의 수가 $2$개일 때 경우의 수는 $$_2\mathrm{H}_3\cdot 2\tag{2}\label{eq2}$$

③ 전체 모둠의 수가 $3$개 일 때

만약 학생 전체를 세 모둠 $$A(실수)-B(허수)-C(실수)$$으로 나눈다면, 전체 모둠의 수가 $2$개 일 때와 같이 학생 1이 포함된 모둠 $A$는 $1$로, 허수 모둠인 $B$는 $i$로 채우거나 $-i$로 채울 수 있습니다. 그렇다면 실수 모둠 $C$는 어떨까요? 결론부터 먼저 말씀드리면 실수 모둠 $C$는 $1$로 채워 주어야 합니다. 왜냐하면 실수 모둠 $C$는 학생5를 포함하고 있는 모둠이기 때문에 실수 모둠 $C$를 $-1$로 채운다면, 학생5의 번호가 $-1$이 되어 학생5와 이웃한 학생1이 선택한 숫자 $1$과의 합이 $0$이 되기 때문입니다. 따라서 세 모둠 $A$, $B$, $C$를 채울 수 있는 숫자를 결정하는 방법은 $1\times 2\times 1=2$입니다. $$\begin{array}{c| c | c}
\text{모둠} & \text{종류} & \text{채울수 있는 수} \\\hline
A & \text{실수} & 1 \\
B & \text{허수} & i, -i \\
C & \text{실수} & 1\\
\end{array}$$ 그리고 세 모둠의 크기의 합은 $5$이고, 각 모둠에는 적어도 한명의 학생이 있어야 하기 때문에 $$a+b+c=5, (a,b,c\geq 1)$$입니다. 이 방정식의 자연수 해의 개수는 $_3\mathrm{H}_2$ 이므로 전체 모둠의 수가 $3$개 일 때 경우의 수는 $$_3\mathrm{H}_2\cdot 2\tag{3}\label{eq3}$$

④ 전체 모둠의 수가 $4$개 일 때

만약 학생 전체를 네 모둠 $$A(실수)-B(허수)-C(실수)-D(허수)$$으로 나눈다면 학생1이 포함된 모둠$A$는 $1$로, 허수 모둠인 $B$는 $i$만으로 채우거나 $-i$만으로 채워야 합니다. 이제 그 다음 실수 모둠 $C$는 마지막 모둠이 아니기 때문에 $1$로도 채울 수 있고, $-1$로도 채울 수 있습니다. 학생5가 포함된 마지막 모둠인 $D$는 허수 모둠이기 때문에 $i$로 채울 수도 있고, $-i$로도 채울 수 있습니다. 따라서 네 모둠 $A$, $B$, $C$,$D$를 채울 수 있는 숫자를 결정하는 방법은 $$1\times 2\times 2\times 2=2^3$$입니다. $$\begin{array}{c| c | c}
\text{모둠} & \text{종류} & \text{채울수 있는 수} \\\hline
A & \text{실수} & 1 \\
B & \text{허수} & i, -i \\
C & \text{실수} & 1, -1\\
D & \text{허수} & i, -i \\
\end{array}$$ 그리고 네 모둠의 크기의 합은 $5$이고, 각 모둠에는 적어도 한명의 학생이 있어야 하기 때문에 $$a+b+c+d=5, (a,b,c,d\geq 1)$$입니다. 이 방정식의 자연수 해의 개수는 $_4\mathrm{H}_1$ 이므로 전체 모둠의 수가 $4$개 일 때 경우의 수는 $$_4\mathrm{H}_1\cdot 2^3\tag{4}\label{eq4}$$

⑤ 전체 모둠의 수가 $5$개 일 때

마지막으로, 학생 전체를 다섯개의 모둠 $$A(실수)-B(허수)-C(실수)-D(허수)-E(실수)$$으로 나누면, 지금까지와 같은 방법으로 각 모둠을 채울 수있는 숫자의 종류는 $$\begin{array}{c| c | c}
\text{모둠} & \text{종류} & \text{채울수 있는 수} \\\hline
A & \text{실수} & 1 \\
B & \text{허수} & i, -i \\
C & \text{실수} & 1, -1\\
D & \text{허수} & i, -i \\
E & \text{실수} & 1
\end{array}$$입니다. 따라서 다섯 모둠 $A$, $B$, $C$, $D$, $E$를 채울 수 있는 숫자를 결정하는 방법은 $$1\times 2\times 2\times 2\times 1=2^3$$입니다. 또한 다섯 모둠의 크기의 합은 $5$이고, 각 모둠안에는 적어도 한명의 학생이 있어야 하기 때문에 $$a+b+c+d+e=5,(a,b,c,d,e\geq 1)$$입니다. 이 방정식의 자연수 해의 개수는 $_5\mathrm{H}_0$ 이므로 전체 모둠의 수가 $5$개 일 때, 경우의 수는 $$_5\mathrm{H}_0\cdot 2^3\tag{5}\label{eq5}$$입니다.

전체 경우의 수

따라서 학생1을 기준으로 반시계방향으로 $$학생1-학생2-학생3-학생4-학생5-(학생1)$$이 나열 되어 있고, 학생1이 숫자 $1$을 선택했을 때의 경우의 수는 $$\begin{align}
&\eqref{eq1}+\eqref{eq2}+\eqref{eq3}+\eqref{eq4}+\eqref{eq5}\\
&=\ _1H_4+\ _2H_3\cdot 2+\ _3H_2\cdot 2+\ _4H_1\cdot 2^3+\ _5H_0\cdot 2^3\\&=\ _4C_0+\ _4C_1\cdot 2+\ _4C_2\cdot 2+\ _4C_3\cdot 2^3+\ _4C_4\cdot 2^3\\
&=61\end{align}$$입니다. 학생1을 기준으로 나머지 $4$명이 원탁위에 앉는 방법은 $4!$이고, 학생1이 선택할 수 있는 숫자의 종류는 모두 $4$개($1$, $-1$, $i$, $-i$)이므로 전체 경우의 수는 $$4!\times 4\times 61$$입니다. 이제 전체 학생의 수가 $n$명일 때로 일반화하려면, 학생1을 기준으로 $$학생1-학생2-학생3-\cdots-학생n-(학생1)$$이 나열되어 있는 상태에서 학생1이 $1$을 선택했을 때의 경우의 수를 세고, 학생1을 기준으로 나머지 $n-1$명을 나열하는 경우의 수인 $(n-1)!$과 학생1이 선택할 수 있는 수의 종류인 $4$를 곱해주면 됩니다.

먼저 학생1이 숫자$1$을 선택했을 때의 경우의 수는 $5$명일 때와 같은 방법을 사용하면 $$\begin{align}
&_1H_{n-1}+\ _2H_{n-2}\cdot 2+\ _3H_{n-3}\cdot 2 \\
&+\ _4H_{n-4}\cdot 2^3 + \ _5H_{n-5}\cdot2^3+\cdots\\\end{align}$$로 나타낼 수 있습니다. 이 식의 중복조합을 조합으로 바꾸어주면 $$\begin{align}&_{n-1}C_0 +\ _{n-1}C_1\cdot 2+\ _{n-1}C_2\cdot 2\\
&+\ _{n-1}C_3\cdot 2^3+\ _{n-1}C_4\cdot 2^3+\cdots \end{align}\tag{6}\label{eq6}$$로 나타낼 수 있습니다. 이제 남은 것은 식$\eqref{eq6}$을 좀 더 간단하게 나타낼 수 있는 방법이 존재하는지, 존재한다면 어떻게 줄일 수 있을 지 찾아보는 것입니다.

이항정리의 사용

식$\eqref{eq6}$을 관찰하면, 이항정리를 사용하여 $(1+2)^{n-1}$을 전개한 결과와 식$\eqref{eq6}$이 상당히 비슷하다는 것을 알 수 있습니다. $(1+2)^{n-1}$을 이항정리를 사용하여 전개하면 $$\begin{align}&(1+2)^{n-1}\\=&\ _{n-1}C_0+_{n-1}C_1\cdot 2+_{n-1}C_2\cdot 2^2\\&+_{n-1}C_3\cdot2^3+_{n-1}C_4\cdot 2^4+\cdots\end{align}$$ 입니다. 이제 이항정리를 사용하여 $(2+1)^{n-1}$을 전개한 식과 식$\eqref{eq6}$을 항별로 비교해 보겠습니다. $$\begin{array}{c | c}
(1+2)^{n-1} & \text{식\eqref{eq6}} \\\hline
_{n-1}C_0 & _{n-1}C_0 \\\
_{n-1}C_1\cdot 2 & _{n-1}C_1\cdot 2 \\
_{n-1}C_2\cdot 2^2 & \color{red}{_{n-1}C_2\cdot 2} \\
_{n-1}C_3\cdot 2^3 & _{n-1}C_3\cdot 2^3 \\
_{n-1}C_4\cdot 2^4 & \color{red}{_{n-1}C_4\cdot 2^3} \\
\cdots & \cdots\\
\end{array}$$ 식$\eqref{eq6}$에서 첫번째 항을 제외한 홀수번째 항 $$\begin{align}&
_{n-1}C_2\cdot 2^1,\\
& _{n-1}C_4\cdot 2^3,\\
&\cdots\\
& _{n-1}C_{2k}\cdot 2^{2k-1},\\
&\cdots\\
\end{align}$$서로 다르다는 것을 알 수 있습니다. 마치 이항정리를 사용해 전개한 식을 톱날이라고 생각한다면, 톱날에서 홀수번째 톱니가 빠져 있는 듯한 모습입니다. 이렇게 특정한 모양을 가진 식에서 부족한 항이 규칙적으로 존재하는 식을 다룰 때에는 먼저 부족한 항을 채워서 원하는 모양을 만들어 준 다음, 채워준 항을 다시 빼주는 방법을 사용합니다. 한편, $$\begin{align}&\ _{n-1}C_r\cdot 2^r
\\&=\ _{n-1}C_r\cdot 2\cdot 2^{r-1}
\\&=2\ _{n-1}C_r\cdot 2^{r-1}
\\&=\ _{n-1}C_r\cdot 2^{r-1} +\ _{n-1}C_r\cdot 2^{r-1}\end{align} $$이므로 $$\begin{align}&_{n-1}C_r\cdot 2^{r-1}\\&=\ _{n-1}C_r\cdot 2^{r}-\ _{n-1}C_r\cdot 2^{r-1}\end{align}$$ 따라서 식$\eqref{eq6}$의 (첫항을 제외한) 홀수번째 항을 다음과 같이 바꾸어주면 이항정리의 빠진 톱날을 채울 수있습니다. $$\begin{align}
&\ _{n-1}C_2\cdot 2=\ _{n-1}C_2\cdot 2^2-\ _{n-1}C_2\cdot 2\\
&\ _{n-1}C_4\cdot 2^3=\ _{n-1}C_4\cdot 2^4-\ _{n-1}C_4\cdot 2^3,\\
&\cdots\\
\end{align}$$ 이제 이항정리에서 빠진 톱날의 이를 채워주면 식$\eqref{eq6}$는 다음과 같이 바뀌게 됩니다. $$\begin{align}
&_{n-1}C_0 \\
&+\ _{n-1}C_1\cdot 2\\
&+\ _{n-1}C_2\cdot 2^2-\ _{n-1}C_2\cdot 2\\
&+\ _{n-1}C_3\cdot 2^3\\
&+\ _{n-1}C_4\cdot 2^4-\ _{n-1}C_4\cdot 2^3\\
\cdots\\
&=\underbrace{(\ _{n-1}C_0+\ _{n-1}C_1\cdot 2+\ _{n-1}C_2\cdot 2^2\cdots)}_{\text{합①}}\\
&-\underbrace{(\ _{n-1}C_2\cdot 2+\ _{n-1}C_4\cdot 2^3+\ _{n-1}C_6\cdot 2^5\cdots)}_{\text{합②}}\\
\end{align}$$ 입니다. 먼저, 합①은 간단히 $$\begin{align}
&\ _{n-1}C_0+\ _{n-1}C_1\cdot 2+\ _{n-1}C_2\cdot 2^2\cdots\\
&=(1+2)^{n-1}=3^{n-1}\\
\end{align}$$ 입니다. 그렇다면 합②은 어떻게 계산할 수 있을까요? 합②의 항들을 보면 이항계수 $\ _nC_r$의 $r$부분이 짝수들로 이루어져 있습니다. 혹시 이항항정리를 이용한 식에서 $r$이 짝수인 항만 존재하는 식이 있을까요? 가장 먼저 떠오르는 식은 이항정리를 이용한 공식인 $$\ _nC_0+\ _nC_2+\ _nC_4+\cdots = 2^{n-1}$$입니다. 이 공식을 얻는 과정과 비슷한 방법을 사용하면 $r$이 짝수인 항만 남길 수 있을 것 같습니다! $$\begin{align}
(1+2)^n=\ 1+\ _nC_1\cdot 2+\ _nC_2\cdot 2^2+\ _nC_3\cdot 2^3+\ _nC_4\cdot 2^5\cdots+\\
(1-2)^n=\ 1-\ _nC_1\cdot 2+\ _nC_2\cdot 2^2-\ _nC_3\cdot 2^3+\ _nC_4\cdot 2^5\cdots-\\
\end{align}$$ 이므로 두 식을 더하면, $$3^n+(-1)^n=2(1+\ _nC_2\cdot 2^2+\ _nC_3\cdot 2^3+\ _nC_4\cdot 2^4\cdots)$$를 얻을 수 있습니다. 따라서 $$\begin{align}
&1+\ _nC_2\cdot 2^2+\ _nC_3\cdot 2^3+\ _nC_4\cdot 2^4\cdots\\
&=\frac{1}{2}(3^n+(-1)^n)
\end{align}$$입니다. 하지만 합②를 구하기 위해서 이 결과를 바로 이용할 수 없습니다. 이 결과를 이용하기 위해서는 이용하기 위해서는 $\ _nC_2\cdot 2^2$과 같이 $\ _nC_r$의 $r$과 $2$의 지수가 같아야 하는데, 합②에서는 $\ _nC_2\cdot 2$처럼 $2$의 지수가 $r$보다 $1$만큼 작기 때문입니다. 하지만 이 문제는 다음과 같이 모든 항에 $2$를 곱하고 전체를 $2$로 나누어 주는 방법으로 간단히 해결할 수 있습니다. $$\begin{align}
&\ _{n-1}C_2\cdot 2+\ _{n-1}C_4\cdot 2^3+\ _{n-1}C_6\cdot 2^5\cdots\\
&=\frac{1}{2}(\ _{n-1}C_2\cdot 2^2+\ _{n-1}C_4\cdot 2^4+\ _{n-1}C_6\cdot 2^6\cdots)\\
\end{align}$$ 이제 $\ _nC_r$의 $r$과 $2$의 지수가 같기 때문에 합②를 계산할 수 있습니다. $$\begin{align}
&\ _{n-1}C_2\cdot 2+\ _{n-1}C_4\cdot 2^3+\ _{n-1}C_6\cdot 2^5\cdots\\
&=\frac{1}{2}(\ _{n-1}C_2\cdot 2^2+\ _{n-1}C_4\cdot 2^4+\ _{n-1}C_6\cdot 2^5\cdots)\\
&=\frac{1}{2}(1+\ _{n-1}C_2\cdot 2^2+\ _{n-1}C_4\cdot 2^4+\ _{n-1}C_6\cdot 2^6\cdots)-\frac{1}{2}\\
&=\frac{1}{2}\cdot\frac{1}{2}(3^{n-1}+(-1)^{n-1})-\frac{1}{2}\\
&=\frac{1}{4}\left(3^{n-1}+(-1)^{n-1}-2\right)
\end{align}$$ 입니다.

따라서 식$\eqref{eq6}$의 값은 $$\begin{align}
&합①-합②\\
&=3^{n-1}-\frac{1}{4}\left(3^{n-1}+(-1)^{n-1}-2\right)\\
&=\frac{1}{4}(4\cdot 3^{n-1} -3^{n-1}-(-1)^{n-1}+2)\\
&=\frac{1}{4}(3\cdot 3^{n-1}-(-1)^{n-1}+2)\\
&=\frac{1}{4}(3^n+(-1)^n+2)
\end{align}$$ 입니다. 한편, 학생1을 기준으로 나머지 $n-1$명의 학생이 원탁에 앉는 방법은 모두 $(n-1)!$이고, 학생1이 고를 수 있는 숫자는 모두 네 개($1$, $-1$, $i$, $-i$)이므로 식$\eqref{eq6}$에 이 값들을 곱해주면 문제에서 요구하는 경우의 수는 $$\begin{align}
&(n-1)!\times 4\times \frac{3^n+(-1)^n+2}{4}\\
&=(n-1)!\cdot(3^n+(-1)^n+2)\end{align}$$