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 풀이가 잘 알려져 있다. 임의의 꽉찬 수열을 잡아 ia_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 2n-k개, 1 \times 1m-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}^nj번째 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가 성립함을 보이면 비슷하게 해결할 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중