본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[슬기로운 수학생활] 슬25. 부분수열 피하기
수학동아 2022.05.01 01:16 조회 249

슬기로운 수학생활 25번

 

 

 

부분수열 피하기

 

 

 

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

 

 

 

 

 

서로 다른 수들로 이루어진 길이 $m$의 수열 $x_1, x_2, \cdots, x_m$이 있다. 이 수열의 부분수열이란 이 수열에서 순서를 유지한 채 몇개의 수들을 일부 골라 새로 만들 수 있는 수열이다. 예를 들면 4, 2, 3, 1, 5의 부분수열로 4, 3, 1이나 2, 5가 있을 수 있다. 수열 3, 2, 1은 2와 3의 위치가 바뀌었으므로 4, 2, 3, 1, 5의 부분수열이 아니다.

 

 

 

 

 

문제 1. 어떤 자연수 $a, b \geq 2$가 고정되어 있다. 증가하는 길이 $a$의 부분수열 $y_1 < y_2 < \cdots < y_a$이나 감소하는 길이 $b$의 부분수열 $z_1 > z_2 > \cdots > z_b$ 가 둘 다 없는 서로 다른 수들의 수열 $x_1, x_2, \cdots, x_m$의 최대 길이 $m$은 얼마인가?

 

 

문제2. 어떤 자연수 $a, b \geq 2$가 고정되어 있다. 모든 $1 \leq i \leq a - 2$에 대해 $y_i < y_{i+2}$를 만족하는 길이 $a$의 부분수열 $y_1, y_2, \cdots, y_a$이나, 모든 $1 \leq j \leq b - 2$에 대해 $z_j > z_{j+2}$를 만족하는 길이 $b$의 부분수열 $z_1, z_2, \cdots, z_b$ 가 둘 다 없는 서로 다른 수들의 수열 $x_1, x_2, \cdots, x_m$의 최대 길이 $m$은 얼마인가?  

 

 

 

 

힌트 : 1번 문제는 Erdős–Szekeres theorem이라는 이름으로 알려진 정리이니 관련 내용을 찾아서 공부해봐도 좋겠습니다! 2번 문제는 저도 답을 모릅니다. 1번 문제의 풀이를 잘 응용해서 풀 수 있을지 않을까 싶긴 하네요!

 

  •  
    구머 Lv.5 2022.05.02 00:10

    1. (a-1)(b-1)

    실례는 간단합니다.

    a-1 a-2 .... 1 -> 2a-2 2a-3 .... a -> 3a-3 3a-4 .... 2a-1 -> ....... -> (b-1)(a-1) (b-1)(a-1)-1 .... (b-2)(a-1)+1

    댓글 작성하기 좋아요0 댓글수2
    •  
      강지원 멘토 Lv.3 2022.05.02 16:07

      실례는 맞습니다! 길이가 (a-1)(b-1)+1 이상이면 증가하는 길이 a의 부분수열이나 감소하는 길이 b의 부분수열이 있다는 사실도 증명해보세요.

      좋아요0
    •  
      구머 Lv.5 2022.05.02 18:38

      저는 이미 대한수학회 9번 문제에서 유사한 문제를 풀어본 적이 있어, 다른 분들께 우선적으로 기회를 드리고자 합니다. 혹시 풀다 막히시는 분들은 대9 문제의 2018.01.27 01:32에 작성한 댓글을 참조하시면 될것 같습니다.

      좋아요0
  •  
    Scubed Lv.6 2022.05.15 16:56
    확인요청중

    1. 

    어떤 논문에서 발견한 내용을 정리하였습니다.(참고논문)

    우선 수열을 x_1, x_2, ..., x_n라 합시다. 

    그리고 수열의 수에 (a_i, b_i)라는 순서쌍을 할당합시다.

    여기서 a_i는 x_i로 끝나는 증가하는 부분수열(이하 부분증가수열)의 최대 길이, b_i는 x_i로 끝나는 감소하는 부분수열(이하 부분감소수열)의 최대 길이입니다.

    그러면 a_i와 b_i에는 다음 성질이 있습니다.

    (1) i< j, x_i< x_j\rightarrow a_i< a_j

    (2) i< j, x_i> x_j\rightarrow b_i< b_j

    이를 간단히 증명해보겠습니다.

    (1) x_i, ..., x_j 에서 x_i가 c번째, x_j가 d번째 작은 수라면 (c<d)  a_j-a_i=d-c>0이 되어 성립합니다.

    (2) x_i, ..., x_j 에서 x_i가 c번째, x_j가 d번째 작은 수라면 (c>d)  b_j-b_i=c-d>0이 되어 성립합니다.

    이를 통해 알 수 있는 사실은 (a_i, b_i)는 같을 수 없다는 것입니다.

    이제 다시 돌아옵시다. 길이가 a인 부분증가수열과 길이가 b인 부분감소수열이 존재하지 않기 위해서는 a_i< a, b_i< b여야 합니다.

    그런데 앞의 증명에 의해 (a_i, b_i)는 같을 수 없으므로 (a_i, b_i)는 최대 (a-1)(b-1)개 존재할 수 있습니다.

    따라서 m의 최댓값은 (a-1)(b-1)입니다.

    실례는 구머님이 제시한 

    a-1, a-2, ...., 1, 2a-2, 2a-3, ...., a, 3a-3, 3a-4, ...., 2a-1, ......., (b-1)(a-1), (b-1)(a-1)-1, ...., (b-2)(a-1)+1

    이 있네요

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

  • ☎문의 02-6749-3911