본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[슬기로운 수학생활] 슬27. Log-concave한 수열들
수학동아 2022.07.01 09:32 조회 628

슬기로운 수학생활 27번

 

 

 

Log-concave한 수열들

 

 

 

문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생

 

 

 

 

양수로 이루어진 길이 $n$의 수열 $a_1, a_2, \cdots, a_n$이 있다.

 

만약 모든 $2 \leq i \leq n - 1$에 대해 부등식 $a_i^2 \geq a_{i-1}a_{i+1}$이 성립하면 수열 $a_1, a_2, \cdots, a_n$이 log-concave하다고 정의하자.

 

수학에서 등장하는 많은 수열들이 log-concave하다. 이를테면 임의의 자연수 $n$에 대해 파스칼 삼각형의 $n+1$번째 가로줄 $\binom{n}{0}, \binom{n}{1}, \cdots, \binom{n}{n}$은 log-concave하다.

 

 

 

 

문제 1. 왜 모든 자연수 $n$에 대해 이항계수 수열 $\binom{n}{0}, \binom{n}{1}, \cdots, \binom{n}{n}$이 log-concave할까? 다양한 방법을 찾을 수 있다. 이항계수의 공식을 대입해서 증명하는 것부터 해보자. 다른 방법은 값 $\binom{n}{i}^2 - \binom{n}{i-1}\binom{n}{i+1}$이 뭔가를 세는지를 증명하는 것이다. 그러면 뭔가를 세는 개수는 무조건 0 이상일 수 밖에 없기에 log-concavity가 바로 증명이 된다.

 

 

 

 

문제 2. 자연수 $n$에 대해 다항식 $x(x+1)(x+2)\cdots(x+(n-1))$을 전개하자. 이때 나오는 다항식이  $s_{n, 0} + s_{n, 1}x + s_{n, 2}x^2 + \cdots + s_{n, n}x^n$라고 할 때, 순서대로 나오는 계수 $s_{n, 0}, s_{n, 1}, \cdots, s_{n, n}$의 수열을 제 1종 스털링 수(Stirling number of the first kind)라고 한다. 이 수에 대해서 구글에 검색하면 더 많은 정보를 얻을 수 있다 (어쩌면 영어로 검색하는 게 더 많은 정보가 나올 수도 있다). 각 $n$에 대해 제 1종 스털링 수의 수열이 log-concave함을 다양한 방법으로 증명해보자.

 

 

 

 

문제 3. Eulerian number $A(n, m)$이 무엇인지를 찾아보자. 고정된 자연수 $n$에 대해 수열 $A(n, 0), A(n, 1), \cdots, A(n, n-1)$이 log-concave함을 증명해보자.

 

 

백진언 연구원의 팁

인터넷 검색을 통해 모르는 내용에 대해 많은 정보를 얻을 수 있어요. 적극적으로 검색해서 내용을 찾아보자! 답이 있는 논문을 검색해서 공부하는 것도 좋아요. - 단 이때는 풀이를 쓸때 출처를 명확하게 하세요.

  •  
    부분해결
    굴러가던 도토리 Lv.5 2022.07.02 23:30 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      출제자(슬기) Lv.4 2022.07.03 09:42

      문제 1을 공식을 대입해서 잘 풀어주셨습니다! 다른 친구들도 볼 수 있게 비공을 풀어줘도 고마울 것 같아요 ㅎㅎ

      좋아요0
  •  
    굴러가던 도토리 Lv.5 2022.07.04 12:06

    1번 문제의 풀이를 공개댓글로 다시 올립니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    Scubed Lv.7 2022.07.05 23:58

    (1)에서 나타내는 식이 다음과 같은 경우인 것 같아요

    1~n까지의 수가 있을 때 i개의 수를 뽑고, 다시 i개의 수를 뽑아(중복 가능) 수들을 나열했을 때(순서 무관) 나오는 경우 중 중복을 제외한 경우

    예를 들면 n=3, i=2일 때 12/12-1122, 12/13-1123, 12/23-1223, 13/12-1123, 13/13-1133, 13/23-1233, 23/12-1223, 23/13-1233, 23/23-2233

    에서 1122,1123,1223,1133,1233,2233의 6개

     

    이제 증명해봐야겠죠...ㅠ

    댓글 작성하기 좋아요0 댓글수4
    •  
      Scubed Lv.7 2022.07.06 11:44

      조금 더 세련되게 정리하면

      "1~n이 적혀있는 카드가 각각 2장씩 총 2n개 있을 때 이 중 2i개를 뽑는 경우의 수"

      가 되겠네요

      좋아요0
    •  
      Amath Lv.8 2022.07.08 22:39

      (대댓글 말고 댓글에) Scubed 님이 말한 것을 i=2가 아닌 경우에 생각해 보세요. 그때 반례가 무수히 많이 존재해요. i=2일 때는 무언가의 중복에 관련해서 특수한 성질을 갖기 때문에 i=2일 때는 성립하는 것으로 보여요. 

      좋아요0
    •  
      Scubed Lv.7 2022.07.09 20:43

      @Amath

      어...제가 여러 개 더 해봤는데 아직 반례를 찾지 못해서...혹시 반례를 들어주실 수 있나요?

      좋아요0
    •  
      Amath Lv.8 2022.07.11 20:32

      어.. 제가 잘못 생각한 것 같기도 하네요,. 

      좋아요0
  •  
    다시 도전
    Scubed Lv.7 2022.07.11 23:11

    1번의 조합론적 풀이입니다.

    (i) 1부터 n까지의 수 중 i개를 뽑아 크기 순대로 나열하여 한 행을 만들고, 다시 1부터 n까지의 수 중 i개를 뽑아 크기 순대로 나열하여 전에 만든 행 밑에 행을 추가하여 행이 2개, 열이 i개인 행렬을 만듭시다. 그러면 가능한 행렬의 총 개수는 \begin{pmatrix} n\\ i\end{pmatrix}^2 이 됩니다.

    (ii) 이번에는 1부터 n까지의 수 중 (i+1)개를 뽑아 크기 순대로 나열하여 한 행을 만들고, 다시 1부터 n까지의 수 중 (i-1)개를 뽑아 크기 순대로 나열하여 전에 만든 행 밑에 행을 추가하여 행이 2개, 열이 (i+1)개인 불완전한 행렬을 만듭시다. 그러면 가능한 불완전한 행렬의 총 개수는 \begin{pmatrix} n\\ i+1\end{pmatrix}\begin{pmatrix} n\\ i-1\end{pmatrix}이 됩니다.

    이제 (i)의 경우의 수가 (ii)의 경우의 수보다 많은 것을 증명하면 됩니다. 이제 (ii)에서 만든 불완전한 행렬에 조금의 변화를 줍시다. (ii)의 불완전한 행렬의 윗행에는 (i+1)개의 숫자가 있고, 아랫행에는 (i-1)개의 숫자가 있으므로 윗행에는 있고 아랫행에는 없는 숫자가 반드시 존재합니다. 그 수들 중 가장 큰 수를 윗행에서 아랫행으로 옮기면 불완전한 행렬은 완전한 행렬이 됩니다. 여기서 가장 큰 수를 옮기는 이유는 경우의 수가 중복되는 것을 제외하기 위해서입니다. 이렇게 변환을 취해주면 완전한 행렬로 변한 행렬의 총 개수는 \begin{pmatrix} n\\ i+1\end{pmatrix}\begin{pmatrix} n\\ i-1\end{pmatrix}인데, 이 행렬들은 모두 (i)의 경우에 "포함"됩니다. 따라서 \begin{pmatrix} n\\ i\end{pmatrix}^2이 \begin{pmatrix} n\\ i+1\end{pmatrix}\begin{pmatrix} n\\ i-1\end{pmatrix}보다 크거나 같고, 이항계수 수열의 로그 오목성은 증명됩니다.

     

    댓글 작성하기 좋아요1 댓글수4
    •  
      Amath Lv.8 2022.07.12 18:39

      (ii)에 변화를 주었을 때, 열 i+1개가 꽉 차 있는 행의 가장 큰 수가 다른 행의 가장 큰 수보다 작을 수 있지 않나요?

       

      그러면 아래에 채워진 행에 있는 수가 같은 것이 있을 수 있고, (i)에 포함되지 않는 경우가 있을 수도 있는 것 같은데..

      좋아요0
    •  
      Scubed Lv.7 2022.07.12 23:07

      아랫 행과 겹치지 않는 수들 중 가장 큰 수를 밑으로 내리는 시행입니다

      그래서 포함되지 않는 경우는 없을 것 같아요

      좋아요0
    •  
      출제자(슬기) Lv.4 2022.07.14 14:55

      n=7, i=4일때 (12347, 156), (12346, 157) 모두 (1234, 1567)로 가는 것 같아요!

      좋아요0
    •  
      Scubed Lv.7 2022.07.14 21:28

      @출제자(슬기)

      어 그렇네요...ㅠㅠ

      폐---기

      좋아요0
  •  
    해결
    Scubed Lv.7 2022.07.26 00:14

    일반화? 시킨 풀이 올립니다.

    제가 증명할 내용은 다음과 같습니다.

    a항들이 모두 양수일 때,

    (x+a_1)(x+a_2)...(x+a_k)를 전개한 식의 x^{i}의 계수를 b_i라 할 때, b_i는 항상 로그 오목하다는 것입니다.

    (증명)

    b_i는 i개의 다른 a들의 곱의 합으로 이루어져있습니다. 우리는 다음을 증명해야 합니다.

    b_i^2\geq b_{i-1}b_{i+1}-------***

    이를 증명하기 위해 저는 다음과 같이 생각했습니다.

    우선 ***의 우변에서 나오는 항들은 다음과 같은 꼴을 이룰 것입니다.

    a_{s_1}^2a_{s_2}^2...a_{s_m}^2a_{t_1}a_{t_2}...a_{t_2_n}, 2m+2n=2i

    여기서 첨자가 s인 a항들은 b_{i-1}와 b_{i+1} 둘 다에서 겹친 항들이고, 첨자가 t인 a항들은 b_{i-1}와 b_{i+1} 중 하나에서만 나온 항들입니다.

    여기서 같은 값을 가지는 항이 나오는 총 경우의 수는 _{2n}C_{n-1}입니다. 이는 첨자가 s인 a항들은 b_{i-1}과 b_{i+1}에 둘 다 포함되어야 하므로 경우의 수에 영향이 없지만

    첨자가 t인 a항들은 둘 중 하나에서만 나오기 때문입니다. 

    반면, ***의 좌변에서도 같은 항이 나올 수 있습니다. 그런데 좌변에서는 값을 가지는 항이 나오는 총 경우의 수가 _{2n}C_{n}이 됩니다. 

    이는 같은 꼴의 항의 개수가 좌변이 우변보다 많음을 의미하며, 모든 항들은 양수이기 때문에 좌변이 항상 우변보다 큽니다.

    따라서 항상 b_i는 로그 오목합니다.

     

    이제 위의 사실을 가지고 (1)과 (2)는 쉽게 증명할 수 있습니다.

    (1) a_i=1인 경우에 해당합니다.

    (2) a_i=i인 경우에 해당합니다.

     

    +(3)도 같이 되면 좋겠는데...아직 못 찾겠네요

     

    댓글 작성하기 좋아요0 댓글수2
    •  
      출제자(슬기) Lv.4 2022.08.01 16:52

      저도 생각하지 못했던 방법으로 잘 해결하셨어요! 다른 친구들이 보고 또 배울 수 있게 혹시 어떻게 생각했는지 알려줄 수 있나요?

      좋아요0
    •  
      Scubed Lv.7 2022.08.01 17:35

      저는 처음에는 a항들이 로그 오목일 때 b항들도 로그 오목인 줄 알고 증명을 시작했는데 하다보니 a항들이 양수이기만 하면 b항들이 항상 로그 오목이었어서 쉽게 해결할 수 있었어요

      좋아요0
  •  
    RedoC Lv.5 2022.08.03 13:53 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      RedoC Lv.5 2022.08.05 00:29

      풀이 공유합니다.

      ---

      문제 2입니다.

       

      좋아요0
  •  
    Scubed Lv.7 2022.08.05 00:04
    확인요청중

    3번 증명입니다.

    우선 위키피디아에서 오일러 수는 다음과 같은 성질이 있음을 알아냈습니다.

    A(n, m)=(n-m)A(n-1,m-1)+(m+1)A(n-1,m)

    이 성질을 이용해서 수학적 귀납법을 적용하려 합니다.

    (i) n=1, 2, 3일 때

    각각 1/1, 1/1, 4, 1이 되므로 성립합니다.

    (ii) n=k에서 성립한다고 가정합시다. 즉, A(k,m)^2\geq A(k,m-1)A(k,m+1)을 만족합니다.

    이제 우리는 다음을 증명하려 합니다. A(k+1,m)^2-A(k+1,m-1)A(k+1,m+1)\geq 0

    이를 위의 점화식을 통해 정리하겠습니다. 과정은 생략합니다...

     [(k-m)^2A(k-1,m-1)^2-(k-m-1)(k-m+1)A(k-1,m)A(k-1,m-2)] +[(m+1)^2A(k-1,m)^2-m(m+2)A(k-1,m-1)A(k-1,m+1)] +(mk-k^2+2k-m)A(k-1,m-1)A(k-1,m)-(mk-k^2+2k-m+2)A(k-1,m-2)A(k-1,m+1)\geq 0

    여기서 대괄호로 묶인 2개의 항을 봅시다. 이 두 항들은 가정에 의해 다음과 같이 쓰일 수 있습니다.

    [(k-m)^2A(k-1,m-1)^2-(k-m-1)(k-m+1)A(k-1,m)A(k-1,m-2)] \geq A(k-1,m-1)^2 , [(m+1)^2A(k-1,m)^2-m(m+2)A(k-1,m-1)A(k-1,m+1)] \geq A(k-1,m)^2

    그러므로 식은 조금 더 간단히(???) 변합니다.

    A(k-1,m)^2+A(k-1,m-1)^2 +(mk-k^2+2k-m)A(k-1,m-1)A(k-1,m)-(mk-k^2+2k-m+2)A(k-1,m-2)A(k-1,m+1)

    여기서 앞의 두 항에 산술기하평균 부등식을 씁시다. 그럼 다음과 같이 변합니다.

    (mk-k^2+2k-m+2)A(k-1,m-1)A(k-1,m)-(mk-k^2+2k-m+2)A(k-1,m-2)A(k-1,m+1)\geq 0

    계수가 같습니다!!! 저 계수를 인수분해해보면 (k-m+1)(m+2)로 양수임이 틀림없습니다. 그러니 나눠주면 최종적으로 증명할 식은 다음과 같습니다.

    A(k-1, m-1)A(k-1,m)\geq A(k-1,m-2)A(k-1,m+1)

    이 식은 생각보다 쉽게 증명됩니다.

    A(k-1, m-1)^2\geq A(k-1,m)A(k-1,m-2)

    A(k-1, m)^2\geq A(k-1,m-1)A(k-1,m+1)

    가정에 의해 두 식이 만족되고 두 식을 곱하면 위의 식이 나옵니다.

    따라서 n=k일 때 성립한다고 가정했을 때 n=k+1인 경우에도 성립하므로, 수학적 귀납법에 의해 오일러 수는 로그-오목합니다.

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

  • ☎문의 02-6749-3911