xMO 카페에 올라온 조합 문제들

오랜만에 xMO 카페에 들렀는데 조합 문제들 몇 가지가 소개된 글을 보게 되어 여기에서 그 문제들을 살펴보고자 한다.

1번은 Coupon collector’s problem으로도 알려져있는 문제이다. 처음으로 $k$ 종류의 과자를 얻었을 때의 과자 수를 나타내는 random variable을 $a_k$ , $a_k - a_{k-1} = b_k$ 로 두면 ( $a_0 = 0$ ) 구하고자 하는 것은 $\mathbb{E}(a_n) = \mathbb{E}(\sum_{k=1}^n b_k) = \sum_{k=1}^n \mathbb{E}(b_k)$ 가 된다. 편의상 $p = \frac{n-k+1}{n}$ 라 하면 $\mathbb{E}(b_k) = p + 2(1-p)p + 3(1-p)^2 p + \cdots = \frac{1}{p} = \frac{n}{n-k+1}$ 이므로 답은 $n \left( \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n} \right)$ 이 된다. Probabilistic method에서 자주 쓰이는 linearity of expected value의 대표적인 예.

2번은 일전에 이 블로그에서 소개한 적이 있는 문제로, 2019년 도쿄 공대 전기 수학 문제이다.

3번은 본 적이 있는 듯 없는 듯… 비슷한 유형의 문제들처럼 비슷하게 풀린다. $0 \leq y_1, \ldots, y_{2p} \leq p$ 들에 대해 $(\sum_{j=1}^{2p} a_{1j}y_j, \ldots, \sum_{j=1}^{2p} a_{pj}y_j)$ 들을 보면 $y_j$ 들을 잡는 경우의 수는 $(2p+1)^{2p}$ 개, 순서쌍으로 나타날 수 있는 경우의 수는 $(4p^2+1)^p$ 이하인데 $(2p+1)^2 > 4p^2+1$ 이라 비둘기 집의 원리에 의해 순서쌍이 일치하는 두 $\{ y_j \}$ 들이 나타나고 그들의 차를 $\{ x_j \}$ 로 잡으면 된다.

4번은 Federico Ardila가 발견한 수열로, 2002년 IMO 쇼트리스트 C3 문제로도 등장한 적이 있다. 답은 $n!$ 으로, 다음과 같은 bijection 풀이가 잘 알려져 있다. 임의의 꽉찬 수열을 잡아 $i$ 가 $a_i$ 번 등장한다고 하면 1들이 있는 곳에 $a_1, a_1-1,\ldots,1$ 을, 2들이 있는 곳에 $a_1+a_2, a_1+a_2-1,\ldots,a_1+1$ 을, … 이렇게 써내려나가면 순열을 얻을 수 있게 되고, 임의의 순열에 대해서는 $a_1, a_1-1, \ldots, 1$ 이 부분수열이 되는 최대의 $a_1$ 을 잡아 그들에 1을, $a_1+a_2, a_1+a_2-1,\ldots,a_1+1$ 이 부분수열이 되는 최개의 $a_2$ 를 잡아 그들에 2를, … 이렇게 써내려나가면 꽉찬 수열을 얻게 되며 이 둘이 서로 역대응이 된다.

5번은 처음 본 문제. 편의상 $m = a+b-n$ 으로 두고, $1 \times 1$ 블록 $m$ 개와 $1 \times 2$ 블록 $n$ 개를 일렬로 늘어놓되 왼쪽의 $1 \times b$ 부분이 이 블록들로 딱 들어맞게 채워지는 경우의 수를 생각한다. (단 $n \leq b \leq m+n$ ) 그러면 $1 \times b$ 안의 $1 \times 2$ 의 개수가 $k$ 라 하면 $\times 1$ 의 개수는 $b-2k$ 이므로 이 왼쪽 파트를 채우는 경우의 수가 $\binom{b-k}{k}$ 가 되고 오른쪽은 $1 \times 2$ 가 $n-k$ 개, $1 \times 1$ 이 $m-b+2k$ 개이므로 오른쪽 파트를 채우는 경우의 수가 $\binom{m+n-b+k}{n-k} = \binom{a+k}{n-k}$ 개가 된다. 이 둘을 곱해 $k$ 에 대해 더하면 좌변이 바로 이 경우의 수가 됨을 알 수 있다. 한 편 이 경우의 수를 $f_b(m,n)$ 이라 하면 전체 경우 중에서 $b$ 에 해당하는 위치를 $1 \times 2$ 가 덮는 경우를 제외하여 세면 되는데, 그 $1 \times 2$ 를 제외하고 생각하면 경우의 수가 $f_{b-1}(m,n-1)$ 이 된다. 즉 $f_b(m,n) = \binom{m+n}{m} - f_{b-1}(m,n-1)$ 이 되므로 $f_b(m,n) = \binom{m+n}{m} - \binom{m+n-1}{m} + \cdots = \binom{m+n-1}{m-1} + \binom{m+n-3}{m-1} + \cdots$ 가 되는데 이게 바로 우변이 된다.

6번은 Generalized Fisher’s inequality로 알려진 문제이다. 1940년 Ronald Fisher가 제안한 문제로 design theory의 fundamental result 중 하나. 이에 대해선 다음과 같은 깔끔한 증명이 있다. $v_i \in \mathbb{R}^n$ 의 $j$ 번째 component는 $j \in X_i$ 일 때 1, 아닐 때 0이 되도록 벡터 $v_1, \ldots, v_m$ 을 정의한다. 만약 이들이 $\mathbb{R}$ 에 대해 linearly dependent했다면 $\sum_{i=1}^m a_i v_i = 0$ 인 전부가 0은 아닌 실수 $a_i$ 들이 존재해야 한다. 그러면 $0 = \left|\sum_{i=1}^m a_i v_i \right|^2 = \sum_{i=1}^m a_i^2 |v_i|^2 + 2\sum_{i < j} a_i a_j v_i \cdot v_j = \sum_{i=1}^m a_i^2 |X_i| + 2\sum_{i < j} a_i a_j = \sum_{i=1}^m a_i^2 \left(|X_i|-1 \right) + (\sum_{i=1}^m a_i)^2 \geq 0$ 이 되어 마지막 부등식에서 등호가 성립하게 된다. $a_i^2 (|X_i|-1) = 0$ 에서 임의의 $i$ 에 대해 $a_i=0$ 이거나 $|X_i|=1$ 이어야 하는데 $a_i$ 들은 전부 0일 수는 없으므로 원소 개수가 1개인 $X_i$ 가 1개 이상 있어야 한다. 그런데 원소 개수가 1개인 $X_i$ 는 최대 1개까지만 가능하므로, 그러한 $i$ 는 유일하게 존재한다. 편의상 $|X_1|=1$ 이라 하면 $a_1 \neq 0, a_2, a_3, \ldots, a_n = 0$ 이 된다. 그러나 $\sum_{i=1}^m a_i$ 역시 0이어야 하므로 모순을 얻게 되어 $m$ 개의 벡터들이 linearly independent하게 된다. dimension이 $n$ 인 vector space에서 그런 개수는 $n$ 이하이므로 증명이 끝난다. 이 풀이는 1949년 R. C. Bose가 증명한 것으로 알려져있다.

이 문제도 올림피아드 연습문제로 자주 등장했는데 실제 시험에도 나왔는지는 모르겠다. 선형대수를 쓰지 않는 풀이 역시 있는데, $r \times c$ 행렬의 모든 항이 0 또는 1일 때 row sum을 $R_i$ , column sum을 $C_j$ 라 하고 $0<R_i <c, 0 < C_j < r$ 이라 가정하였을 때 만약 $a_{ij}=0 \Rightarrow C_j \geq R_i$ 가 항상 성립한다면 $r \geq c$ 가 된다는 보조정리를 이용하는 것. (이 보조정리는 귀류법 가정 하에서 $\frac{(1-a_{ij})R_i}{c-R_i} < \frac{(1-a_{ij})C_j}{r-C_j}$ 를 전부 합하는 것으로 증명할 수 있다) 행에는 $n$ 개의 원소를, 열에는 $m$ 개의 집합을 대응시키고 $i \in X_j$ 이면 $a_{ij}=1$ , 아니면 0이라고 뒀을 때 한 행이 전부 0이거나 1인 경우를 제외시킬 수 있다. $a_{ij}=0$ 이면 $i \not \in A_j$ 가 되는데 이 때 $i$ 행의 또 다른 1이 있어 $a_{ik}=1$ 이라 하면 $X_k \cap X_j = \{l\}$ 가 되어 $a_{lj}=1$ 이 된다. 즉 $j$ 열의 한 1로 대응한다고 볼 수 있고, 이것이 injective함을 보일 수 있다. 따라서 보조정리의 전제조건이 성립하게 되어 증명이 끝난다.

위 풀이와 비슷한 풀이를 이용한게 1999년 이란 수학 올림피아드에서 등장한 적이 있다. $n$ 개의 단위원이 한 평면 위에 있어 어떤 두 원도 서로 접하지 않고 이 원들 위의 점들로 이루어진 집합이 연결집합이었다면 교점의 개수는 $n$ 개 이상임을 증명하는 문제인데, $R_i > 0, C_j > 0$ 이고 $a_{ij}=1 \Rightarrow C_j \geq R_i$ 가 성립하면 $r \geq c$ 가 성립함을 보이면 비슷하게 해결할 수 있다.