본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대51. 이항계수의 성질
수학동아 2021.03.02 11:42 조회 1482

이항 계수 nCr=\binom{n}{r}의 정수론적 성질에 대한 재미있는 문제들을 소개하려 합니다.

 

먼저 ijn은 정수이고 1\leq i< j\leq \frac{n}{2}임을 가정합시다. 양의 정수 ab에 대하여 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임을 증명하세요.

  •  
    Scubed Lv.6 2021.03.05 23:59

    일단 1번은 n이 소수일 때는 성립하니깐 저는 'n=a,b에서 성립할 때 n=ab에서 성립한다'라고 놓고 풀어보고 있는데 잘 안되네요...ㅇㅅㅇ

    댓글 작성하기 좋아요0 댓글수1
  •  
    Sait2000 Lv.3 2021.03.23 06:04

    구글 검색 능력을 측정하는 게 아니라는 건 알지만... 찾은 건 찾은 거니까 올립니다

    P. Erd ̋os and G. Szekeres, Some  number  theoretic  problems  on  binomial  coefficients.

    http://combinatorica.hu/~p_erdos/1978-46.pdf

     

    내용은 대충 1, 2번을 한 번에 증명하고 3번의 몇개를 보이고 4번이 참이지 않을까 추측하는 내용이네요

    1,2번 증명은 다음과 같습니다. C(n, j)C(j, i) = n! / ( (n-j)! (j-i)! i! ) = C(n, i)C(n-i, j-i) 입니다.

    따라서 C(n, i) 는 C(n, j)C(j, i)의 약수입니다. 따라서 두 자연수 a, b가 존재하여 a * b = C(n, i)이고 a는 C(n, j)의 약수, b는 C(j, i)의 약수라 합시다.

    이때 gcd(C(n, i), C(n, j)) ≥ a = C(n, i) / b ≥ C(n, i) / C(j, i) ≥ (n/j) ^ i ≥ 2^i 입니다.

    등호는 홀수 소수 p에 대해 C(2p, p)는 p의 배수가 아니므로 gcd(C(2p, 1), C(2p, p)) = gcd(2p, C(2p, p)) = 2가 되므로 등호가 성립하는 경우가 무한히 많습니다.

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911