KAIST POW 2019-02 Simplification of an expression with factorials

2019. 3. 29. 12:50수학 문풀/기타

문제 링크

 

2019-02 Simplification of an expression with factorials - KAIST Math Problem of the Week

For any positive integers m and n, show that \[ C_{n,m} = \frac{(mn)!}{(m!)^n n!} \] is an integer. Recommend on Facebook Tweet about it Print for later Tell a friend Related

mathsci.kaist.ac.kr

POW라는 걸 믿을 수 없을 정도로 쉬운 문제가 나와버렸다. 스포방지 안할래...


문제. 모든 자연수 \(n,m\)에 대해, 다음이 정수임을 보여라.

$$ C_{n,m} = \frac{(nm)!}{(m!)^{n}n!} $$

 

Sol 1.

 

\(C_{n,m}\)은 \(nm\)개의 수를 구분이 가지 않는 \(n\)개의 group으로 나누는 경우의 수이므로 당연히 정수이다.

 

Sol 2.

 

\(\displaystyle n!C_{n,m} = \begin{pmatrix} m \\ m \end{pmatrix} \begin{pmatrix} 2m \\ m \end{pmatrix} \cdots \begin{pmatrix} nm \\ m \end{pmatrix}\)이다.

\(\begin{pmatrix} km \\ m \end{pmatrix} = \frac{km}{m} \begin{pmatrix} km-1 \\ m-1 \end{pmatrix} \equiv 0 (\text{mod } k)\)이므로 주어진 식의 우변은 \(n!\)의 배수이다.

'수학 문풀 > 기타' 카테고리의 다른 글

KAIST POW 2019-03 Simple Spectrum  (0) 2019.03.29
Balkan MO 2015  (0) 2019.02.09
Putnam 2017 풀이 - 풀리는 것만  (0) 2018.11.30
2018 대수경 2분야 5번 풀이  (0) 2018.11.24
2017 Benelux MO 풀이  (0) 2018.09.29