주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대9. 수열의 성질 / 힌트를 추가했어요!

2017.08.31

같이 풀어볼까?

네이버밴드 구글플러스

양의 정수 \large n에 대해 순열(일대일대응) \large $\sigma: \{ 1, 2, \dots, n \} \to \{ 1, 2, \dots, n \}$를 모두 모아놓은 집합 \large S_n을 생각합니다. 순열 \large $\sigma \in S_n$에 대해 \large $(\sigma(i_1),\, \sigma(i_2),\, \dots,\, \sigma(i_k))$을 $\sigma$을 \large \sigma의 부분수열이라고 부릅니다. (단, \large \large $1 \leq i_1 < i_2 < \dots < \ i_k \leq n$

부분수열 \large $(\sigma(i_1), \sigma(i_2), \dots, \sigma(i_k))$이 \large $\sigma(i_1) < \sigma(i_2) < \dots \sigma(i_k)$를 만족시킨다면, 이 부분수열을 증가부분수열이라고 부릅니다.

예를 들어 \large n=5일 때, 순열 \large \sigma가 \large $(\sigma(1),\, \sigma(2),\, \sigma(3), \,\sigma(4),\, \sigma(5)) = (3, 1, 2, 5, 4)$로 주어졌다면 \large (1, 2, 4)는 \large \sigma의 부분수열이며, 증가부분수열입니다.

순열 \large \sigma에 대해  \large L(\sigma)를 \large \sigma의 증가부분수열 중 가장 긴 것의 길이로 정의하고, \large L(\sigma)를 사용해 다음과 같은 수열을 다시 정의합니다.

\large \ell_n = \frac{1}{n!} \sum_{\sigma \in S_n} L(\sigma)

 

문제1. 위의 정의로부터 \large $\ell_1,\, \ell_2,\, \ell_3,\, \ell_4$의 값을 구하세요.

 

문제2. 모든 양의 정수 \large n에 대해 \large $\ell_n \geq \sqrt{n}$ 임을 보이세요.

문제 풀이에 진전이 없어 힌트를 추가했어요. 문제 2번을 풀 때 참고하세요!

힌트!  

증가부분수열의 정의에서 '증가'를 '감소'로 바꿔서 감소부분수열을 정의한 뒤 감소부분수열 중 가장 긴 것의 길이를 {\color{Blue} D(\sigma )}라 합니다. 그 후 {\color{Blue}L(\sigma ) D(\sigma )\geq n} 임을 증명해 보도록 합시다.

 

문제3. 어떤 양수 \large C가 존재해 모든 양의 정수 \large n에 대해 \large $\ell_n \leq C \sqrt{n}$이 성립함을 보이세요.

 

*알립니다

구머 친구에 의해 1, 2번이 해결됐습니다~. 남은 3번 문제도 화이팅!!

댓글 24

  • 수학동아 2017.08.31 18:07:24

    이제부터는 댓글에 파일을 첨부할 수 있어요! 풀이를 올릴 때 참고하세요!

    좋아요0 댓글수0
  • 여백 패르마 2017.08.31 20:33:18

    l1에서 ik들은 모두 1이 됩니다.모두 같게 되니 증가부분수열은 없고,즉 l1은 0이 됩니다.

    좋아요0 댓글수1
    • 구머 2017.08.31 21:51:13

      아마 {1}이 증가수열로 취급될 것 같습니다

       

      좋아요0
  • 수돌이 2017.08.31 20:46:37

    총 순열의 개수가 n!개이므로 l_n은 임의의 S_n중 하나의 순열을 뽑았을 때 그 순열의 최대증가부분수열의 길이의 평균값(기댓값)이라 할 수 있겠네요!

    수학적 귀납법을 쓰면 좋을 것 같습니다. 좀 있다가 저는 돌입할게요 그때까지 여러분 화이팅!

    좋아요0 댓글수0
  • 구머 2017.08.31 21:49:45

    l_1=1 l_2=1.5 l_3=2 l_4=29/12

    풀이는 그냥 단순노가다라서 생략하겠습니다.

    좋아요0 댓글수3
    • shine 2017.09.01 16:09:26

      l_4는 55/24 아닌가요?

      좋아요0
    • 구머 2017.09.01 17:42:36

      58/24 맞는것 같은데요..

       

      좋아요0
    • 수학자 2017.09.02 21:14:06

      l_4 = 29/12가 맞는 것 같습니다.

      좋아요0
  • 구머 2017.09.05 18:58:18

    문제 아이디어 제공: {a1,a2,...,an}에서 집합의 원소의 개수가 n-1개인 집합 n개를 뽑을 수 있습니다. 이 n개의 집합들의 각각의 가장 긴 증가부분수열의 길이를 구해보면, n개의 길이들이 나오는데, 이 길이들은 많아야 2종류이며(예를 들자면, {1,2,4,3}에서는 길이가 3,3,2,2로 나옵니다), {a1,a2,...an}의 가장 긴 증가부분수열의 길이는 n개의 길이들 중에서 가장 긴것이 됩니다.(단 {1,2,3,..,n}은 예외)

    좋아요0 댓글수2
    • c언어 2017.09.06 00:23:10

      n개중에서 n-1개를 뽑을때 종류가 많아야 2종류 라는 것과, 그중 1가지가 n개의 증가부분수열의 최대값 이라는 것을 증명하실 수 있나요?

      좋아요0
    • 구머 2017.09.06 17:12:03

      가능합니다. 먼저 \sigma={a1,a2,.....an}의 가장 긴 증가부분수열을 {af(1),af(2),....af(m)}이라 하면, \sigma={1,2,.....n}인 경우를 제외하였을 때 m은 n-1보다 작거나 같습니다. 따라서 {af(1),af(2),....af(m)}을 포함하는 길이가 n-1인 수열이 존재하고(이 수열을....'최대수열'이라 정의해 봅시다), 그 수열의 가장 긴 증가부분수열의 길이는 m입니다. 또, 최대수열이 아닌 길이가 n-1개인 수열과 최대수열의 교집합은 길이가 n-2인 수열로, {af(1),af(2),....af(m)} 중에서 적어도 m-1개는 포함하게 되고, 따라서 이 수열의 가장 긴 증가부분수열의 길이는 적어도 m-1개보다 크거나 같고 m보다 작거나 같습니다.

      좋아요0
  • Cocopolis 2017.09.12 11:27:22 비밀댓글
    비밀댓글 입니다.
    댓글수0
  • 수학장 2018.01.25 21:21:23

    \sum _{\sigma\subset S_{n}}L(\sigma)\sum _{\sigma\subset S_{n}}D(\sigma)=\sum _{\sigma_{a},\sigma_{b}\subset S_{n}}(L(\sigma_{a})D(\sigma_{b}))>n\cdot n!\cdot n! 이걸 증명하면 되겠네요. 힌트 감사합니다.

    좋아요0 댓글수0
  • 구머 2018.01.27 01:32:48

    순열 \sigma_0={\sigma (1),\sigma (2),...\sigma (n)} 증가부분수열 L_{\sigma_0}을 귀납적으로 정의하자: L_{\sigma_0}=\left \{\sigma(i_1), \sigma(i_2), ...\sigma(i_k)\right \}라 할 때,

    (1) i1=1

    (2) ik+1은 \sigma(m)>\sigma(i_k), m>ik을 만족시키는 최소의 자연수 m을 ik+1이라고 정의한다. 만약 그런 자연수 m이 없다면, 수열 L_{\sigma_0}은 \left \{\sigma(i_1), \sigma(i_2), ...\sigma(i_k)\right \}로 결정된다. 

    이제 순열 \sigma_0={\sigma (1),\sigma (2),...\sigma (n)}에서 L_{\sigma_0}의 원소들을 제거한 수열을 \sigma_1 이라고 하자. 그리고, \sigma_1에서 L_{\sigma_1}을 뺀 순열을 \sigma_2라 하고,.. 이런 식으로 하면 결국 순열 \sigma={\sigma (1),\sigma (2),...\sigma (n)}는 L_\sigmaL_{\sigma_{1}}L_{\sigma_{2}}, ... ,L_{\sigma_{t-1}}로 이루어 질 것이다. 이제 L_{\sigma_0}L_{\sigma_{1}}L_{\sigma_{2}}, ... ,L_{\sigma_{t-1}}에서 각각 1개씩 t+1개의 수(n0, n1, ...,nt)를 잘 선택하면, 그 수들이 감소부분수열이 되게 할 수 있음을 보이자. 우선 n=1일 때는 잘 성립한다. 이제 n<=p-1일때 성립한다고 가정했을 때, \sigma_1는 원소의 개수가 p-1개 이하이므로 위 조건을 잘 만족시킨다. 이제 n1보다 왼쪽에 있고 숫자가 더 큰 수를 L_{\sigma_0}에서 찾으면 되는데, 만약 존재하지 않는다고 가정하면, n1은 L_{\sigma_0}안에 포함되어야 하므로 모순, 따라서 

    L_{\sigma_0}L_{\sigma_{1}}L_{\sigma_{2}}, ... ,L_{\sigma_{t-1}}에서 각각 1개씩 t개의 수(n0, n1, ...,nt)를 잘 선택하면, 그 수들이 감소부분수열이 되게 할 수 있따.

    이제 증가부분수열 중 가장 긴 것의 길이를 l이라 하면, t>=n/l이어야 하고, t는 감소순열이므로, l*t>=n이 성립.

    따라서 \large \ell_n = \frac{1}{n!} \sum_{\sigma \in S_n} L(\sigma)=\frac{1}{2}\frac{1}{n!} \sum_{\sigma\in S_n }L(\sigma )+D(\sigma )\geq \frac{1}{2}\frac{1}{n!}\sum_{\sigma\in S_n }2\sqrt{n}=\sqrt{n}

    좋아요1 댓글수7
    • 구머 2018.01.27 03:26:39

      제가 생각해도 서술 너무 못했네요ㅜㅜ 혹시 이해안되는 부분 있으면 바로 알려주세요

      좋아요0
    • 수학장 2018.01.27 08:55:16

      아이디어 너무 좋으셔요...ㅠㅠ

      저는 아무리 생각해도 쓸 만한 아이디어가 없는데 이렇게 빨리 푸시다니 대단하네요. 전체적으로 이해는 가요. 맞는 것 같아요

      좋아요0
    • 구머 2018.01.27 15:58:29

      ㅋㅋㅋ열심히 실험하다보니까 규칙성이 보이더라구요!

      좋아요0
    • 구머 2018.02.09 11:00:18

      확인 부탁드립니다.

      좋아요0
    • 김우현 기자 2018.02.20 09:05:23

      멋져요! 
      구머 친구의 풀이는 현재 확인 중에 있으니, 조금만 기다려 주세요!!! :)

      좋아요0
    • 김우현 기자 2018.03.12 11:48:28

      주정훈 멘토에 의뢰한 결과, 문제 2번은 정답입니다~. 출제한 교수님의 확인이 끝나면 부분해결 딱지를 붙이도록 할게요~.

      좋아요0
    • 김우현 기자 2018.03.15 17:21:50

      출제해 주신 이지운 교수님께 여쭤본 결과, 2번도 해결입니다! 대한수학회 9번 문제도 부분해결 딱지 부착! 

      좋아요0
  • 수학자 2018.03.17 10:57:04

    문제3은 아무래도 평균과 같은 성질을 써서 여러 수열들을 묶어서 생각해봐야 할 것 같습니다. 예를 들면, n!개의 수열을 n개씩 (n-1)!개의 그룹으로 묶어서 각각의 평균에 대한 성질을 밝히는 거죠.

    좋아요0 댓글수2
    • 구머 2018.03.17 11:07:15

      전적으로 동의하나, 제가 여러가지 추측을 해보았지만 잘 안되더군요ㅜ

      좋아요0
    • 수학자 2018.03.17 11:13:37

      그러게요... 이것도 증가와 감소를 이용하여 풀어야 하는 문제일 수도 있다는 생각이 듭니다. 마찬가지로 l_n = d_n이 성립할 테니깐요.

      좋아요0