폴리매스

슬기로운 수학생활 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번 문제의 풀이를 잘 응용해서 풀 수 있을지 않을까 싶긴 하네요!