POLYMATH51.md

수학동아 Polymath Problem 51

Number Theory

Problem

Reference

먼저 $i, j, n$은 정수이고 $1\leq i< j\leq \frac{n}{2}$임을 가정합시다. 양의 정수 $a$, $b$에 대하여 $a$와 $b$의 최대공약수를 $(a, b)$라고 하고, $a$와 $b$가 공통으로 가지는 소인수 중 가장 큰 것을 $p(a,b)$라 하겠습니다.

문제 1. $\begin{pmatrix} \binom{n}{i},\binom{n}{j} \end{pmatrix}\geq 2$임을 증명하세요.

문제 2. $\begin{pmatrix} \binom{n}{i},\binom{n}{j} \end{pmatrix}\geq 2^{i}$임을 증명하고, 등호가 성립하는 경우가 무한히 많음을 증명하세요.

문제 3. $p\begin{pmatrix} \binom{n}{i},\binom{n}{j} \end{pmatrix}=i$가 성립하는 경우를 찾아보세요.

문제 4. $p\begin{pmatrix} \binom{n}{i},\binom{n}{j} \end{pmatrix}\geq i$임을 증명하세요.

문제 1

Idea

$\binom{n}{j}$를 $\binom{n}{i} \times A$꼴로 나타내면 이를 이용해 gcd를 구할 수 있을 것이다.

Solution

Also Uploaded to Gist

$\binom{n}{j} = \frac{n!}{(n-j)!j!} = \frac{n!}{(n-i)!i!} \cdot \frac{(n-i)!i!}{(n-j)!j!} = \binom{n}{i} \cdot \frac{(n-i)!i!}{(n-j)!j!}$

$ = \binom{n}{i} \cdot \binom{n-i}{j-i} \cdot \frac{i!(j-i)!}{j!} = \binom{n}{i} \cdot \binom{n-i}{j-i} \cdot \frac{1}{\binom{j}{i}}$

즉, $\binom{n}{j} \binom{j}{i} = \binom{n}{i} \binom{n-i}{j-i}$

이때 $\binom{n}{j}$와 $\binom{n}{i}$이 서로소라면 (Still thinking)

$\therefore Ans=$