슬기로운 수학생활 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번 문제의 풀이를 잘 응용해서 풀 수 있을지 않을까 싶긴 하네요!
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
1.
어떤 논문에서 발견한 내용을 정리하였습니다.(참고논문)
우선 수열을 라 합시다.
그리고 수열의 수에 라는 순서쌍을 할당합시다.
여기서 는
로 끝나는 증가하는 부분수열(이하 부분증가수열)의 최대 길이,
는
로 끝나는 감소하는 부분수열(이하 부분감소수열)의 최대 길이입니다.
그러면 와
에는 다음 성질이 있습니다.
(1)
(2)
이를 간단히 증명해보겠습니다.
(1) 에서
가 c번째,
가 d번째 작은 수라면 (c<d)
이 되어 성립합니다.
(2) 에서
가 c번째,
가 d번째 작은 수라면 (c>d)
이 되어 성립합니다.
이를 통해 알 수 있는 사실은 는 같을 수 없다는 것입니다.
이제 다시 돌아옵시다. 길이가 a인 부분증가수열과 길이가 b인 부분감소수열이 존재하지 않기 위해서는 여야 합니다.
그런데 앞의 증명에 의해 는 같을 수 없으므로
는 최대 (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
이 있네요