본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대51. 이항계수의 성질
수학동아 2021.03.02 11:42 조회 2415

대한수학회 51번

 

이항계수의 성질

 

 

문제 출제자 : 이지운 KAIST 수리과학과 교수

 

 

이항 계수 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.7 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
  •  
    pure math Lv.7 2022.06.06 15:23
    확인요청중

    4번

    베르트랑 공준에 따라 n과 n/2 사이에는 소수가 하나 이상 있으니 증명됩니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      강지원 멘토 Lv.4 2022.06.07 10:56

      그 소수가 실제로 n\choose in\choose j의 소인수가 된다고 보장할 수 없습니다. 예를 들어 i=1이면 {n\choose 1}=n은 그 소수의 배수가 안되는 경우가 있습니다(물론 문제의 명제는 성립합니다). 

      좋아요0
    •  
      pure math Lv.7 2022.06.07 21:01

      아하 넵!

      좋아요0
  •  
    pure math Lv.7 2022.08.06 12:23
    확인요청중

    1, 2번은 앞에 분이 증명하셔서 생략합니다.

    3은 불가능합니다. 그 이유는 Sylvester and Schur정리에 따라 C(n,i)에는 i보다 큰 소인수가 존재하고, 그 소인수 중에 동시적으로 소인수가 되는 (p(C(n,i), C(n,j)))소인수가 존재하기 ㄸ문입니다. --> 이 증명은 4번에서

    4. 위의 정리를 동치인 명제로 바꾸면 구간의 길이가 i이고 최소 원소가 i보다 크면 그 구간에는 i보다 큰 소수의 배수가 있다는 것입니다. 따라서 C(n,i)=n!/i!(n-i)!에서, i보다 큰 어떤 소수가 C(n,i)의 소인수라 할 때, 그 소수를 p라 하고, p(x)=x!에 들어있는 p의 지수라 할 때, p(i)=1, p(n-i)=m이라 한다. 그러면 C(n,i)에는 p의 지수가 1개이므로 p(n)=m+1이 된다.

    여기서, C(n,j)=n!/j!(n-j)!이면, j!=1이하, p(n-j)<p(n-i)=m, p(n)=m+1이다. C(n,j)에 들어있는 p의 지수는 p(n)-p(j)-p(n-j)>=m+1-1-(m-1)=1이므로, 지수는 최소 1개가 있다. 그러므로, C(n,i)에 속하는 i보다 "큰" 소인수가 C(n,j)에도 속하므로 p(C(n,i), C(n,j))>i입니다.

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

  • ☎문의 02-6749-3911