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

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}$ 임을 보이세요.

 

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

댓글 12

  • 수학동아 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