http://mathsci.kaist.ac.kr/pow/2009/02/06/2009-1 에 출제된 문제이다.

Let a_1 \le a_2 \le \cdots \le a_n be integers. Prove that

\prod_{1\le j < i \le n} \frac{a_i-a_j}{i-j}

is an integer.

이 문제의 식은 나에게는 매우 익숙한 식이라, 이 식이 어떤 정수 행렬의 행렬식이라는 것을 바로 알아 챌 수 있었다. 하지만 아직 학생들의 답이 올라오지 않을 때였기에, 이제서야 풀이를 써 본다. 홈페이지에 가보면 학생들의 풀이 중 가장 좋은 풀이가 올라와 있다. 내 풀이와 근본적으로 같은 것이라, 내 풀이의 핵심아이디어만 뽑아 따로 적어본다.

핵심 아이디어는 행렬 M

\large M = \left( \begin{array}{cccc} {a_1 \choose 0}&{a_1 \choose 1}&\cdots&{a_1 \choose n-1}\\ {a_2 \choose 0}&{a_2 \choose 1}&\cdots&{a_2 \choose n-1}\\ \vdots&\vdots&\ddots&\vdots\\ {a_n \choose 0}&{a_n \choose 1}&\cdots&{a_n \choose n-1} \end{array}\right)

의 모든 성분은 정수이기 때문에 그것의 행렬식 det(M) 은 정수가 된다는 것이다. 그러므로

\det(M)=\prod_{1\le j < i \le n} \frac{a_i-a_j}{i-j}

임을 증명하면 충분하다. Vandermonde Matrix 의 행렬식을 구하는 방법으로 행렬 M의 행렬식을 구할 수 있다. (수식 쓰기가 어려워 생략!)

조금 더 덧붙이면, 이항계수들로 구성된 행렬의 행렬식은 때에 따라서 조합론적으로 해석이 가능한 수가 된다. 위의 행렬 M 의 행렬식도 마찬가지인데, a_1\ge 0 일때, 다음과 같이 조합론적으로 해석이 가능하다.

좌표 A_i=(i-1,i-1) 에서 좌표 B_i=(a_i,0) 로 향하는 최단 격자 경로를 L_i 라고 하자. 이 때 n개의 최단 격자 경로 L_1, L_2, \ldots, L_n 이 서로 만나지 않는 경우의 수는

\large \det \left( \begin{array}{cccc} {a_1 \choose 0}&{a_1 \choose 1}&\cdots&{a_1 \choose n-1}\\ {a_2 \choose 0}&{a_2 \choose 1}&\cdots&{a_2 \choose n-1}\\ \vdots&\vdots&\ddots&\vdots\\ {a_n \choose 0}&{a_n \choose 1}&\cdots&{a_n \choose n-1} \end{array}\right)

이 된다.

+ Recent posts