간단한 퀴즈와 기사 문제

Quickies.

아래의 문제들을, 각 질문에 바로 답할 수 있을 때까지, 다른 날짜에 세 번 이상 풀어보는 것을 강력히 권한다. 각 질문을 읽으면서 바로 답할 수 있을 정도가 되어야 한다.

1. \(16\)쌍의 여학생-남학생 커플에서 5명의 여학생을 택하는 경우의 수는?
2. \(7\)개의 글자 AAABBBB를 배열하는 경우의 수는?
3. \(12\)개의 글자 AAABBBBCCCCC를 배열할 때, C끼리는 이웃하지 않도록 배열하는 경우의 수는?
4. \(10\)명의 사람을 일렬로 앉히는 경우의 수는?
5. \(10\)명의 사람을 원탁에 앉히는 경우의 수는?
6. 서로 구별되는 도미노는 몇 가지인가? (도미노는 정사각형 두 개를 이어붙여 만든 도형이며, 각 정사각형에는 \(0\)개에서 \(6\)개까지의 점이 찍혀있다.)
7. \(9\)명의 여학생과 \(12\)명의 남학생을 일렬로 앉힐 때, 여학생끼리는 서로 이웃하지 않도록 앉히는 경우의 수는?
8. 서로 다른 \(4\) 종류의 콜라캔에서 \(10\)캔을 택하는 경우의 수는?
9. \(4\)명의 사람에게 사이다 \(22\)캔을 나눠줄 때, 각자 적어도 \(1\)캔 이상을 받도록 나눠주는 경우의 수는?
10. \(57\)가지 종류가 있는 캔음료 중 \(8\)가지를 추려 그들 중 \(9\)개의 캔을 택하는 경우의 수는?
11. 여섯 명의 어린이에게 사과 \(5\)개, 오렌지 \(8\)개를 분배하는 경우의 수는?
12. 사과 \(5\)개, 오렌지 \(8\)개에서 몇 개를 골라 한 접시에 담을 때, 사과와 오렌지 각각 적어도 하나는 담기도록 담는 경우의 수는?
13. \(10\)억보다 작은 음이 아닌 정수 중에서, (\(10\)진법으로 표현했을 때) \(5\)개의 \(7\)을 갖는 수는 몇 개인가?
14. 알파벳으로 이루어진 \(5\)-letter word들 중에서 반복된 글자가 없는 것은 몇 개인가?
15. \(8\)명의 \(2\)학년 학생, \(8\)명의 \(1\)학년 학생이 있을 때, 이들을 \(2\)인 \(1\)조로 분류하는데, 같은 학년끼리는 한 조가 되지 않도록 분류하는 경우의 수는?
16. 방정식 \(w+x+y+z=24\)의 양의 정수해의 개수는?
17. \(12\)개의 A, \(12\)개의 B에서 \(12\)개의 글자를 택하는 경우의 수는?
18. \(12\)개의 A, \(12\)개의 B에서 \(18\)개의 글자를 택하는 경우의 수는?
19. \(12\)개의 A, \(12\)개의 B, \(12\)개의 C에서 \(25\)개의 글자를 택하는 경우의 수는?
20. 총 \(7\)종류의 도넛이 있는데, \(12\)개의 도넛을 고르되 각 종류의 도넛이 적어도 하나는 포함되도록 고르는 경우의 수는?
21. 총 \(50\)명의 요원을 \(5\)개의 나라 각각에 \(10\)명씩 배정하여 파견하는 경우의 수는?
22. 서로 구별되는 \(12\)개의 상자에 \(17\)개의 빨간공을 넣는데, 빈 상자가 없도록 넣는 경우의 수는?
23. \(9\)개의 주사위를 던졌을 때의 경우의 수는?
24. \(12\)명의 요정을 원탁에 앉히는 경우의 수는? (물론 요정들은 서로 구별된다.)
25. \(5\)개의 C, \(15\)개의 R을 배열할 때, 두 개의 C 사이에는 항상 적어도 두 개의 R이 있도록 배열하는 경우의 수는?

다음 문제를 생각해보자.

집합 \(\{1, 2, \ldots, 20\}\)에서 다섯 개의 정수를 택할 때, 택한 다섯 개의 정수 중 임의의 두 정수의 차가 적어도 \(3\)이 되도록 택하는 경우의 수는?

이 문제는 언뜻 어려워 보일 수도 있다. \(5\)개의 C, \(15\)개의 R을 생각해보자(C는 Choose에서, R은 Reject에서 따온 것이다). 임의의 두 C 사이에 적어도 \(2\)개의 R이 있도록 이들을 배열하는 것,.... 아하! 이건 바로 앞의 Quickies의 마지막 문제와 동일한 것에 불과하다. 직접 계산해보자. 먼저 \[ {}_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge} \] 를 생각하자. 안쪽의 \(4\)개의 wedge 각각에 \(2\)개의 R을 넣고 남은 \(15-8=7\)개의 R을 \(6\)개의 wedge에 임의로 넣는 경우를 생각하면 그 경우의 수가 \(\left\langle\!{{6}\atop{7}}\!\right\rangle\)임을 얻는다. 즉 구하는 답이 \(\left\langle\!{{6}\atop{7}}\!\right\rangle=\binom{6+7-1}{7}=792\)임을 얻는다. 다소 어려워 보일 수 있었던 이 문제도, 이제는 그냥 하나의 쉬운 문제일 뿐이라 하겠다.

Knights

이제 지금까지 사용한 셈하기 기법을 하나의 고전적인 문제에 활용해보자. 이 문제는 위의 문제들처럼 간단한 문제는 아닌데, 해법을 읽기 전에 먼저 스스로 문제를 해결해보는 것을 추천한다.

이번에도 원탁에 앉아 있는 한 명의 기사인 Lucky Lancelot Pierre를 소환하자. Lancelot이 원정대에 속하느냐 속하지 않느냐의 두 가지 경우로 나누어 생각할 수 있다.

먼저 Lancelot이 원정대에 속하는 경우를 생각하자. 이 경우 Lancelot과 이웃한 두 명은 원정대에서 제외된다. 이제 남은 \(12\)명의 기사들 중 \(3\)명을 뽑되 인접한 기사는 없도록 뽑아야 한다. \(3\)개의 C와 \(9\)개의 R로 만든 word를 생각하되 C는 서로 인접하지 않게 배열된 것을 생각하자(이번에도 Choose와 Reject에서 각각 C와 R을 가져왔다). \(9\)개의 R을 먼저 써두면 이들 사이의 많아야 \(1\)개의 C를 쓸 수 있는 \(10\)개의 위치를 생각할 수 있다. 따라서 조건에 맞는 word의 개수가 \(\binom{10}{3}\)임을 얻으며 이는 Lancelot이 속하는 원정대를 꾸리는 경우의 수와 같다.

이번에는 Lancelot이 원정대에 속하지 않는 경우를 생각해보자. 이는 \(4\)개의 C와 \(10\)개의 R로 이루어진 \(14\)-letter word를 만들되 인접한 C가 없게끔 만드는 경우를 찾는 것으로 \(\binom{11}{4}\)가지 경우가 있음을 알 수 있다. 따라서 결국 구하는 값은 \[ \binom{10}{3}+\binom{11}{4}=450 \] 임을 알 수 있다.

이를 일반화하여 원탁에 앉은 \(k\)명의 기사 중 \(q\)명을 택하여 원정대를 만들 때, 이웃한 기사는 함께 뽑히지 않도록 만드는 경우의 수를 생각해보자. 만일 Lancelot이 속한 원정대를 만드는 경우의 수를 구하고 그 수에 \(k\)를 곱한다면, 이는 우리가 구하는 수에 \(q\)를 곱한 것과 일치하게 된다. (이 값은 우리가 관심을 두고 있는 경우가 아니긴 하지만, 리더가 있는 원정대를 만드는 경우의 수와 같다.) 이제 Lancelot을 원정대에 속하게 하고, Lancelot과 인접한 두 기사를 제외하고 생각해보자. 남아 있는 \(k-3\)명의 기사가 있으며 인접하지 않은 \(q-1\)명의 기사를 택해야 한다. 이를 위해 \(q-1\)개의 C와 \((k-3)-(q-1)\)개의 R로 이루어진 word를 만들되, 인접한 C가 없도록 만드는 경우의 수를 구해보자. 이 수는 \(\binom{k-q-1}{q-1}\)이며 이는 Lancelot이 속한 원정대를 만드는 경우의 수와 같다. 따라서 우리가 찾는 수는 \(\frac{k}{q}\binom{k-q-1}{q-1}\) 혹은 \(\frac{k}{k-q}\binom{k-q}{q}\) 혹은 \[ \frac{k(k-q-1)!}{q!(k-2q)!} \] 과 같다.

한걸음 더 나아가 이웃한 기사가 원정대로 뽑히지 않는다는 조건을 원정대로 뽑힌 두 기사 사이에 적어도 \(g\)명의 기사가 있어야한다는 조건으로 일반화해보자. (TMI: \(g\)는 gap에서 가져왔다.) 이번에는 \(q-1\)개의 C와 \((k-(2g+1))-(q-1)\)개의 R로 이루어진 word를 만들되 임의의 두 C 사이에는 적어도 \(g\)개의 R이 있도록 만드는 경우의 수에 \(k/q\)를 곱하려 한다. 이 경우 \(q-1\)개의 C를 먼저 써두고 시작하는 것이 편하다. 즉 \(q-1\)개의 C를 나열한 \[ {}_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge}\ldots_{\wedge}\mathrm{C}_{\wedge}\mathrm{C}_{\wedge} \] 를 생각하자. R을 써넣을 수 있는 \((q-1)+1\)개의 wedge가 있다. 이 중 안쪽에 있는 \((q-1)-1\)개의 각 위치는 적어도 \(g\)번 선택하여 R을 써넣어야 문제의 조건에 맞다. 그리고 남아있는 \(k-(2g+1)-(q-1)-g(q-2)\)개의 R을 \(q\)개의 wedge에 임의로 써넣으면 원하는 word를 얻게 된다. 따라서 우리가 찾는 수는 \(\frac{k}{q}\left\langle\!{{q}\atop{k-(2g+1)-(q-1)-g(q-2)}}\!\right\rangle\) 혹은 \(\frac{k}{q}\binom{k-gq-1}{q-1}\) 혹은 \[ \frac{k(k-gq-1)!}{q!(k-(g+1)q)!} \] 과 같다.